This is a wellknown trick but I’m posting it here since I often have a hard time tracking it down when I need it for an introductory coding theory talk or something. Hopefully someone else will find it amusing too!
Let and let be the set of all vectors in the third column below (for simplicity, we omit commas and parentheses, so is written instead of , for example).
The [7,4,3] Hamming code
decimal 
binary 
Hamming [7,4] 
0 
0000 
0000000 
1 
0001 
0001110 
2 
0010 
0010101 
3 
0011 
0011011 
4 
0100 
0100011 
5 
0101 
0101101 
6 
0110 
0110110 
7 
0111 
0111000 
8 
1000 
1000111 
9 
1001 
1001001 
10 
1010 
1010010 
11 
1011 
1011100 
12 
1100 
1100100 
13 
1101 
1101010 
14 
1110 
1110001 
15 
1111 
1111111 
This is a linear code of length 7, dimension 4, and minimum distance 3. It is called the Hamming [7,4,3]code.
In fact, there is a mapping from to given by , where
. Moreover, the matrix is a generator matrix.
Now, suppose a codeword is sent over a noisy channel and denote the received word by . We assume at most 1 error was made.

Put in the region of the Venn diagram above associated to coordinate in the table below, .

Do parity checks on each of the circles , , and .
Decoding table
parity failure region(s) 
error position 
none 
none 
A, B, and C 
1 
B and C 
2 
A and C 
3 
A and B 
4 
A 
5 
B 
6 
C 
7 
Exercise: Decode in the binary Hamming code using this algorithm.
(This is solved at the bottom of this column.)
In his 1976 autobiography Adventures of a Mathematician, Stanislaw Ulam [U] poses the following problem:
Someone thinks of a number between one and one million (which is just less than 220). Another person is allowed to ask up to twenty questions, to which the first person is supposed to answer only yes or no. Obviously, the number can be guessed by asking first: Is the number in the first halfmillion? and then again reduce the reservoir of numbers in the next question by onehalf, and so on. Finally, the number is obtained in less than log2(1000000). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer?
We define Ulam’s Problem as follows: Fix integers and . Let Player 1 choose the number from the set of integers and Player 2 ask the yes/no questions to deduce the number, to which Player 1 is allowed to lie at most e times. Player 2 must discern which number Player 1 picked with a minimum number of questions with no feedback (in other words, all the questions must be provided at once)
As far as I know, the solution to this version of Ulam’s problem without feedback is still unsolved if e=2. In the case e=1, see [N] and [M]. (Also, [H] is a good survey.)
Player 1 has to convert his number to binary and encode it as a Hamming [7,4,3] codeword. A table containing all 16 codewords is included above for reference. Player 2 then asks seven questions of the form, “Is the ith bit of your 7tuple a 1?” Player 1’s answers form the new 7tuple, , and each coordinate is placed in the corresponding region of the circle. If Player 1 was completely truthful, then the codeword’s parity conditions hold. This means that the 7tuple generated by Player 2’s questions will match a 7tuple from the codeword table above. At this point, Player 2 just has to decode his 7tuple into an integer using the codeword table above to win the game. A single lie, however, will yield a 7tuple unlike any in the codeword table. If this is the case, Player 2 must errorcheck the received codeword using the three parity check bits and the decoding table above. In other words, once Player 2 determines the position of the erroneous bit, he corrects it by “flipping its bit”. Decoding the corrected codeword will yield Player 1’s original number.
References
[H] R. Hill, “Searching with lies,” in Surveys in Combinatorics, ed. by P. Rowlinson, London Math Soc, Lecture Notes Series # 218.
[M] J. Montague, “A Solution to Ulam’s Problem with Errorcorrecting Codes”
[N] I. Niven, “Coding theory applied to a problem of Ulam,” Math Mag 61(1988)275281.
[U] S. Ulam, Adventures of a mathematician, Scribner and Sons, New York, 1976 .
Solution to exercise using SAGE:
sage: MS = MatrixSpace(GF(2), 4, 7)
sage: G = MS([[1,0,0,0,1,1,1],[0,1,0,0,0,1,1],[0,0,1,0,1,0,1],[0,0,0,1,1,1,0]])
sage: C = LinearCode(G)
sage: V = VectorSpace(GF(2), 7)
sage: w = V([0,1,0,0,0,0,1])
sage: C.decode(w)
(0, 1, 0, 0, 0, 1, 1)
In other words, Player picked 4 and lied on the 6th question.
Here is a Sage subtlety:
sage: C = HammingCode(3, GF(2))
sage: C
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: V = VectorSpace(GF(2), 7)
sage: w = V([0,1,0,0,0,0,1])
sage: C.decode(w)
(1, 1, 0, 0, 0, 0, 1)
Why is this decoded word different? Because the Sage Hamming code is distinct (though “equivalent” to) the Hamming code we used in the example above.
Unfortunately, SAGE does not yet do code isomorphisms (at least not as easily as GUAVA), so we use GUAVA’s CodeIsomorphism
function, which calls J. Leon’s GPL’s desauto
C code function:
gap> C1 := GeneratorMatCode([[1,0,0,1,0,1,0],[0,1,0,1,0,1,1],[0,0,1,1,0,0,1],[0,0,0,0,1,1,1]],GF(2));
a linear [7,4,1..3]1 code defined by generator matrix over GF(2)
gap> C2 := GeneratorMatCode([[1,0,0,0,1,1,1],[0,1,0,0,0,1,1],[0,0,1,0,1,0,1],[0,0,0,1,1,1,0]],GF(2));
a linear [7,4,1..3]1 code defined by generator matrix over GF(2)
gap> CodeIsomorphism(C1,C2);
(2,6,7,3)
gap> Display(GeneratorMat(C1));
1 . . 1 . 1 .
. 1 . 1 . 1 1
. . 1 1 . . 1
. . . . 1 1 1
gap> Display(GeneratorMat(C2));
1 . . . 1 1 1
. 1 . . . 1 1
. . 1 . 1 . 1
. . . 1 1 1 .
Now we see that the permutation (2,6,7,3) sends the “SAGE Hamming code” to the “circle Hamming code”:
sage: H = HammingCode(3, GF(2))
sage: G = MS([[1,0,0,0,1,1,1],[0,1,0,0,0,1,1],[0,0,1,0,1,0,1],[0,0,0,1,1,1,0]])
sage: C = LinearCode(G)
sage: C.gen_mat()
[1 0 0 0 1 1 1]
[0 1 0 0 0 1 1]
[0 0 1 0 1 0 1]
[0 0 0 1 1 1 0]
sage: S7 = SymmetricGroup(7)
sage: g = S7([(2,6,7,3)])
sage: H.permuted_code(g) == C
True
You must be logged in to post a comment.