The (7, 4) Hamming Code

Background

All information in a computer is stored as numbers. For example, a single letter is recorded as a number, according to some arbitrary but standardized system (such as A = 65, B = 66, etc. in the ASCII standard). A block of text is a sequence of letters, hence a sequence of numbers. A color is recorded as three numbers, indicating how much red, green, and blue light make up the color. An image is a grid of colors, and a video is a sequence of images, so these are ultimately numbers too. Audio is recorded as numbers sampled from a sound wave. I'm oversimplifying a bit here, but the key idea remains true: Computers store all information as numbers.

All numbers in a computer are stored in base 2 (binary), as opposed to the base-10 (decimal) numbers that we commonly use. Writing and reading numbers in base 2 is not difficult, once you've practiced a little. First you must know the powers of 2: 1, 2, 4, 8, 16, 32, etc. Any positive integer can be written as a sum of powers of 2 in a unique way. For example, 11 = 8 + 2 + 1. In base 2 this is recorded as 1011, which means "1 times 1, plus 1 times 2, plus 0 times 4, plus 1 times 8".

Since all computer information is stored as numbers, and all numbers are stored as sequences of binary digits (bits), all computer information is stored as sequences of bits. Computers work their magic by putting these sequences of bits through extremely complicated contortions. Unfortunately, any one of these contortions may suffer a hardware error, in which one or more of the bits is accidentally flipped from 0 to 1 or from 1 to 0. Errors are especially common on communications networks --- like those that underlie the Internet --- where noise on the network can disrupt a bit-sequence as it is transmitted from one computer to another.

Various procedures have been devised to automatically detect errors in bit-sequences. One example is the parity bit. Suppose that you want to send a four-bit message from your computer to your friend's computer in Texas. Before sending the four bits, you compute an extra bit called the parity bit. This bit is 1 if the original four bits add up to an odd number, and 0 if they add up to an even number. So altogether the four original bits and the parity bit add up to an even number. Once you've computed the parity bit, you transmit all five bits. When your friend receives them, she makes sure that they all add up to an even number. If they don't, then an error must have occurred.

This system is elegant but rather limited. First, it can detect whether a single bit was flipped, but it cannot determine which bit that was, and hence it cannot correct the error; the receiver must ask the sender to resend the data. Second, if two bits are flipped then the parity is unchanged, so the parity check fails to detect that the received data is wrong.

The Hamming code (invented by Richard W. Hamming in 1950) is much more capable. It can detect up to two errors, or it can automatically correct a single error. Codes like this are continually detecting and correcting errors, behind the scenes, whenever you use any kind of digital media: computer, telephone, cable or satellite television, CD or DVD, etc.

Before we describe the Hamming code, we need to talk a little about arithmetic modulo 2. This is a different system of arithmetic from the one you've been using all your life, but it's not difficult. To add two numbers modulo 2, you just add them as normal, then divide the answer by 2 and keep only the remainder. For example, 

    0 + 0 = 0,
    0 + 1 = 1,
    1 + 0 = 1, but
    1 + 1 = 2 = 0.

Similarly, to multiply two numbers modulo 2, you multiply them as usual, divide by 2, and keep only the remainder. Arithmetic modulo 2 may seem a strange operation, but it's highly useful in computer science. It works well with linear algebra, too; everything we've done using real scalars can be done instead using integers-modulo-2 as scalars. In particular, if we have two matrices, then we can multiply them modulo 2 by multiplying them in the usual way and then replacing each entry by its remainder upon divison by 2.

Transmission With No Errors

For simplicity, assume again that you want to transmit four bits. You and your friend are going to need the following matrices.

encoder = {{1, 1, 0, 1}, {1, 0, 1, 1}, {1, 0, 0 ,0}, {0, 1, 1, 1}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
MatrixForm[encoder]
decoder = {{0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 1}};
MatrixForm[decoder]
checker = {{0, 0, 0, 1, 1, 1, 1}, {0, 1, 1, 0, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 1}};
MatrixForm[checker]

To encode your four-bit message, you place the four bits in a column and multiply-modulo-2 by the encoder matrix. For example, the following commands encode the message (1, 1, 0, 1). (We're using the Mathematica command Mod[..., 2] to reduce modulo 2.)

myMessage = {1, 1, 0, 1}
myEncodedMessage = Mod[encoder.myMessage, 2]

The result is a seven-bit chunk of data. This system of error correction is called the (7, 4) Hamming code, because it encodes four bits into seven. Anyway, you send this seven-bit sequence to your friend in Texas. She first checks the message with the checker matrix:

Mod[checker.myEncodedMessage, 2]

The vector of 0s indicates that no error has occurred. (Things are more interesting when an error occurs; we'll talk about that in a moment.) Since there is no error, she simply multiplies the message by the decoder matrix to recover the original four-bit message:

Mod[decoder.myEncodedMessage, 2]

The decoder matrix is not very impressive; all it does it pick out the third, fifth, sixth, and seventh bits, which equal the four bits of the original message. The first, second, and fourth bits of the seven-bit message are more interesting. Let's see why.

Transmission With One Error

Suppose again that you want to transmit the message (1, 1, 0, 1).

myMessage = {1, 1, 0, 1}
myEncodedMessage = Mod[encoder.myMessage, 2]

This time, however, the fifth bit is accidentally flipped during transmission:

myEncodedMessage[[5]] = 1 - myEncodedMessage[[5]];
myEncodedMessage

Your friend in Texas receives this chunk of data. If she were now to multiply by the decoder matrix, then she would obtain the wrong four-bit message:

Mod[decoder.myEncodedMessage, 2]

But your friend knows how to use the Hamming code. Before trying to decode, she checks the encoded message using the checker matrix:

Mod[checker.myEncodedMessage, 2]

The result is 101, which is 5 in binary. This indicates an error in the fifth bit! So she flips that bit:

myEncodedMessage[[5]] = 1 - myEncodedMessage[[5]];
myEncodedMessage

Then she multiplies by the decoder matrix and obtains the correct four-bit message.

Mod[decoder.myEncodedMessage, 2]

In this example, nothing was special about the fifth bit. A single error occuring in any of the seven bits (including the three parity bits) is detected by the checker matrix.

Transmission With Two Errors

Suppose again that you want to transmit the message (1, 1, 0, 1).

myMessage = {1, 1, 0, 1}
myEncodedMessage = Mod[encoder.myMessage, 2]

This time, the first and fifth bits are both accidentally flipped during transmission:

myEncodedMessage[[1]] = 1 - myEncodedMessage[[1]];
myEncodedMessage[[5]] = 1 - myEncodedMessage[[5]];
myEncodedMessage

Your friend in Texas receives this bit-sequence. She checks the encoded message using the checker matrix:

Mod[checker.myEncodedMessage, 2]

100 is 4 in binary. This suggests that the fourth bit was flipped --- but that's not what happened. What's going on? Did our error-detection system fail? No, the error-detection system is working as designed; we are just expecting too much of it.

Single Error Correction OR Double Error Detection

When the checking step returns an error code of 4, that code could have two meanings: that an error occurred in bit 4, or that multiple errors occurred somewhere in the message. The Hamming code cannot distinguish between these two failure modes. So what can the Hamming code do? Here are two precise answers.

Assume that your communication line is pretty good, in that it never introduces more than one error into a seven-bit message. When the receiver receives your seven-bit message, she multiplies the checker matrix by it. If the zero-vector results, then there was no error. If a nonzero vector results, then interpret it is a binary number, flip the indicated bit, and then multiply by the decoder matrix to retriever the original four-bit message.

Assume that your communication line is less good, but that it still never produces more than two errors into a seven-bit message. When the receiver receives your seven-bit message, she multiplies the checker matrix by it. If the zero-vector results, then there was no error. If a nonzero vector results, then one or two errors have occurred; she should then ask you to resend the message.

In short, the Hamming code can be used to correct one error or detect two errors, but it cannot be used for both purposes at the same time. And it certainly cannot be used to detect three errors, as the following example illustrates.

myMessage = {1, 1, 0, 1}
myEncodedMessage = Mod[encoder.myMessage, 2]
myEncodedMessage[[1]] = 1 - myEncodedMessage[[1]];
myEncodedMessage[[4]] = 1 - myEncodedMessage[[4]];
myEncodedMessage[[5]] = 1 - myEncodedMessage[[5]];
myEncodedMessage
Mod[checker.myEncodedMessage, 2]

The checker matrix produces the vector (0, 0, 0), indicating no error even though three errors have occurred.

How Does This Work?

It is easy to verify for any four-bit message (x, y, z, w) that the product of the checker matrix, the encoder matrix, and the four-bit message is 0 modulo 2. Simply multiply them out, and notice that every term is divisible by 2. This shows that the output of the checker matrix is (0, 0, 0) when no error has occurred.

Clear[x, y, z, w]
checker.encoder.{x, y, z, w}

In other words, the kernel of the checker matrix contains the image of the encoder matrix. The checker matrix clearly has rank 3, hence nullity 4; its kernel is 4-dimensional. The encoder matrix clearly has rank 4; its image is 4-dimensional. Since the kernel contains the image and they have the same dimension, it follows that the kernel equals the image. This is crucial, for the Hamming code to work.

Suppose now that a single error occurs in bit j. Then the transmitted message is not the product of encoder and (x, y, z, w), but rather this product plus the standard basis vector e_j. Then the output of the checker matrix is

    checker.(encoder.(x, y, z, w) + e_j) = checker.encoder.(x, y, z, w) + checker.e_j = checker.e_j.

But checker.e_j is the jth column of the checker matrix. If you look at that matrix, you'll see that it is constructed exactly so that its jth column is the number j in binary. So that's how we correct single errors.

The ability to detect double errors is more subtle. It amounts to this fact: Any two vectors in the image of the encoder matrix differ by at least three bit flips. We will not prove this, but you should inspect the encoder matrix to convince yourself. Therefore if two errors occur on an encoded message, we get a vector that cannot possibly be an encoded message.