WDS : << The questioners asked about J=4 and J=6 and a single-error-correcting Hamming code should do the job. >> I cannot understand how this idea is supposed to work. Suppose we have 16 coins, heads = 1, tails = 0, numbered 0..15, and the prisoners agree coins 0..6 to communicate the Hamming(7, 4) code as shown at http://en.wikipedia.org/wiki/Hamming%287,4%29 The warder selects coin 0 , then turns all coins heads. How is prisoner A to convert this 1111111 to a message (correctable to) 0000000, using only a single turn? WFL On 4/15/15, Warren D Smith <warren.wds@gmail.com> wrote:
If there is a binary error correcting code on N=2^J bits such that (1) exactly N cosets of it constitute the whole set of 2^N possible bitstrings (2) any N-bit word is distance <=1 away from a codeword then you can solve the problem by changing a bit to move it into coset X, thus communicating the value of X to the other prisoner.
The questioners asked about J=4 and J=6 and a single-error-correcting Hamming code should do the job. Actually I do better. If N= 2^J - 1 (for example N=127, J=7), then Hamming codes have cardinality=2^(N-J-1) hence we can by my method provide J+1 bits of information to the other prisoner by flipping only at most one coin. But only J bits of info [in fact only log2(2^J - 1) bits] actually are needed.
Is there an actual use for this (not just in a silly puzzle)?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun