8.4 Binary codes: hamming codes for channel coding

The idea behind Hamming codes is to intersperse, or append, extra binary digits to a binary code so that errors in transmission of the code over a channel may be detected and corrected. For example, suppose we transmit the code 01101001, and it is received as 01001001. In this transmission, the third most significant bit is received erroneously. Let's define the following “modulo-2 addition” of binary numbers:

Multiplication in modulo-2 arithmetic is simply $0·0=0·1=1·0=0$ and 1 $·1=1$ . Then we can say that the error sequence 00100000 is “added” to the transmission 01101001 to produce the erroneous reception:

Hamming error correcting codes will permit us to receive the erroneous transmission and to detect and correct the error. This is obviously of greatvalue in transmitting and storing information. (Imagine how upset you would be to have the binary code for your checking account confused with that ofMrs. Joan Kroc.)

Choosing the Number of Check Bits. Let's suppose we have $N$ bits of information that we wish to transmit and that we wish to intersperse “check bits” that will enable us to detect and correct any single bit error in the transmission. If we use $N$ information bits and $n$ check bits, then we will transmit a code word containing $N+n$ bits. The $n$ check bits can code $2^n$ events, and we want these events to indicate whether or not any errors occurred and, if so, where they occurred. Therefore we require

where $(N+n)$ is the number of single error events that can occur and +1 is the number of no-error events. For example, when $N=4$ , we require $n=3$ so that $2^3\ge (4+3)+1$ .

How many check bits do you require to code seven bits of information for single error correction?

Code Construction. Let's suppose we have constructed an $(N,n)$ Hamming code consisting of $N$ information bits and $n$ check bits (or parity bits). We denote the information bits by $x_1,x_2,...,x_N$ and the check bits by $c_1,c_2,...,c_n$ . These bits may be interspersed. When $N=4$ and $n=3$ , then a typical array of bits within a code word would be one of the following:

The first ordering is “natural” (as we will see), and the second is “systematic” (a term that is used to describe any code whose head is information and whose tail is check). If a single error occurs in an $(N,n)$ code, then the received code word will be the modulo-2 sum of the code word and the error word that contains a 1 in its $i^{th}$ position:

We would like to operate on this received code word in such a way that the location of the error bit can be determined. If there were no code word, then an obvious solution would be to premultiply the error word by the parity check matrix