Hamming Code

In short, a HammingCode of separation s and length n is a collection of n "words" from an "alphabet" chosen such that every pair of distinct words are at least s apart, according to the HammingDistance.

In slightly more detail ...

Take an alphabet A and consider the set W of all the "words" of length n that can be made from it.

The HammingDistance d(,) between two "words" is the number of places in which they differ.

A HammingCode of distance s is a subset of S of W such that for any two words chosen from S have a HammingDistance of at least s

Examples:

Let A = {0,1} and n=3, so |W|=8. Let S be {000,101,110,011}, a code obtained by prepending the parity to each of {00,01,10,11}. S has separation 2 and single-bit errors in transmission can be detected.

Let A = {0,1} and n=7, so |W|=128. It is possible to find a set S of separation 3 and size 16 in this case. Furthermore, the set S can be chosen such that the bottom four bits of the code words are the binary representation of the numbers 0 to 15. It's like the parity example, but harder, and bigger.

Motivation:

If a word is transmitted and some bits are corrupted, we would like to know and, if possible, be able to recover the original. Given a HammingCode of separation 3 we can always recover from a single-bit error. Given a HammingCode of separation 4 we can always recover from a single-bit error, and detect a double-bit error.

Not a crystal clear explanation, but it can be expanded.