Passing a binary message to a friend where one of the components is always “turned on”
up vote
4
down vote
favorite
Suppose I want to communicate an integer to a friend between 1 and 1000. In order to pass this message I use a $k$-vector whose entries can be set to $0$ or $1$. So for example if $k=3$, a natural way to express the number $7$ is $langle 1,1,0rangle$, where this corresponds to the binary representation $2^2+2^1+2^0$ for $7$.
However, there is a wrinkle! Before my friend can view my vector, he must pass it through a function $f_i$ which is the identity on all components not equal to $i$, and which sets the $i$-th component to $1$. For example, $f_1(langle 1,1,0rangle) = langle 1,1,0rangle$, but $f_3(langle 1,1,0rangle) = langle 1,1,1rangle$.
Critically, the value of $i$ is unknown to both me and my friend. The challenge is:
What is the smallest $k$ such that my friend can always understand my
number?
My thought process:
Clearly if there were no error $k=10$ would be sufficient. If I simply wanted my friend to know if the message were changed $k=11$ would be sufficient, since I would agree to represent all numbers using a $1$-even representation (i.e. a $k$-binary with an even number of $1$s) and if my friend received an odd number he would know one of the $1$s would have been changed.
Of course he must be able to recover a garbled message. Therefore, all $1$-even vectors which could have plausibly "degenerated" into a $1$-odd vector must be considered equivalent. Therefore I think one can reduce the problem to smaller problems. Let $A^k_j$ be the set of all $k$-vectors with exactly $j$ ones. For all even $j<k$, what is the largest subset $S_j^ksubset A_j^k$ such that no two elements of $S_j^k$ can degenerate into the same vector in $A_{j+1}^k$. If we solve this, then we can sum these maximal cardinalities over all even $j$ and obtain the result.
However, it's not clear how to finish! I'm aware that this seems vaguely related to error correcting codes and Hamming distance - I think the reduced problem can plausibly be reduced to a question about subsets of the permutation group. But I can't quite figure it out...
Edit: Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be 1-even. This is a crude upper bound. I am quite sure one can do much better than this...
Update: Can currently get to as low as $k=15$
I can do $k=15$ as follows: Let $mathbf{v}$ be your original $k$-vector. First encode the message as a $1$-even message with the first $11$ digits. If the message is uncorrupted, your friend will know and you will be done. If it is corrupted, the remaining $4$ digits tell your friend the value of $sum_{i=1}^{11} v_i cdot i (text{mod} 10),$ from which you can infer which digit was flipped.
puzzle coding-theory permutation-cycles
add a comment |
up vote
4
down vote
favorite
Suppose I want to communicate an integer to a friend between 1 and 1000. In order to pass this message I use a $k$-vector whose entries can be set to $0$ or $1$. So for example if $k=3$, a natural way to express the number $7$ is $langle 1,1,0rangle$, where this corresponds to the binary representation $2^2+2^1+2^0$ for $7$.
However, there is a wrinkle! Before my friend can view my vector, he must pass it through a function $f_i$ which is the identity on all components not equal to $i$, and which sets the $i$-th component to $1$. For example, $f_1(langle 1,1,0rangle) = langle 1,1,0rangle$, but $f_3(langle 1,1,0rangle) = langle 1,1,1rangle$.
Critically, the value of $i$ is unknown to both me and my friend. The challenge is:
What is the smallest $k$ such that my friend can always understand my
number?
My thought process:
Clearly if there were no error $k=10$ would be sufficient. If I simply wanted my friend to know if the message were changed $k=11$ would be sufficient, since I would agree to represent all numbers using a $1$-even representation (i.e. a $k$-binary with an even number of $1$s) and if my friend received an odd number he would know one of the $1$s would have been changed.
Of course he must be able to recover a garbled message. Therefore, all $1$-even vectors which could have plausibly "degenerated" into a $1$-odd vector must be considered equivalent. Therefore I think one can reduce the problem to smaller problems. Let $A^k_j$ be the set of all $k$-vectors with exactly $j$ ones. For all even $j<k$, what is the largest subset $S_j^ksubset A_j^k$ such that no two elements of $S_j^k$ can degenerate into the same vector in $A_{j+1}^k$. If we solve this, then we can sum these maximal cardinalities over all even $j$ and obtain the result.
However, it's not clear how to finish! I'm aware that this seems vaguely related to error correcting codes and Hamming distance - I think the reduced problem can plausibly be reduced to a question about subsets of the permutation group. But I can't quite figure it out...
Edit: Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be 1-even. This is a crude upper bound. I am quite sure one can do much better than this...
Update: Can currently get to as low as $k=15$
I can do $k=15$ as follows: Let $mathbf{v}$ be your original $k$-vector. First encode the message as a $1$-even message with the first $11$ digits. If the message is uncorrupted, your friend will know and you will be done. If it is corrupted, the remaining $4$ digits tell your friend the value of $sum_{i=1}^{11} v_i cdot i (text{mod} 10),$ from which you can infer which digit was flipped.
puzzle coding-theory permutation-cycles
There's also an obvious way to get $k = 20$; just duplicate each bit and send that (equivalently, send the string twice).
– platty
Nov 28 at 1:58
The problem with that is that you don't know which number, the first or second, is correct if they don't agree. This is why I wrote that $22$ is an upper bound, because then you can encode them so that you can clearly tell which degenerated.
– Lepidopterist
Nov 28 at 2:14
Not the way you have it written above. If the two numbers differ, it must be in exactly one position -- and it must be the case that this was turned from a 0 into a 1. Otherwise, the two copies are the same and both are the original value.
– platty
Nov 28 at 2:33
Ah, good point! Btw, I think I can get to 15, see new edit.
– Lepidopterist
Nov 28 at 2:37
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Suppose I want to communicate an integer to a friend between 1 and 1000. In order to pass this message I use a $k$-vector whose entries can be set to $0$ or $1$. So for example if $k=3$, a natural way to express the number $7$ is $langle 1,1,0rangle$, where this corresponds to the binary representation $2^2+2^1+2^0$ for $7$.
However, there is a wrinkle! Before my friend can view my vector, he must pass it through a function $f_i$ which is the identity on all components not equal to $i$, and which sets the $i$-th component to $1$. For example, $f_1(langle 1,1,0rangle) = langle 1,1,0rangle$, but $f_3(langle 1,1,0rangle) = langle 1,1,1rangle$.
Critically, the value of $i$ is unknown to both me and my friend. The challenge is:
What is the smallest $k$ such that my friend can always understand my
number?
My thought process:
Clearly if there were no error $k=10$ would be sufficient. If I simply wanted my friend to know if the message were changed $k=11$ would be sufficient, since I would agree to represent all numbers using a $1$-even representation (i.e. a $k$-binary with an even number of $1$s) and if my friend received an odd number he would know one of the $1$s would have been changed.
Of course he must be able to recover a garbled message. Therefore, all $1$-even vectors which could have plausibly "degenerated" into a $1$-odd vector must be considered equivalent. Therefore I think one can reduce the problem to smaller problems. Let $A^k_j$ be the set of all $k$-vectors with exactly $j$ ones. For all even $j<k$, what is the largest subset $S_j^ksubset A_j^k$ such that no two elements of $S_j^k$ can degenerate into the same vector in $A_{j+1}^k$. If we solve this, then we can sum these maximal cardinalities over all even $j$ and obtain the result.
However, it's not clear how to finish! I'm aware that this seems vaguely related to error correcting codes and Hamming distance - I think the reduced problem can plausibly be reduced to a question about subsets of the permutation group. But I can't quite figure it out...
Edit: Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be 1-even. This is a crude upper bound. I am quite sure one can do much better than this...
Update: Can currently get to as low as $k=15$
I can do $k=15$ as follows: Let $mathbf{v}$ be your original $k$-vector. First encode the message as a $1$-even message with the first $11$ digits. If the message is uncorrupted, your friend will know and you will be done. If it is corrupted, the remaining $4$ digits tell your friend the value of $sum_{i=1}^{11} v_i cdot i (text{mod} 10),$ from which you can infer which digit was flipped.
puzzle coding-theory permutation-cycles
Suppose I want to communicate an integer to a friend between 1 and 1000. In order to pass this message I use a $k$-vector whose entries can be set to $0$ or $1$. So for example if $k=3$, a natural way to express the number $7$ is $langle 1,1,0rangle$, where this corresponds to the binary representation $2^2+2^1+2^0$ for $7$.
However, there is a wrinkle! Before my friend can view my vector, he must pass it through a function $f_i$ which is the identity on all components not equal to $i$, and which sets the $i$-th component to $1$. For example, $f_1(langle 1,1,0rangle) = langle 1,1,0rangle$, but $f_3(langle 1,1,0rangle) = langle 1,1,1rangle$.
Critically, the value of $i$ is unknown to both me and my friend. The challenge is:
What is the smallest $k$ such that my friend can always understand my
number?
My thought process:
Clearly if there were no error $k=10$ would be sufficient. If I simply wanted my friend to know if the message were changed $k=11$ would be sufficient, since I would agree to represent all numbers using a $1$-even representation (i.e. a $k$-binary with an even number of $1$s) and if my friend received an odd number he would know one of the $1$s would have been changed.
Of course he must be able to recover a garbled message. Therefore, all $1$-even vectors which could have plausibly "degenerated" into a $1$-odd vector must be considered equivalent. Therefore I think one can reduce the problem to smaller problems. Let $A^k_j$ be the set of all $k$-vectors with exactly $j$ ones. For all even $j<k$, what is the largest subset $S_j^ksubset A_j^k$ such that no two elements of $S_j^k$ can degenerate into the same vector in $A_{j+1}^k$. If we solve this, then we can sum these maximal cardinalities over all even $j$ and obtain the result.
However, it's not clear how to finish! I'm aware that this seems vaguely related to error correcting codes and Hamming distance - I think the reduced problem can plausibly be reduced to a question about subsets of the permutation group. But I can't quite figure it out...
Edit: Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be 1-even. This is a crude upper bound. I am quite sure one can do much better than this...
Update: Can currently get to as low as $k=15$
I can do $k=15$ as follows: Let $mathbf{v}$ be your original $k$-vector. First encode the message as a $1$-even message with the first $11$ digits. If the message is uncorrupted, your friend will know and you will be done. If it is corrupted, the remaining $4$ digits tell your friend the value of $sum_{i=1}^{11} v_i cdot i (text{mod} 10),$ from which you can infer which digit was flipped.
puzzle coding-theory permutation-cycles
puzzle coding-theory permutation-cycles
edited Nov 28 at 11:54
amWhy
191k27223438
191k27223438
asked Nov 28 at 1:23
Lepidopterist
9991026
9991026
There's also an obvious way to get $k = 20$; just duplicate each bit and send that (equivalently, send the string twice).
– platty
Nov 28 at 1:58
The problem with that is that you don't know which number, the first or second, is correct if they don't agree. This is why I wrote that $22$ is an upper bound, because then you can encode them so that you can clearly tell which degenerated.
– Lepidopterist
Nov 28 at 2:14
Not the way you have it written above. If the two numbers differ, it must be in exactly one position -- and it must be the case that this was turned from a 0 into a 1. Otherwise, the two copies are the same and both are the original value.
– platty
Nov 28 at 2:33
Ah, good point! Btw, I think I can get to 15, see new edit.
– Lepidopterist
Nov 28 at 2:37
add a comment |
There's also an obvious way to get $k = 20$; just duplicate each bit and send that (equivalently, send the string twice).
– platty
Nov 28 at 1:58
The problem with that is that you don't know which number, the first or second, is correct if they don't agree. This is why I wrote that $22$ is an upper bound, because then you can encode them so that you can clearly tell which degenerated.
– Lepidopterist
Nov 28 at 2:14
Not the way you have it written above. If the two numbers differ, it must be in exactly one position -- and it must be the case that this was turned from a 0 into a 1. Otherwise, the two copies are the same and both are the original value.
– platty
Nov 28 at 2:33
Ah, good point! Btw, I think I can get to 15, see new edit.
– Lepidopterist
Nov 28 at 2:37
There's also an obvious way to get $k = 20$; just duplicate each bit and send that (equivalently, send the string twice).
– platty
Nov 28 at 1:58
There's also an obvious way to get $k = 20$; just duplicate each bit and send that (equivalently, send the string twice).
– platty
Nov 28 at 1:58
The problem with that is that you don't know which number, the first or second, is correct if they don't agree. This is why I wrote that $22$ is an upper bound, because then you can encode them so that you can clearly tell which degenerated.
– Lepidopterist
Nov 28 at 2:14
The problem with that is that you don't know which number, the first or second, is correct if they don't agree. This is why I wrote that $22$ is an upper bound, because then you can encode them so that you can clearly tell which degenerated.
– Lepidopterist
Nov 28 at 2:14
Not the way you have it written above. If the two numbers differ, it must be in exactly one position -- and it must be the case that this was turned from a 0 into a 1. Otherwise, the two copies are the same and both are the original value.
– platty
Nov 28 at 2:33
Not the way you have it written above. If the two numbers differ, it must be in exactly one position -- and it must be the case that this was turned from a 0 into a 1. Otherwise, the two copies are the same and both are the original value.
– platty
Nov 28 at 2:33
Ah, good point! Btw, I think I can get to 15, see new edit.
– Lepidopterist
Nov 28 at 2:37
Ah, good point! Btw, I think I can get to 15, see new edit.
– Lepidopterist
Nov 28 at 2:37
add a comment |
3 Answers
3
active
oldest
votes
up vote
5
down vote
accepted
Let me use, as usual, $k$ for the "data bits" and $n$ for the total bits sent, with $n-k$ being the redundancy.
$n=14$ bits should be enough
Take $k=10$ , $n-k=4$. Build a Hamming parity check with $n-k=4$ rows, placing the $2^4$ distinct columns, except for the null column and some extra column (I chose the all-ones column) :
$$H=begin{pmatrix}
1&0&0&0&1&1&1&0&0&0&1&1&1&0\
0&1&0&0&1&0&0&1&1&0&1&1&0&1\
0&0&1&0&0&1&0&1&0&1&1&0&1&1\
0&0&0&1&0&0&1&0&1&1&0&1&1&1
end{pmatrix}=( I_4 mid P)
$$
The corresponding generator matrix is
$$ G= (P^t , | , I_{10})$$
This linear code (a shortened Hamming code) has distance $d=3$ (because you need to pick at least three columns of $H$ to get a linearly dependent set), so you can correct a single error. (Not only $0to 1$ but also $1 to 0$)
And you can trasmit $2^k=1024$ values (more than $1000$).
Because this encoding corrects more errors than needed (we have some kind of Z-channel, instead of a BSC channel), it remains to be seen if $n$ can be further reduced.
Update. $n=13$ is not enough. There is some literature about this scenario, a (not necessarily linear) code for a Z-channel, with single-error correcting capability. Several bounds and construction methods have been found. A 1983 survey (updated in 1995) can be found in the report Error Correcting Codes for the Asymmetric Channel (Torleiv Kløve). A table in page 38, shows that, for our scenario, $n=14$ is enough for sending at least $M=1096$ messages (a slight improvement against my simple shortened Hamming code), an upper bound is $Mle 1500$. For $n=13$, an upper bound is $Mle 786$ (so we cannot send 1000 messages), and the best found construction gives only $M=586$. A more recent (2009) paper in Russian, here.
2
As noted in the comments on @mlerma54's answer, 14 should be optimal; there are $1000 cdot 11$ distinct outcomes that must be handled, and $log_2(11000) approx 13.42$.
– platty
Nov 28 at 6:24
@leonbloy Thanks for this excellent answer, which I will likely accept. One confusion I have is that your update seems to imply that mlerma54's argument, cited by platty, is not convincing and requires the references you've cited. It would be extremely illuminating to understand what is wrong with that argument, if indeed that is the case. It struck me as convincing.
– Lepidopterist
Nov 29 at 0:36
@Lepidopterist Yes, I don't find mlerma54's argument convincing, but perhaps I don't really understand it. It seems to me that it assumes things that are not necessary or obvious - for one thing, it assumes that the information bits and the "parity" bits must be sent separately (yet it does not deal with the case where the errors occur inside the parity bits); it also disregards the asymmetry in the errors here. And so on. Neither I really understand the comment by platty above.
– leonbloy
Nov 29 at 1:43
I was convinced by the simpler argument: the message requires at least $log_2(1000)$ bits. This bits can be altered, so one must be able to determine which bit has been altered. This requires us to identify, at the very least, which of these $log_2(1000)$ bits has been altered. This leads to the lower bound $log_2(1000) + log_2(log_2(1000))$. This, I think conservative, lower bound doesn't require any assumption about how to deal with the more complicated problem of the error in the parity bits.
– Lepidopterist
Nov 29 at 2:14
The bound is conservative in that respect, but it's not in the other: we don't always require to "identify which of these log2(1000) bits has been altered" because sometimes the selected bit is a 1 (hence, if the sent message has five 0' and five 1's, we only need to identify six cases.
– leonbloy
2 days ago
add a comment |
up vote
2
down vote
This may not be the best possible, but I think it works.
[Added: After I posted my answer, I saw that the OP found a similar, but better, strategy to send the message using one fewer bit.]
Encode the number $N$ as a $10$-bit base-$2$ value $b_1b_2dots b_{10}$, and then send an $16$-bit message comprising your number followed by the binary representation of $f(N)=b_1+2b_2+3b_3+4b_4+5b_5+6b_6+7b_7+8b_8+9b_9+10b_{10}$
(which is between $0$ and $55$, so requires $6$ bits). Share the formula for $f$ with your friend.
Your friend decodes the first $10$ bits of the message as $x$ and the last $6$ bits as $F$. If $F=f(x)$, then your message was $x$. If $F<f(x)$, then a $0$ bit of $x$ was set to $1$ during transmission. The value of $f(x)-F$ tells you which bit it was, and $N=x-2^{10-f(x)+F}$. If $F>f(x)$, a $0$ bit of $f(N)$ was set during transmission, and $N=x$.
add a comment |
up vote
2
down vote
[Ok, I am amending my waaay suboptimal answer (which I gave after misreading the question and used k=30 in a trivial way).]
This is my new solution with k=14 (which in my comments showed cannot be improved) [I see leonbloy already posted a solution with k=14 using Hamming code, mine goes more in the direction previously tried by the OP].
Let ${v_i}_{i=1}^{10}$ the 10 components (0's and 1's) of your binary vector. Let $x$ be
$$
x = 3v_1 + 5v_2 + 6v_3 + 7v_4 + 9v_5 + 10v_6 + 11v_7 + 12v_8 + 13v_9 + 14v_{10}
$$
(note I have omitted coefficients that are exact powers of 2).
Then compute $y = x pmod{16}$, express it as a binary number with 4 bits, and append it to your string. You get a 14-bit binary string, and send it to your friend. Your friend computes $x pmod{16}$ and compares it to $y$ from the string he receives. If the difference is not a power of 2 then it tells him which coefficient is missing in the formula used to compute his $x$, and which bit has been altered in your original vector. If it is a power of 2, then the part altered is $y$, and your original vector has not been modified.
Would that work?
This is not anywhere close to the minimum. Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be $1$-even, in my notation. I think you must be able to do much better. An answer to this should argue what the minimum $k$ is...
– Lepidopterist
Nov 28 at 1:49
Sorry, I read to quick and I missed that your are specifically looking for the minimum k, I apologize. the only thing that comes to my mind is a theoretical lower bound of $kgeq 14$, since you need to pass 10 bits of information and your friend should have some additional information if he is able to determine which bit is the one altered, so that is 4 extra bits. I can think of some ways to solve the problem with less than 22 bits, but my best approach would require 17 bits, so all I can say is $17 geq k geq 14$.
– mlerma54
Nov 28 at 2:24
Your answer would be greatly improved if you could rigorously show why the lower bound is $14$. I can think of a way with $15$, which I'll write above.
– Lepidopterist
Nov 28 at 2:29
2
After recieving your string of 0's and 1's your friend will be able to detemine which of the 1000 numbers you have transmitted, and also which of your binary digits was altered. The first task requires at least $log_2(1000)$ bits of information, wich can only be attained with a string of at least 10 bits. The second (independent) piece of information, which bit has been altered, cannot be less than $log_2(10)$. So at least $log_2(1000) + log_2(10) = 13.2877dots$ bits of information must be transmitted. Hence $k > 13.2877dots$, and since it must be an integer, $kgeq 14$.
– mlerma54
Nov 28 at 2:52
If you make this your answer I'll add +1. What is not clear is whether one also needs $log_2(2)$ bits of information to understand whether the information about which bit has been altered has itself been altered! If it's possible to get to $k=14$ then one has to construct the message so as to infer whether to trust the message (the first 10 digits) or the $4$ bits that tell you where the error is...
– Lepidopterist
Nov 28 at 3:01
|
show 1 more comment
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
Let me use, as usual, $k$ for the "data bits" and $n$ for the total bits sent, with $n-k$ being the redundancy.
$n=14$ bits should be enough
Take $k=10$ , $n-k=4$. Build a Hamming parity check with $n-k=4$ rows, placing the $2^4$ distinct columns, except for the null column and some extra column (I chose the all-ones column) :
$$H=begin{pmatrix}
1&0&0&0&1&1&1&0&0&0&1&1&1&0\
0&1&0&0&1&0&0&1&1&0&1&1&0&1\
0&0&1&0&0&1&0&1&0&1&1&0&1&1\
0&0&0&1&0&0&1&0&1&1&0&1&1&1
end{pmatrix}=( I_4 mid P)
$$
The corresponding generator matrix is
$$ G= (P^t , | , I_{10})$$
This linear code (a shortened Hamming code) has distance $d=3$ (because you need to pick at least three columns of $H$ to get a linearly dependent set), so you can correct a single error. (Not only $0to 1$ but also $1 to 0$)
And you can trasmit $2^k=1024$ values (more than $1000$).
Because this encoding corrects more errors than needed (we have some kind of Z-channel, instead of a BSC channel), it remains to be seen if $n$ can be further reduced.
Update. $n=13$ is not enough. There is some literature about this scenario, a (not necessarily linear) code for a Z-channel, with single-error correcting capability. Several bounds and construction methods have been found. A 1983 survey (updated in 1995) can be found in the report Error Correcting Codes for the Asymmetric Channel (Torleiv Kløve). A table in page 38, shows that, for our scenario, $n=14$ is enough for sending at least $M=1096$ messages (a slight improvement against my simple shortened Hamming code), an upper bound is $Mle 1500$. For $n=13$, an upper bound is $Mle 786$ (so we cannot send 1000 messages), and the best found construction gives only $M=586$. A more recent (2009) paper in Russian, here.
2
As noted in the comments on @mlerma54's answer, 14 should be optimal; there are $1000 cdot 11$ distinct outcomes that must be handled, and $log_2(11000) approx 13.42$.
– platty
Nov 28 at 6:24
@leonbloy Thanks for this excellent answer, which I will likely accept. One confusion I have is that your update seems to imply that mlerma54's argument, cited by platty, is not convincing and requires the references you've cited. It would be extremely illuminating to understand what is wrong with that argument, if indeed that is the case. It struck me as convincing.
– Lepidopterist
Nov 29 at 0:36
@Lepidopterist Yes, I don't find mlerma54's argument convincing, but perhaps I don't really understand it. It seems to me that it assumes things that are not necessary or obvious - for one thing, it assumes that the information bits and the "parity" bits must be sent separately (yet it does not deal with the case where the errors occur inside the parity bits); it also disregards the asymmetry in the errors here. And so on. Neither I really understand the comment by platty above.
– leonbloy
Nov 29 at 1:43
I was convinced by the simpler argument: the message requires at least $log_2(1000)$ bits. This bits can be altered, so one must be able to determine which bit has been altered. This requires us to identify, at the very least, which of these $log_2(1000)$ bits has been altered. This leads to the lower bound $log_2(1000) + log_2(log_2(1000))$. This, I think conservative, lower bound doesn't require any assumption about how to deal with the more complicated problem of the error in the parity bits.
– Lepidopterist
Nov 29 at 2:14
The bound is conservative in that respect, but it's not in the other: we don't always require to "identify which of these log2(1000) bits has been altered" because sometimes the selected bit is a 1 (hence, if the sent message has five 0' and five 1's, we only need to identify six cases.
– leonbloy
2 days ago
add a comment |
up vote
5
down vote
accepted
Let me use, as usual, $k$ for the "data bits" and $n$ for the total bits sent, with $n-k$ being the redundancy.
$n=14$ bits should be enough
Take $k=10$ , $n-k=4$. Build a Hamming parity check with $n-k=4$ rows, placing the $2^4$ distinct columns, except for the null column and some extra column (I chose the all-ones column) :
$$H=begin{pmatrix}
1&0&0&0&1&1&1&0&0&0&1&1&1&0\
0&1&0&0&1&0&0&1&1&0&1&1&0&1\
0&0&1&0&0&1&0&1&0&1&1&0&1&1\
0&0&0&1&0&0&1&0&1&1&0&1&1&1
end{pmatrix}=( I_4 mid P)
$$
The corresponding generator matrix is
$$ G= (P^t , | , I_{10})$$
This linear code (a shortened Hamming code) has distance $d=3$ (because you need to pick at least three columns of $H$ to get a linearly dependent set), so you can correct a single error. (Not only $0to 1$ but also $1 to 0$)
And you can trasmit $2^k=1024$ values (more than $1000$).
Because this encoding corrects more errors than needed (we have some kind of Z-channel, instead of a BSC channel), it remains to be seen if $n$ can be further reduced.
Update. $n=13$ is not enough. There is some literature about this scenario, a (not necessarily linear) code for a Z-channel, with single-error correcting capability. Several bounds and construction methods have been found. A 1983 survey (updated in 1995) can be found in the report Error Correcting Codes for the Asymmetric Channel (Torleiv Kløve). A table in page 38, shows that, for our scenario, $n=14$ is enough for sending at least $M=1096$ messages (a slight improvement against my simple shortened Hamming code), an upper bound is $Mle 1500$. For $n=13$, an upper bound is $Mle 786$ (so we cannot send 1000 messages), and the best found construction gives only $M=586$. A more recent (2009) paper in Russian, here.
2
As noted in the comments on @mlerma54's answer, 14 should be optimal; there are $1000 cdot 11$ distinct outcomes that must be handled, and $log_2(11000) approx 13.42$.
– platty
Nov 28 at 6:24
@leonbloy Thanks for this excellent answer, which I will likely accept. One confusion I have is that your update seems to imply that mlerma54's argument, cited by platty, is not convincing and requires the references you've cited. It would be extremely illuminating to understand what is wrong with that argument, if indeed that is the case. It struck me as convincing.
– Lepidopterist
Nov 29 at 0:36
@Lepidopterist Yes, I don't find mlerma54's argument convincing, but perhaps I don't really understand it. It seems to me that it assumes things that are not necessary or obvious - for one thing, it assumes that the information bits and the "parity" bits must be sent separately (yet it does not deal with the case where the errors occur inside the parity bits); it also disregards the asymmetry in the errors here. And so on. Neither I really understand the comment by platty above.
– leonbloy
Nov 29 at 1:43
I was convinced by the simpler argument: the message requires at least $log_2(1000)$ bits. This bits can be altered, so one must be able to determine which bit has been altered. This requires us to identify, at the very least, which of these $log_2(1000)$ bits has been altered. This leads to the lower bound $log_2(1000) + log_2(log_2(1000))$. This, I think conservative, lower bound doesn't require any assumption about how to deal with the more complicated problem of the error in the parity bits.
– Lepidopterist
Nov 29 at 2:14
The bound is conservative in that respect, but it's not in the other: we don't always require to "identify which of these log2(1000) bits has been altered" because sometimes the selected bit is a 1 (hence, if the sent message has five 0' and five 1's, we only need to identify six cases.
– leonbloy
2 days ago
add a comment |
up vote
5
down vote
accepted
up vote
5
down vote
accepted
Let me use, as usual, $k$ for the "data bits" and $n$ for the total bits sent, with $n-k$ being the redundancy.
$n=14$ bits should be enough
Take $k=10$ , $n-k=4$. Build a Hamming parity check with $n-k=4$ rows, placing the $2^4$ distinct columns, except for the null column and some extra column (I chose the all-ones column) :
$$H=begin{pmatrix}
1&0&0&0&1&1&1&0&0&0&1&1&1&0\
0&1&0&0&1&0&0&1&1&0&1&1&0&1\
0&0&1&0&0&1&0&1&0&1&1&0&1&1\
0&0&0&1&0&0&1&0&1&1&0&1&1&1
end{pmatrix}=( I_4 mid P)
$$
The corresponding generator matrix is
$$ G= (P^t , | , I_{10})$$
This linear code (a shortened Hamming code) has distance $d=3$ (because you need to pick at least three columns of $H$ to get a linearly dependent set), so you can correct a single error. (Not only $0to 1$ but also $1 to 0$)
And you can trasmit $2^k=1024$ values (more than $1000$).
Because this encoding corrects more errors than needed (we have some kind of Z-channel, instead of a BSC channel), it remains to be seen if $n$ can be further reduced.
Update. $n=13$ is not enough. There is some literature about this scenario, a (not necessarily linear) code for a Z-channel, with single-error correcting capability. Several bounds and construction methods have been found. A 1983 survey (updated in 1995) can be found in the report Error Correcting Codes for the Asymmetric Channel (Torleiv Kløve). A table in page 38, shows that, for our scenario, $n=14$ is enough for sending at least $M=1096$ messages (a slight improvement against my simple shortened Hamming code), an upper bound is $Mle 1500$. For $n=13$, an upper bound is $Mle 786$ (so we cannot send 1000 messages), and the best found construction gives only $M=586$. A more recent (2009) paper in Russian, here.
Let me use, as usual, $k$ for the "data bits" and $n$ for the total bits sent, with $n-k$ being the redundancy.
$n=14$ bits should be enough
Take $k=10$ , $n-k=4$. Build a Hamming parity check with $n-k=4$ rows, placing the $2^4$ distinct columns, except for the null column and some extra column (I chose the all-ones column) :
$$H=begin{pmatrix}
1&0&0&0&1&1&1&0&0&0&1&1&1&0\
0&1&0&0&1&0&0&1&1&0&1&1&0&1\
0&0&1&0&0&1&0&1&0&1&1&0&1&1\
0&0&0&1&0&0&1&0&1&1&0&1&1&1
end{pmatrix}=( I_4 mid P)
$$
The corresponding generator matrix is
$$ G= (P^t , | , I_{10})$$
This linear code (a shortened Hamming code) has distance $d=3$ (because you need to pick at least three columns of $H$ to get a linearly dependent set), so you can correct a single error. (Not only $0to 1$ but also $1 to 0$)
And you can trasmit $2^k=1024$ values (more than $1000$).
Because this encoding corrects more errors than needed (we have some kind of Z-channel, instead of a BSC channel), it remains to be seen if $n$ can be further reduced.
Update. $n=13$ is not enough. There is some literature about this scenario, a (not necessarily linear) code for a Z-channel, with single-error correcting capability. Several bounds and construction methods have been found. A 1983 survey (updated in 1995) can be found in the report Error Correcting Codes for the Asymmetric Channel (Torleiv Kløve). A table in page 38, shows that, for our scenario, $n=14$ is enough for sending at least $M=1096$ messages (a slight improvement against my simple shortened Hamming code), an upper bound is $Mle 1500$. For $n=13$, an upper bound is $Mle 786$ (so we cannot send 1000 messages), and the best found construction gives only $M=586$. A more recent (2009) paper in Russian, here.
edited Nov 28 at 19:35
answered Nov 28 at 5:05
leonbloy
39.8k645106
39.8k645106
2
As noted in the comments on @mlerma54's answer, 14 should be optimal; there are $1000 cdot 11$ distinct outcomes that must be handled, and $log_2(11000) approx 13.42$.
– platty
Nov 28 at 6:24
@leonbloy Thanks for this excellent answer, which I will likely accept. One confusion I have is that your update seems to imply that mlerma54's argument, cited by platty, is not convincing and requires the references you've cited. It would be extremely illuminating to understand what is wrong with that argument, if indeed that is the case. It struck me as convincing.
– Lepidopterist
Nov 29 at 0:36
@Lepidopterist Yes, I don't find mlerma54's argument convincing, but perhaps I don't really understand it. It seems to me that it assumes things that are not necessary or obvious - for one thing, it assumes that the information bits and the "parity" bits must be sent separately (yet it does not deal with the case where the errors occur inside the parity bits); it also disregards the asymmetry in the errors here. And so on. Neither I really understand the comment by platty above.
– leonbloy
Nov 29 at 1:43
I was convinced by the simpler argument: the message requires at least $log_2(1000)$ bits. This bits can be altered, so one must be able to determine which bit has been altered. This requires us to identify, at the very least, which of these $log_2(1000)$ bits has been altered. This leads to the lower bound $log_2(1000) + log_2(log_2(1000))$. This, I think conservative, lower bound doesn't require any assumption about how to deal with the more complicated problem of the error in the parity bits.
– Lepidopterist
Nov 29 at 2:14
The bound is conservative in that respect, but it's not in the other: we don't always require to "identify which of these log2(1000) bits has been altered" because sometimes the selected bit is a 1 (hence, if the sent message has five 0' and five 1's, we only need to identify six cases.
– leonbloy
2 days ago
add a comment |
2
As noted in the comments on @mlerma54's answer, 14 should be optimal; there are $1000 cdot 11$ distinct outcomes that must be handled, and $log_2(11000) approx 13.42$.
– platty
Nov 28 at 6:24
@leonbloy Thanks for this excellent answer, which I will likely accept. One confusion I have is that your update seems to imply that mlerma54's argument, cited by platty, is not convincing and requires the references you've cited. It would be extremely illuminating to understand what is wrong with that argument, if indeed that is the case. It struck me as convincing.
– Lepidopterist
Nov 29 at 0:36
@Lepidopterist Yes, I don't find mlerma54's argument convincing, but perhaps I don't really understand it. It seems to me that it assumes things that are not necessary or obvious - for one thing, it assumes that the information bits and the "parity" bits must be sent separately (yet it does not deal with the case where the errors occur inside the parity bits); it also disregards the asymmetry in the errors here. And so on. Neither I really understand the comment by platty above.
– leonbloy
Nov 29 at 1:43
I was convinced by the simpler argument: the message requires at least $log_2(1000)$ bits. This bits can be altered, so one must be able to determine which bit has been altered. This requires us to identify, at the very least, which of these $log_2(1000)$ bits has been altered. This leads to the lower bound $log_2(1000) + log_2(log_2(1000))$. This, I think conservative, lower bound doesn't require any assumption about how to deal with the more complicated problem of the error in the parity bits.
– Lepidopterist
Nov 29 at 2:14
The bound is conservative in that respect, but it's not in the other: we don't always require to "identify which of these log2(1000) bits has been altered" because sometimes the selected bit is a 1 (hence, if the sent message has five 0' and five 1's, we only need to identify six cases.
– leonbloy
2 days ago
2
2
As noted in the comments on @mlerma54's answer, 14 should be optimal; there are $1000 cdot 11$ distinct outcomes that must be handled, and $log_2(11000) approx 13.42$.
– platty
Nov 28 at 6:24
As noted in the comments on @mlerma54's answer, 14 should be optimal; there are $1000 cdot 11$ distinct outcomes that must be handled, and $log_2(11000) approx 13.42$.
– platty
Nov 28 at 6:24
@leonbloy Thanks for this excellent answer, which I will likely accept. One confusion I have is that your update seems to imply that mlerma54's argument, cited by platty, is not convincing and requires the references you've cited. It would be extremely illuminating to understand what is wrong with that argument, if indeed that is the case. It struck me as convincing.
– Lepidopterist
Nov 29 at 0:36
@leonbloy Thanks for this excellent answer, which I will likely accept. One confusion I have is that your update seems to imply that mlerma54's argument, cited by platty, is not convincing and requires the references you've cited. It would be extremely illuminating to understand what is wrong with that argument, if indeed that is the case. It struck me as convincing.
– Lepidopterist
Nov 29 at 0:36
@Lepidopterist Yes, I don't find mlerma54's argument convincing, but perhaps I don't really understand it. It seems to me that it assumes things that are not necessary or obvious - for one thing, it assumes that the information bits and the "parity" bits must be sent separately (yet it does not deal with the case where the errors occur inside the parity bits); it also disregards the asymmetry in the errors here. And so on. Neither I really understand the comment by platty above.
– leonbloy
Nov 29 at 1:43
@Lepidopterist Yes, I don't find mlerma54's argument convincing, but perhaps I don't really understand it. It seems to me that it assumes things that are not necessary or obvious - for one thing, it assumes that the information bits and the "parity" bits must be sent separately (yet it does not deal with the case where the errors occur inside the parity bits); it also disregards the asymmetry in the errors here. And so on. Neither I really understand the comment by platty above.
– leonbloy
Nov 29 at 1:43
I was convinced by the simpler argument: the message requires at least $log_2(1000)$ bits. This bits can be altered, so one must be able to determine which bit has been altered. This requires us to identify, at the very least, which of these $log_2(1000)$ bits has been altered. This leads to the lower bound $log_2(1000) + log_2(log_2(1000))$. This, I think conservative, lower bound doesn't require any assumption about how to deal with the more complicated problem of the error in the parity bits.
– Lepidopterist
Nov 29 at 2:14
I was convinced by the simpler argument: the message requires at least $log_2(1000)$ bits. This bits can be altered, so one must be able to determine which bit has been altered. This requires us to identify, at the very least, which of these $log_2(1000)$ bits has been altered. This leads to the lower bound $log_2(1000) + log_2(log_2(1000))$. This, I think conservative, lower bound doesn't require any assumption about how to deal with the more complicated problem of the error in the parity bits.
– Lepidopterist
Nov 29 at 2:14
The bound is conservative in that respect, but it's not in the other: we don't always require to "identify which of these log2(1000) bits has been altered" because sometimes the selected bit is a 1 (hence, if the sent message has five 0' and five 1's, we only need to identify six cases.
– leonbloy
2 days ago
The bound is conservative in that respect, but it's not in the other: we don't always require to "identify which of these log2(1000) bits has been altered" because sometimes the selected bit is a 1 (hence, if the sent message has five 0' and five 1's, we only need to identify six cases.
– leonbloy
2 days ago
add a comment |
up vote
2
down vote
This may not be the best possible, but I think it works.
[Added: After I posted my answer, I saw that the OP found a similar, but better, strategy to send the message using one fewer bit.]
Encode the number $N$ as a $10$-bit base-$2$ value $b_1b_2dots b_{10}$, and then send an $16$-bit message comprising your number followed by the binary representation of $f(N)=b_1+2b_2+3b_3+4b_4+5b_5+6b_6+7b_7+8b_8+9b_9+10b_{10}$
(which is between $0$ and $55$, so requires $6$ bits). Share the formula for $f$ with your friend.
Your friend decodes the first $10$ bits of the message as $x$ and the last $6$ bits as $F$. If $F=f(x)$, then your message was $x$. If $F<f(x)$, then a $0$ bit of $x$ was set to $1$ during transmission. The value of $f(x)-F$ tells you which bit it was, and $N=x-2^{10-f(x)+F}$. If $F>f(x)$, a $0$ bit of $f(N)$ was set during transmission, and $N=x$.
add a comment |
up vote
2
down vote
This may not be the best possible, but I think it works.
[Added: After I posted my answer, I saw that the OP found a similar, but better, strategy to send the message using one fewer bit.]
Encode the number $N$ as a $10$-bit base-$2$ value $b_1b_2dots b_{10}$, and then send an $16$-bit message comprising your number followed by the binary representation of $f(N)=b_1+2b_2+3b_3+4b_4+5b_5+6b_6+7b_7+8b_8+9b_9+10b_{10}$
(which is between $0$ and $55$, so requires $6$ bits). Share the formula for $f$ with your friend.
Your friend decodes the first $10$ bits of the message as $x$ and the last $6$ bits as $F$. If $F=f(x)$, then your message was $x$. If $F<f(x)$, then a $0$ bit of $x$ was set to $1$ during transmission. The value of $f(x)-F$ tells you which bit it was, and $N=x-2^{10-f(x)+F}$. If $F>f(x)$, a $0$ bit of $f(N)$ was set during transmission, and $N=x$.
add a comment |
up vote
2
down vote
up vote
2
down vote
This may not be the best possible, but I think it works.
[Added: After I posted my answer, I saw that the OP found a similar, but better, strategy to send the message using one fewer bit.]
Encode the number $N$ as a $10$-bit base-$2$ value $b_1b_2dots b_{10}$, and then send an $16$-bit message comprising your number followed by the binary representation of $f(N)=b_1+2b_2+3b_3+4b_4+5b_5+6b_6+7b_7+8b_8+9b_9+10b_{10}$
(which is between $0$ and $55$, so requires $6$ bits). Share the formula for $f$ with your friend.
Your friend decodes the first $10$ bits of the message as $x$ and the last $6$ bits as $F$. If $F=f(x)$, then your message was $x$. If $F<f(x)$, then a $0$ bit of $x$ was set to $1$ during transmission. The value of $f(x)-F$ tells you which bit it was, and $N=x-2^{10-f(x)+F}$. If $F>f(x)$, a $0$ bit of $f(N)$ was set during transmission, and $N=x$.
This may not be the best possible, but I think it works.
[Added: After I posted my answer, I saw that the OP found a similar, but better, strategy to send the message using one fewer bit.]
Encode the number $N$ as a $10$-bit base-$2$ value $b_1b_2dots b_{10}$, and then send an $16$-bit message comprising your number followed by the binary representation of $f(N)=b_1+2b_2+3b_3+4b_4+5b_5+6b_6+7b_7+8b_8+9b_9+10b_{10}$
(which is between $0$ and $55$, so requires $6$ bits). Share the formula for $f$ with your friend.
Your friend decodes the first $10$ bits of the message as $x$ and the last $6$ bits as $F$. If $F=f(x)$, then your message was $x$. If $F<f(x)$, then a $0$ bit of $x$ was set to $1$ during transmission. The value of $f(x)-F$ tells you which bit it was, and $N=x-2^{10-f(x)+F}$. If $F>f(x)$, a $0$ bit of $f(N)$ was set during transmission, and $N=x$.
edited Nov 28 at 2:45
answered Nov 28 at 2:39
Steve Kass
10.9k11429
10.9k11429
add a comment |
add a comment |
up vote
2
down vote
[Ok, I am amending my waaay suboptimal answer (which I gave after misreading the question and used k=30 in a trivial way).]
This is my new solution with k=14 (which in my comments showed cannot be improved) [I see leonbloy already posted a solution with k=14 using Hamming code, mine goes more in the direction previously tried by the OP].
Let ${v_i}_{i=1}^{10}$ the 10 components (0's and 1's) of your binary vector. Let $x$ be
$$
x = 3v_1 + 5v_2 + 6v_3 + 7v_4 + 9v_5 + 10v_6 + 11v_7 + 12v_8 + 13v_9 + 14v_{10}
$$
(note I have omitted coefficients that are exact powers of 2).
Then compute $y = x pmod{16}$, express it as a binary number with 4 bits, and append it to your string. You get a 14-bit binary string, and send it to your friend. Your friend computes $x pmod{16}$ and compares it to $y$ from the string he receives. If the difference is not a power of 2 then it tells him which coefficient is missing in the formula used to compute his $x$, and which bit has been altered in your original vector. If it is a power of 2, then the part altered is $y$, and your original vector has not been modified.
Would that work?
This is not anywhere close to the minimum. Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be $1$-even, in my notation. I think you must be able to do much better. An answer to this should argue what the minimum $k$ is...
– Lepidopterist
Nov 28 at 1:49
Sorry, I read to quick and I missed that your are specifically looking for the minimum k, I apologize. the only thing that comes to my mind is a theoretical lower bound of $kgeq 14$, since you need to pass 10 bits of information and your friend should have some additional information if he is able to determine which bit is the one altered, so that is 4 extra bits. I can think of some ways to solve the problem with less than 22 bits, but my best approach would require 17 bits, so all I can say is $17 geq k geq 14$.
– mlerma54
Nov 28 at 2:24
Your answer would be greatly improved if you could rigorously show why the lower bound is $14$. I can think of a way with $15$, which I'll write above.
– Lepidopterist
Nov 28 at 2:29
2
After recieving your string of 0's and 1's your friend will be able to detemine which of the 1000 numbers you have transmitted, and also which of your binary digits was altered. The first task requires at least $log_2(1000)$ bits of information, wich can only be attained with a string of at least 10 bits. The second (independent) piece of information, which bit has been altered, cannot be less than $log_2(10)$. So at least $log_2(1000) + log_2(10) = 13.2877dots$ bits of information must be transmitted. Hence $k > 13.2877dots$, and since it must be an integer, $kgeq 14$.
– mlerma54
Nov 28 at 2:52
If you make this your answer I'll add +1. What is not clear is whether one also needs $log_2(2)$ bits of information to understand whether the information about which bit has been altered has itself been altered! If it's possible to get to $k=14$ then one has to construct the message so as to infer whether to trust the message (the first 10 digits) or the $4$ bits that tell you where the error is...
– Lepidopterist
Nov 28 at 3:01
|
show 1 more comment
up vote
2
down vote
[Ok, I am amending my waaay suboptimal answer (which I gave after misreading the question and used k=30 in a trivial way).]
This is my new solution with k=14 (which in my comments showed cannot be improved) [I see leonbloy already posted a solution with k=14 using Hamming code, mine goes more in the direction previously tried by the OP].
Let ${v_i}_{i=1}^{10}$ the 10 components (0's and 1's) of your binary vector. Let $x$ be
$$
x = 3v_1 + 5v_2 + 6v_3 + 7v_4 + 9v_5 + 10v_6 + 11v_7 + 12v_8 + 13v_9 + 14v_{10}
$$
(note I have omitted coefficients that are exact powers of 2).
Then compute $y = x pmod{16}$, express it as a binary number with 4 bits, and append it to your string. You get a 14-bit binary string, and send it to your friend. Your friend computes $x pmod{16}$ and compares it to $y$ from the string he receives. If the difference is not a power of 2 then it tells him which coefficient is missing in the formula used to compute his $x$, and which bit has been altered in your original vector. If it is a power of 2, then the part altered is $y$, and your original vector has not been modified.
Would that work?
This is not anywhere close to the minimum. Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be $1$-even, in my notation. I think you must be able to do much better. An answer to this should argue what the minimum $k$ is...
– Lepidopterist
Nov 28 at 1:49
Sorry, I read to quick and I missed that your are specifically looking for the minimum k, I apologize. the only thing that comes to my mind is a theoretical lower bound of $kgeq 14$, since you need to pass 10 bits of information and your friend should have some additional information if he is able to determine which bit is the one altered, so that is 4 extra bits. I can think of some ways to solve the problem with less than 22 bits, but my best approach would require 17 bits, so all I can say is $17 geq k geq 14$.
– mlerma54
Nov 28 at 2:24
Your answer would be greatly improved if you could rigorously show why the lower bound is $14$. I can think of a way with $15$, which I'll write above.
– Lepidopterist
Nov 28 at 2:29
2
After recieving your string of 0's and 1's your friend will be able to detemine which of the 1000 numbers you have transmitted, and also which of your binary digits was altered. The first task requires at least $log_2(1000)$ bits of information, wich can only be attained with a string of at least 10 bits. The second (independent) piece of information, which bit has been altered, cannot be less than $log_2(10)$. So at least $log_2(1000) + log_2(10) = 13.2877dots$ bits of information must be transmitted. Hence $k > 13.2877dots$, and since it must be an integer, $kgeq 14$.
– mlerma54
Nov 28 at 2:52
If you make this your answer I'll add +1. What is not clear is whether one also needs $log_2(2)$ bits of information to understand whether the information about which bit has been altered has itself been altered! If it's possible to get to $k=14$ then one has to construct the message so as to infer whether to trust the message (the first 10 digits) or the $4$ bits that tell you where the error is...
– Lepidopterist
Nov 28 at 3:01
|
show 1 more comment
up vote
2
down vote
up vote
2
down vote
[Ok, I am amending my waaay suboptimal answer (which I gave after misreading the question and used k=30 in a trivial way).]
This is my new solution with k=14 (which in my comments showed cannot be improved) [I see leonbloy already posted a solution with k=14 using Hamming code, mine goes more in the direction previously tried by the OP].
Let ${v_i}_{i=1}^{10}$ the 10 components (0's and 1's) of your binary vector. Let $x$ be
$$
x = 3v_1 + 5v_2 + 6v_3 + 7v_4 + 9v_5 + 10v_6 + 11v_7 + 12v_8 + 13v_9 + 14v_{10}
$$
(note I have omitted coefficients that are exact powers of 2).
Then compute $y = x pmod{16}$, express it as a binary number with 4 bits, and append it to your string. You get a 14-bit binary string, and send it to your friend. Your friend computes $x pmod{16}$ and compares it to $y$ from the string he receives. If the difference is not a power of 2 then it tells him which coefficient is missing in the formula used to compute his $x$, and which bit has been altered in your original vector. If it is a power of 2, then the part altered is $y$, and your original vector has not been modified.
Would that work?
[Ok, I am amending my waaay suboptimal answer (which I gave after misreading the question and used k=30 in a trivial way).]
This is my new solution with k=14 (which in my comments showed cannot be improved) [I see leonbloy already posted a solution with k=14 using Hamming code, mine goes more in the direction previously tried by the OP].
Let ${v_i}_{i=1}^{10}$ the 10 components (0's and 1's) of your binary vector. Let $x$ be
$$
x = 3v_1 + 5v_2 + 6v_3 + 7v_4 + 9v_5 + 10v_6 + 11v_7 + 12v_8 + 13v_9 + 14v_{10}
$$
(note I have omitted coefficients that are exact powers of 2).
Then compute $y = x pmod{16}$, express it as a binary number with 4 bits, and append it to your string. You get a 14-bit binary string, and send it to your friend. Your friend computes $x pmod{16}$ and compares it to $y$ from the string he receives. If the difference is not a power of 2 then it tells him which coefficient is missing in the formula used to compute his $x$, and which bit has been altered in your original vector. If it is a power of 2, then the part altered is $y$, and your original vector has not been modified.
Would that work?
edited Nov 28 at 6:09
answered Nov 28 at 1:45
mlerma54
33916
33916
This is not anywhere close to the minimum. Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be $1$-even, in my notation. I think you must be able to do much better. An answer to this should argue what the minimum $k$ is...
– Lepidopterist
Nov 28 at 1:49
Sorry, I read to quick and I missed that your are specifically looking for the minimum k, I apologize. the only thing that comes to my mind is a theoretical lower bound of $kgeq 14$, since you need to pass 10 bits of information and your friend should have some additional information if he is able to determine which bit is the one altered, so that is 4 extra bits. I can think of some ways to solve the problem with less than 22 bits, but my best approach would require 17 bits, so all I can say is $17 geq k geq 14$.
– mlerma54
Nov 28 at 2:24
Your answer would be greatly improved if you could rigorously show why the lower bound is $14$. I can think of a way with $15$, which I'll write above.
– Lepidopterist
Nov 28 at 2:29
2
After recieving your string of 0's and 1's your friend will be able to detemine which of the 1000 numbers you have transmitted, and also which of your binary digits was altered. The first task requires at least $log_2(1000)$ bits of information, wich can only be attained with a string of at least 10 bits. The second (independent) piece of information, which bit has been altered, cannot be less than $log_2(10)$. So at least $log_2(1000) + log_2(10) = 13.2877dots$ bits of information must be transmitted. Hence $k > 13.2877dots$, and since it must be an integer, $kgeq 14$.
– mlerma54
Nov 28 at 2:52
If you make this your answer I'll add +1. What is not clear is whether one also needs $log_2(2)$ bits of information to understand whether the information about which bit has been altered has itself been altered! If it's possible to get to $k=14$ then one has to construct the message so as to infer whether to trust the message (the first 10 digits) or the $4$ bits that tell you where the error is...
– Lepidopterist
Nov 28 at 3:01
|
show 1 more comment
This is not anywhere close to the minimum. Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be $1$-even, in my notation. I think you must be able to do much better. An answer to this should argue what the minimum $k$ is...
– Lepidopterist
Nov 28 at 1:49
Sorry, I read to quick and I missed that your are specifically looking for the minimum k, I apologize. the only thing that comes to my mind is a theoretical lower bound of $kgeq 14$, since you need to pass 10 bits of information and your friend should have some additional information if he is able to determine which bit is the one altered, so that is 4 extra bits. I can think of some ways to solve the problem with less than 22 bits, but my best approach would require 17 bits, so all I can say is $17 geq k geq 14$.
– mlerma54
Nov 28 at 2:24
Your answer would be greatly improved if you could rigorously show why the lower bound is $14$. I can think of a way with $15$, which I'll write above.
– Lepidopterist
Nov 28 at 2:29
2
After recieving your string of 0's and 1's your friend will be able to detemine which of the 1000 numbers you have transmitted, and also which of your binary digits was altered. The first task requires at least $log_2(1000)$ bits of information, wich can only be attained with a string of at least 10 bits. The second (independent) piece of information, which bit has been altered, cannot be less than $log_2(10)$. So at least $log_2(1000) + log_2(10) = 13.2877dots$ bits of information must be transmitted. Hence $k > 13.2877dots$, and since it must be an integer, $kgeq 14$.
– mlerma54
Nov 28 at 2:52
If you make this your answer I'll add +1. What is not clear is whether one also needs $log_2(2)$ bits of information to understand whether the information about which bit has been altered has itself been altered! If it's possible to get to $k=14$ then one has to construct the message so as to infer whether to trust the message (the first 10 digits) or the $4$ bits that tell you where the error is...
– Lepidopterist
Nov 28 at 3:01
This is not anywhere close to the minimum. Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be $1$-even, in my notation. I think you must be able to do much better. An answer to this should argue what the minimum $k$ is...
– Lepidopterist
Nov 28 at 1:49
This is not anywhere close to the minimum. Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be $1$-even, in my notation. I think you must be able to do much better. An answer to this should argue what the minimum $k$ is...
– Lepidopterist
Nov 28 at 1:49
Sorry, I read to quick and I missed that your are specifically looking for the minimum k, I apologize. the only thing that comes to my mind is a theoretical lower bound of $kgeq 14$, since you need to pass 10 bits of information and your friend should have some additional information if he is able to determine which bit is the one altered, so that is 4 extra bits. I can think of some ways to solve the problem with less than 22 bits, but my best approach would require 17 bits, so all I can say is $17 geq k geq 14$.
– mlerma54
Nov 28 at 2:24
Sorry, I read to quick and I missed that your are specifically looking for the minimum k, I apologize. the only thing that comes to my mind is a theoretical lower bound of $kgeq 14$, since you need to pass 10 bits of information and your friend should have some additional information if he is able to determine which bit is the one altered, so that is 4 extra bits. I can think of some ways to solve the problem with less than 22 bits, but my best approach would require 17 bits, so all I can say is $17 geq k geq 14$.
– mlerma54
Nov 28 at 2:24
Your answer would be greatly improved if you could rigorously show why the lower bound is $14$. I can think of a way with $15$, which I'll write above.
– Lepidopterist
Nov 28 at 2:29
Your answer would be greatly improved if you could rigorously show why the lower bound is $14$. I can think of a way with $15$, which I'll write above.
– Lepidopterist
Nov 28 at 2:29
2
2
After recieving your string of 0's and 1's your friend will be able to detemine which of the 1000 numbers you have transmitted, and also which of your binary digits was altered. The first task requires at least $log_2(1000)$ bits of information, wich can only be attained with a string of at least 10 bits. The second (independent) piece of information, which bit has been altered, cannot be less than $log_2(10)$. So at least $log_2(1000) + log_2(10) = 13.2877dots$ bits of information must be transmitted. Hence $k > 13.2877dots$, and since it must be an integer, $kgeq 14$.
– mlerma54
Nov 28 at 2:52
After recieving your string of 0's and 1's your friend will be able to detemine which of the 1000 numbers you have transmitted, and also which of your binary digits was altered. The first task requires at least $log_2(1000)$ bits of information, wich can only be attained with a string of at least 10 bits. The second (independent) piece of information, which bit has been altered, cannot be less than $log_2(10)$. So at least $log_2(1000) + log_2(10) = 13.2877dots$ bits of information must be transmitted. Hence $k > 13.2877dots$, and since it must be an integer, $kgeq 14$.
– mlerma54
Nov 28 at 2:52
If you make this your answer I'll add +1. What is not clear is whether one also needs $log_2(2)$ bits of information to understand whether the information about which bit has been altered has itself been altered! If it's possible to get to $k=14$ then one has to construct the message so as to infer whether to trust the message (the first 10 digits) or the $4$ bits that tell you where the error is...
– Lepidopterist
Nov 28 at 3:01
If you make this your answer I'll add +1. What is not clear is whether one also needs $log_2(2)$ bits of information to understand whether the information about which bit has been altered has itself been altered! If it's possible to get to $k=14$ then one has to construct the message so as to infer whether to trust the message (the first 10 digits) or the $4$ bits that tell you where the error is...
– Lepidopterist
Nov 28 at 3:01
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3016575%2fpassing-a-binary-message-to-a-friend-where-one-of-the-components-is-always-turn%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
There's also an obvious way to get $k = 20$; just duplicate each bit and send that (equivalently, send the string twice).
– platty
Nov 28 at 1:58
The problem with that is that you don't know which number, the first or second, is correct if they don't agree. This is why I wrote that $22$ is an upper bound, because then you can encode them so that you can clearly tell which degenerated.
– Lepidopterist
Nov 28 at 2:14
Not the way you have it written above. If the two numbers differ, it must be in exactly one position -- and it must be the case that this was turned from a 0 into a 1. Otherwise, the two copies are the same and both are the original value.
– platty
Nov 28 at 2:33
Ah, good point! Btw, I think I can get to 15, see new edit.
– Lepidopterist
Nov 28 at 2:37