Hamming codes

Joshua R. Davis, Carleton College, Math 134, Fall 2024

Introduction

All information in a computer is stored as numbers. For example, you are currently reading text made up of letters. 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 and hence a sequence of numbers. A color is recorded as three numbers, which measure 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 basic idea remains true: Computers store all information as numbers.

Moreover, all numbers in a computer are stored as base-two (binary) numerals, as opposed to the base-ten (decimal) numerals that we commonly use. Writing and reading numerals in base two is not difficult, once you’ve practiced a little. First you must know the powers of two: 1, 2, 4, 8, 16, 32, etc. Any positive integer can be written as a sum of powers of two in a unique way. For example, 11 = 8 + 2 + 1. In base two, this is recorded as 1011, which means “1 times 1, plus 1 times 2, plus 0 times 4, plus 1 times 8”. It’s similar to how, in base ten, 1011 means “1 times 1, plus 1 times ten, plus 0 times a hundred, plus 1 times a thousand”.

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 of logic and arithmetic.

Unfortunately, any one of these contortions may incur 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. The practical importance of these errors varies. If the error occurs in a downloaded image, then it might imperceptibly change one pixel of the image. If the error occurs in a downloaded application, then it might render the entire application utterly unusable.

Various protocols have been devised to automatically detect errors in bit sequences. This tutorial presents two protocols. The first one, called the parity bit, is simple but not very powerful. The second one, called the Hamming code, is much more powerful. It’s also more complicated, but for students of linear algebra the complication is manageable.

Parity bit

The parity bit is one of the simplest error-correction protocols. Suppose that someone named Ariko in Japan wants to send a four-bit message to her friend Babatope in Nigeria. Before sending the four bits, she computes an extra bit called the parity bit. This bit has value 1 if the original four bits add up to an odd number and 0 if the original four bits add up to an even number. So altogether the four original bits and the parity bit add up to an even number. Once she has computed the parity bit, she transmits all five bits. When Babatope receives them, he makes sure that they all add up to an even number. If they don’t, then an error must have occurred. So Babatope asks Ariko to resend her message.

In the example below, Ariko’s original message is 1011. A parity bit is appended to it, and the message 10111 is sent. During transmission, an error of 00100 (meaning, a flip in the third bit) creeps in. So the message 10011 is received. Because its parity is 1 rather than 0, Babatope knows that an error occurred. (Feel free to try your own examples. You can even increase the number of bits in original, if you enlarge error by the same number of bits.)

original = {1, 0, 1, 1}
sent = Append[original, Mod[Total[original], 2]]
error = {0, 0, 1, 0, 0};
received = Mod[sent + error, 2]
parity = Mod[Total[received], 2]

For the later sections, we need to explain what “mod” means in the code above. It refers to modular arithmetic, where we consider only the remainders of division problems. If k is an even number, then k divided by 2 leaves a remainder of 0, so we say that k mod 2 is 0. If k is an odd number, then k mod 2 is 1. And k mod 2 is computed by Mod[k, 2] in Mathematica.

The following questions illustrate the limitations of the parity bit. First, what happens if errors occur on two bits rather than just one bit? Or on three bits, or on four? Second, if we return to the simple case, where only one bit incurs an error, then is there any way for Babatope to know which bit it was, so that he can correct the error himself rather than asking Ariko to resend?

The (7, 4) Hamming code

To use our second error-correction protocol, Ariko and Babatope are going to need the following matrices.

encoder = {
{1, 0, 0, 0}, 
{0, 1, 0, 0}, 
{0, 0, 1 ,0}, 
{0, 0, 0, 1}, 
{0, 1, 1, 1}, 
{1, 0, 1, 1}, 
{1, 1, 0, 1}};
MatrixForm[encoder]
decoder = {
{1, 0, 0, 0, 0, 0, 0}, 
{0, 1, 0, 0, 0, 0, 0}, 
{0, 0, 1, 0, 0, 0, 0}, 
{0, 0, 0, 1, 0, 0, 0}};
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 her four-bit message, Ariko places the four bits in a column and multiplies-mod-2 that column by the encoder matrix. For example, if her original message is 1011, then here it is multiplied  and multiplied-mod-2 by the encoder matrix.

original = {1, 0, 1, 1}
encoder.original
sent = Mod[encoder.original, 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, Ariko sends the seven-bit encoded message to Babatope.

Transmission with no errors

Suppose that no errors occur in transmission. So Babatope’s received message is identical to Ariko’s sent message.

error = {0, 0, 0, 0, 0, 0, 0};
sent + error
received = Mod[sent + error, 2]

Babatope multiplies-mod-2 the checker matrix by the received message. The output of the check is 000, which means that no error occurred.

checker.received
check = Mod[checker.received, 2]

Because no error occurred, Babatope simply multiplies-mod-2 the decoder matrix by the received message, to get the original message back.

decoder.received
Mod[decoder.received, 2]

If you think about it, the decoder matrix is not very impressive. All it does it pick out the first four bits of the code word, which equal the four bits of the original message. The last three bits of the code word are more interesting. Let's see why.

Transmission with one error

Suppose again that Ariko wants to send 1011, but this time an error creeps in on the third bit during transmission. Here’s what Babatope receives.

original
sent
error = {0, 0, 1, 0, 0, 0, 0};
sent + error
received = Mod[sent + error, 2]

As before, Babatope multiplies-mod-2 the checker matrix by the received message. The output of the check is not 000, which means that an error happened. But the error message contains more information than that. The error message is 011, which is binary for 3. It is telling Babatope that an error occurred in the third bit!

checker.received
check = Mod[checker.received, 2]

In other words, Babatope knows what the error above was. To cancel out of the effect of the error, he simply adds it to the received message. Then he decodes as usual, obtaining the correct intended message.

received + error
decoder.(received + error)
Mod[decoder.(received + error), 2]

So the (7, 4) Hamming code not only detects errors on single bits, but also tells Babatope how to correct them automatically. Ariko doesn’t even need to resend her message.

Transmission with two errors

Suppose once again that Ariko wants to send 1011, but this time an error creeps in on the second and seventh bits during transmission. Here’s what Babatope receives.

original
sent
error = {0, 1, 0, 0, 0, 0, 1};
sent + error
received = Mod[sent + error, 2]

Babatope goes through the protocol. He multiplies-mod-2 the checker matrix by the received message. The output of the check is not 000, which means that an error happened.

checker.received
check = Mod[checker.received, 2]

The error message is 101, which is binary for 5. It is telling Babatope that an error occurred in the fifth bit?! To cancel out of the effect of the error, Babatope adds the supposed error to the received message. Then he decodes as usual.

supposed = {0, 0, 0, 0, 1, 0, 0};
decoder.(received + supposed)
Mod[decoder.(received + supposed), 2]

Unfortunately, this was not the intended message. The error-correcting protocol has broken down. Babatope accurately deduced that an error had occurred, but he did not accurately correct the error.

Correct one error or detect two errors, but not both

As the story of Ariko and Babatope illustrates, the (7, 4) Hamming code can correct a single error, and it can detect up to two errors, but it cannot do both tasks at the same time. In fact, if it tries to correct two errors, then it actually causes a third error to happen. So in practice this error-correcting protocol is used in two distinct ways.

1. Suppose that your communication line is pretty reliable, in that it never introduces more than one error into any seven-bit message. And both you and your intended recipient know that. Then your recipient can automatically detect and correct any single error that happens.

2. Suppose that your communication is less reliable than that, but it’s still pretty good, in that it never introduces more than two errors into any seven-bit message. And both you and your intended recipient know that. Then your recipient can automatically detect any one or two errors that happen, but they cannot correct them. When errors are detected, your recipient must ask you to resend your message.

How does this work?

For brevity, let’s call the encoder, decoder, and checker matrices E, D, and C. There are four key points to understand about these matrices.

1. D E = I. Therefore D E w = w for any four-bit word w. In other words, decoding undoes encoding.

2. C E = 0. Therefore C E w = 0 for any four-bit word w. In other words, any error-free encoded word E w will check to 0.

3. The columns of C are just the numbers 1, 2, ..., 7 in base two. For j = 1, 2, ..., 7, let ej be the seven-bit vector with 1 in the jth spot and 0s elsewhere. Then C ej is the number j in base two. Combining this observation with the preceding point, we have 
	C (E w + ej) = C E w + C ej = C ej, 
which equals the number j in base two. This explains why a single error in bit j causes the number j to pop out of the checking process.

4. Each column of E has at least three 1s. Therefore, altering an entry of w causes at least three entries in E w to change. That is, valid code words of the form E w are at least three bit-flips away from each other. This is what lets us correct one error or detect up to two errors, but not correct two errors or detect three errors...

Exercises

A. Working with the (7, 4) Hamming code, give an example where three errors occur in transmission but the error code is 000. This example shows that we have no hope of detecting more than two errors.

B. The (7, 4) Hamming code was expressed using multiplication-mod-2 involving three matrices, which we called encoder, decoder, and checker. Can the (5, 4) parity bit system (which encodes four bits into five, as above) be expressed using multiplication-mod-2 of encoder, decoder, and checker matrices too? If so, then what are these matrices explicitly?

C. This problem isn’t exactly linear algebra, but it’s informative anyway. The (7, 4) Hamming code presented thus far appends three bits to an unencoded word to make an encoded word, right? The next-larger Hamming code should append four bits to an unencoded word to make an encoded word. In other words, it is the (k + 4, k) Hamming code, for some number k. What is k, and what are the encoder, decoder, and checker matrices? Is this Hamming code still able to correct one error or detect two errors (but not both)?