Encyclopaedia of DesignTheory: A code

Think of a number between 0 and 15. Now answer the following questions. You are allowed to lie at most once.

Is the number 8 or greater? Is it in the set {4,5,6,7,12,13,14,15}? Is it in the set {2,3,6,7,10,11,14,15}? Is it odd? Is it in the set {1,2,4,7,9,10,12,15}? Is it in the set {1,2,5,6,8,11,12,15}? Is it in the set {1,3,4,6,8,10,13,15}?

From your answers, I can decide which (if any) question you lied to, and which number you thought of.

Encode the answers as 1 for "yes", 0 for "no". The correct answers to the first four questions establish the base 2 representation of the number n you thought of, say x = (x₁, x₂, x₃, x₄), where n=8x₁+4x₂+2x₃+x₄. The last three correct answers are linear combinations of these modulo 2. The effect is to produce a binary string y of length 7, obtained by multiplying x by the matrix G given by

1 0 0 0 0 1 1

0 1 0 0 1 0 1

0 0 1 0 1 1 0

0 0 0 1 1 1 1

This is a generator matrix of the code. The code itself consists of the 16 words of the form y=xG consisting of the correct answers to the questions for each of the numbers 0,...,15. That is, it is the row space of G. In particular, it is a linear code: that is, it forms a vector space (over the binary field GF(2)).

Of course, the word that I receive may not be one of these codewords. If you told a lie, then the word I receive will differ in one position from the correct word (that is, one error has occurred).

A parity check matrix of the code is a matrix H whose null space is the code. In this case we can take H to be

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Then yH=0 for any codeword y. So, if the received word z=y+e_i is obtained from y by making an error in the ith position (that is, telling a lie in answering the ith question), then zH=e_iH is the ith row of H, which happens to be the number i written in base 2. If no lie is told, then zH=0.

So calculating zH (the syndrome of z) enables the error to be corrected. This code is the binary Hamming code of length 7.

Exercise: Write out the 16 codewords. Verify that the Hamming distance betweem any two codewords is at least 3.

Table of contents | Glossary | Topics | Bibliography | History

Peter J. Cameron
7 August 2002