Also known as RM\(^*(r-2,r)\) code.
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
- Perfect binary code
- \(q\)-ary Hamming code
- Binary BCH code — Binary Hamming codes are binary primitive narrow-sense BCH codes [7; Corr. 5.1.5]. Binary Hamming codes can be written in cyclic form [8; Thm. 12.22].
- Universally optimal \(q\)-ary code — Binary Hamming codes and several of their extended, punctured, and shortened versions are LP universally optimal codes [9].
Child
Cousins
- Constantin-Rao (CR) code — The nonlinear CR codes for \(G = \mathbb{Z}_2^r\) reduce to Hamming codes at lengths \(n = 2^r - 1\) [10]; see Ref. [11].
- \([2^r,2^r-r-1,4]\) Extended Hamming code — Extended Hamming codes are extensions of Hamming codes by a parity-check bit. Puncturing extended Hamming codes yields the Hamming codes.
- Reed-Muller (RM) code — Binary Hamming codes are equivalent to RM\(^*(r-2,r)\).
- Nearly perfect code — Shortened Hamming codes \([2^r-2,2^r-r-2,3]\) are nearly perfect ([12], pg. 533).
- Combinatorial design — Weight-three codewords of the \([2^r-1,2^r-r-1, 3]\) Hamming code support the Steiner system \(S(2,3,2^r-1)\) [13; pg. 89].
- Repetition code — The triple repetition code \([3,1,3]\) is the smallest Hamming code.
- \([2^m-1,m,2^{m-1}]\) simplex code — Hamming and simplex codes are dual to each other.
- Preparata code — Preparata codes can be obtained by Hensel-lifting Hamming codes to \(\mathbb{Z}_4\) [14]. The union of the dual a Preparata code and some of its translates forms a Hamming code [12; pg. 475].
- Kerdock code — Kerdock codes can be obtained by Hensel-lifting Hamming codes to \(\mathbb{Z}_4\) [14].
- Majorana stabilizer code — Majorana Hamming codes are codes closely related to the classical Hamming codes [15].
- \([[2^r, 2^r-r-2, 3]]\) Gottesman code — \([[2^r, 2^r-r-2, 3]]\) Gottesman codes are analogues of Hamming codes in that they saturate the asymptotic Hamming bound.
- Coherent-parity-check (CPC) code — Tripartite CPC codes are constructed from Hamming codes via the CPC construction [16; Thm. 4].
- \([[2^r-1, 2^r-2r-1, 3]]\) quantum Hamming code — Quantum Hamming codes result from applying the CSS construction to Hamming codes and their duals the simplex codes.
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]
- Kløve, Torleiv. Error correcting codes for the asymmetric channel. Department of Pure Mathematics, University of Bergen, 1981.
- [11]
- M. Grassl et al., “New Constructions of Codes for Asymmetric Channels via Concatenation”, IEEE Transactions on Information Theory 61, 1879 (2015) arXiv:1310.7536 DOI
- [12]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [13]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [14]
- 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
- [15]
- M. B. Hastings, “Small Majorana Fermion Codes”, (2017) arXiv:1703.00612
- [16]
- 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
- Victor V. Albert (2022-08-12) — most recent
- Victor V. Albert (2022-03-22)
- Dhruv Devulapalli (2021-12-17)
Cite as:
“\([2^r-1,2^r-r-1,3]\) Hamming code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/hamming