Hamming code

Binary Hamming codes
The Hamming(7,4)-code (with r = 3)
Named after	Richard W. Hamming
Classification
Type	Linear block code
Block length	2r − 1 where r ≥ 2
Message length	2r − r − 1
Rate	1 − r/(2r − 1)
Distance	3
Alphabet size	2
Notation	[2r − 1, 2r − r − 1, 3]2-code
Properties
perfect code

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

In mathematical terms, Hamming codes are a class of binary linear codes. For each integer r ≥ 2 there is a code with block length n = 2^r − 1 and message length k = 2^r − r − 1. Hence the rate of Hamming codes is R = k / n = 1 − r / (2^r − 1), which is the highest possible for codes with minimum distance of three (i.e., the minimal number of bit changes needed to go from any code word to any other code word is three) and block length 2^r − 1. The parity-check matrix of a Hamming code is constructed by listing all columns of length r that are non-zero, which means that the dual code of the Hamming code is the shortened Hadamard code. The parity-check matrix has the property that any two columns are pairwise linearly independent.

Due to the limited redundancy that Hamming codes add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory (ECC memory), where bit errors are extremely rare and Hamming codes are widely used. In this context, an extended Hamming code having one extra parity bit is often used. Extended Hamming codes achieve a Hamming distance of four, which allows the decoder to distinguish between when at most one one-bit error occurs and when any two-bit errors occur. In this sense, extended Hamming codes are single-error correcting and double-error detecting, abbreviated as SECDED.