Hamming code[1]

Description

An infinite family of perfect linear codes with parameters \((2^r-1,2^r-r-1, 3)\) for \(r \geq 2\). Their \(r \times (2^r-1) \) parity check matrix \(H\) has all possible non-zero \(r\)-bit strings as its columns.

Protection

Can detect 1-bit and 2-bit errors, and can correct 1-bit errors.

Rate

Asymptotic rate \(k/n = 1-\frac{\log n}{n} \to 1\) and normalized distance \(d/n \to 0\).

Realizations

Commonly used when error rates are very low, for example, computer RAM or integrated circuits [2].

Parent

Cousins

Zoo code information

Internal code ID: hamming

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: hamming

Cite as:
“Hamming code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/hamming
BibTeX:
@incollection{eczoo_hamming, title={Hamming code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/hamming} }
Permanent link:
https://errorcorrectionzoo.org/c/hamming

References

[1]
R. W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal 29, 147 (1950). DOI
[2]
R. Hentschke et al., “Analyzing area and performance penalty of protecting different digital modules with Hamming code and triple modular redundancy”, Proceedings. 15th Symposium on Integrated Circuits and Systems Design. DOI
[3]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977

Cite as:

“Hamming code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/hamming

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/hamming.yml.