Hamming Code

Hamming Code

In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming(7,4)-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of errors. Hamming codes are special in that they are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance 3.

In mathematical terms, Hamming codes are a class of binary linear codes. For each integer there is a code with block length and message length . Hence the rate of Hamming codes is, which is highest possible for codes with distance and block length . The parity-check matrix of a Hamming code is constructed by listing all columns of length that are pairwise linearly independent.

Because of the simplicity of Hamming codes, they are widely used in computer memory (ECC memory). In this context, one often uses an extended Hamming code with one extra parity bit. Extended Hamming codes achieve a distance of, which allows the decoder to distinguish between the situation in which at most one bit error occurred and the situation in which two bit errors occurred. In this sense, extended Hamming codes are single-error correcting and double-error detecting, and often referred to as SECDED.