Suppose I want to send you a message composed of three-digit binary "words." In three binary digits, you can represent the eight numbers through :For example, I have a "black and white" photo, made up of a rectangle of dots called pixels, each one of which represents a shade of gray, ranging from 0 = pure black through 7 = pure white. If the picture is ( rows by columns), I would have to send you words representing rows, each of pixels.

Now, the problem is, when I send this information, some of the words may get corrupted by interference or static. I may send the word (= ), but you may receive it as (= ) because of this transmission error. If this happens fairly frequently the image may get too distorted to be usable. What to do?

One possibility is to waste time and energy by resending the entire message, but there is no guarantee that similar serious data losses won't take place in that transmission. A solution that computer scientists have used for decades is to send more data, but in such a way that the receiver can detect errors and automatically compensate for them. This is called an error-correcting code, and I'll explain how one of them works.

The first thing to note is that, for any power of , , it is possible to find a list of binary words of length such that any two of them differ in exactly binary places. Here are some examples:(These lists of words are actually arrays of s and s called Hadamard matrices ). If you look at the list of eight words, you can see that words and , for example, differ in exactly places:

We can define the "distance" --- actually the "Hamming distance" --- between any two binary words to be the number of places in which they differ. Thus, any two words in the list above have distance from each other, since they always differ in exactly 4 binary places.

Ok, suppose I want to send the gray pixel represented by the bits (). Instead of sending just the bits , I send instead the entire row of the Hadamard matrix . That is, I send the bits . Unfortunately, because of interference, you receive the bits . Compare:The Hamming distance between the correct word and the one you received is , since these differ in only the single bit shown. Furthermore, since pairs of rows or words in have distance , the received word must be closer to than it is to any of the other rows. Thus, when you receive the word, if there is only one bit in error, you can simply find the row the received word is closest to and that will be the word that was sent.

In general, then, here's how it works. If we agree to communicate using words of binary digits, then we each set up the square Hadamard matrix of length (and width) . The rows will differ from each other in exactly binary places. Thus, each of the rows will have distance from any other row. To send the binary word of length , I send instead the row of numbered by that binary word. When you receive this word, you look in your copy of and find the row which has smallest distance from the received word. The number of that row (in binary) will then be the word I originally sent, providing there are fewer than errors.

(If I am sending bit words (so , ), for example, then we use the matrix , whose rows have Hamming distance from each other. If I want to send the number , then I send the nd row of , which happens to be . If there were fewer than errors, then whatever you receive will be closer to row than to any other row of , so that's what you assume I sent (and you'll be correct).

In real life, such coding is used, among other things, to communicate images from space probes. Once the digital image is saved in the probe, the encoding and decoding using the Hadamard matrix is done at high speed by computers in the craft and on the ground. Occasionally there will be more errors than permissible, so that pixel may be received incorrectly. Most of the time, or for most of the pixels, things work fine; the bad pixels are simply averaged or otherwise processed out.