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
- Primitive narrow-sense 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].
- 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].
- Lexicographic code — Hamming codes are lexicodes [9].
- Universally optimal \(q\)-ary code — Binary Hamming codes and several of their extended, punctured, and shortened versions are LP universally optimal codes [10].
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\) [11]; see Ref. [12].
- \([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 ([13], 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)\) [14; 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\) [15]. The union of the dual a Preparata code and some of its translates forms a Hamming code [13; pg. 475].
- Kerdock code — Kerdock codes can be obtained by Hensel-lifting Hamming codes to \(\mathbb{Z}_4\) [15].
- Batch code — Hamming codes can be used to construct batch codes [16][17; Exam. 10.9].
- Majorana stabilizer code — Majorana Hamming codes are codes closely related to the classical Hamming codes [18].
- \([[m 2^m / (m+1), 2^m / (m+1)]]\) Khesin-Lu-Shor code — The encoder-respecting form of the \([[m 2^m / (m+1), 2^m / (m+1)]]\) Khesin-Lu-Shor code is the graph of a hypercube in \(m = 2^r - 1\) dimensions, and input nodes in the graph are codewords of the \([2^r-1,2^r-r-1,3]\) Hamming code [19].
- \([[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 [20; 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.
- Subsystem color code — The \([10,6,3]\) shortened Hamming code can be converted into an EAOAQECC [21].
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, F. Marques, F. Lima, L. Carro, A. Susin, and R. Reis, “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 95 DOI
- [4]
- Crandall, Ron. "Some notes on steganography." Posted on steganography mailing list 1998 (1998): 1-6.
- [5]
- A. Westfeld, “F5—A Steganographic Algorithm”, Lecture Notes in Computer Science 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]
- J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
- [10]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
- [11]
- Kløve, Torleiv. Error correcting codes for the asymmetric channel. Department of Pure Mathematics, University of Bergen, 1981.
- [12]
- M. Grassl, P. W. Shor, G. Smith, J. Smolin, and B. Zeng, “New Constructions of Codes for Asymmetric Channels via Concatenation”, IEEE Transactions on Information Theory 61, 1879 (2015) arXiv:1310.7536 DOI
- [13]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [14]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [15]
- A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Sole, “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
- [16]
- T. Baumbaugh, Y. Diaz, S. Friesenhahn, F. Manganiello, and A. Vetter, “Batch Codes from Hamming and Reed-Müller Codes”, (2017) arXiv:1710.07386
- [17]
- I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
- [18]
- M. B. Hastings, “Small Majorana Fermion Codes”, (2017) arXiv:1703.00612
- [19]
- J. Z. Lu, A. B. Khesin, and P. W. Shor, “Universal graph representation of stabilizer codes”, (2024) arXiv:2411.14448
- [20]
- N. Chancellor, A. Kissinger, S. Zohren, J. Roffe, and D. Horsman, “Graphical structures for design and verification of quantum error correction”, Quantum Science and Technology 8, 045028 (2023) arXiv:1611.08012 DOI
- [21]
- P. J. Nadkarni, S. Adonsou, G. Dauphinais, D. W. Kribs, and M. Vasmer, “Unified and Generalized Approach to Entanglement-Assisted Quantum Error Correction”, (2024) arXiv:2411.14389
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