Unruled Notebook

This is a guest post by Anandaswarup Gadde on simple idea in coding theory. I have made minor editing with the original version. Read on…Arunn

Coding Theory Part 1 by Anandaswarup Gadde

A simple technique in reliable communication is repetition.

Some (for example Claude Levi-Strauss) say that one of the roles of mythology is to pass on the values of one age to another and this is done through various myths which may seem different but often carry the same message. A similar idea occurs in coding theory initiated by Richard Hamming of Bell Labs in the late 40′s. Due to patent problems, his paper appeared in 1950, but the famous Hamming matrix appeared already in the paper of Claude Shannon: “A mathematical theory of communication,” Bell. Syst. Tech. J. (1948) [pdf].

The codes invented by Hamming are single error correcting linear codes and the original ideas are very simple. One of the easiest ways to communicate is by a switch by which we can communicate ‘yes’ (1) or ‘no’ (0). So, we can hope to send strings of 1′s and 0′s by simple communication devices. Each string will represent say some word.

For instance, if we want a vocabulary of 16 words, we need strings of length 4 and if we want a vocabulary of 512 words, we need strings of (0′s and 1′s) of length 9.

If there is an error in the transmission, how do we correct it?

Suppose that we start with the simplest case; strings of length one, thus just two words. If we just transmit one symbol and there is a mistake, there is no hope of correcting it. So we replace the message word 1 by code word 111 and 0 by 000 (triple repetition). If we want to send the signal 1, we send the word 111. Suppose that there is one error in transmission. Instead of 111, we may receive 011 or 101 or 110. However, this is still closer to 111 than to 000 in the sense any one of 011,101,110 differs from 111 in only one place where as they differ from 000 in two places. So we conclude that the code word sent was likely to be 111 and then conclude that the message word was most likely 1.

This is called the triple repetition code and gives rise to the notion of Hamming distance.

The Hamming distance between two strings of the same length is the number of places they differ in. The minimum of the distances between the code words is called the minimum distance of the code. In the above example, we have two code words of length three (111,000) and thus the minimum distance of the code is 3. If we make only one error or no error, then the message we receive is closer (of distance less than or equal to one) from the true message than the wrong message (from which the distance must be at least two).

In general, if the minimum distance is 2d+1 and if we make less than d errors, we can guess the right code word.

For Hamming codes (which we next describe), the minimum distance is three and thus we can only detect and correct single errors. However, if we want to use triple code with larger vocabulary, say strings of four symbols, we have to send strings of 12 symbols.

Richard Hamming found a way of manufacturing just 3 more symbols so that it is enough to send strings of 7 symbols (it gets better; for strings of 11 symbols it is enough to send strings of 15 symbols). We shall see how this idea works in our next post.

Tags: claude shannon, coding theory, cryptology, Hamming distance, Hamming matrix, richard hamming