Hamming code[1,2] 

Description

Member of 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. Adding a parity check yields the \([2^r,2^r-r-1, 4]\) extended Hamming code.

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 [3].Hamming-code based matrix embedding used in steganography [4,5].

Notes

See Kaiserslautern database [6] for explicit codes.

Parents

Child

Cousins

References

[1]
R. W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal 29, 147 (1950) DOI
[2]
M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) 657.
[3]
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
[4]
Crandall, Ron. "Some notes on steganography." Posted on steganography mailing list 1998 (1998): 1-6.
[5]
A. Westfeld, “F5—A Steganographic Algorithm”, Information Hiding 289 (2001) DOI
[6]
Michael Helmling, Stefan Scholl, Florian Gensheimer, Tobias Dietz, Kira Kraft, Stefan Ruzika, and Norbert Wehn. Database of Channel Codes and ML Simulation Results. URL, 2022.
[7]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[8]
R. Hill. A First Course In Coding Theory. Oxford University Press, 1988.
[9]
H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[10]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[11]
10.1007/978-1-4757-6568-7
[12]
A. R. Hammons et al., “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
[13]
N. Chancellor et al., “Graphical structures for design and verification of quantum error correction”, Quantum Science and Technology 8, 045028 (2023) arXiv:1611.08012 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

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} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/hamming

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/edit/main/codes/classical/bits/easy/hamming/hamming.yml.