\([2^r-1,2^r-r-1,3]\) Hamming code

\([2^r-1,2^r-r-1,3]\) Hamming code[1,2]

Alternative names: 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.

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\) [7]; see Ref. [8].
\([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 ([9], 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)\) [10; 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\) [11]. The union of the dual a Preparata code and some of its translates forms a Hamming code [9; pg. 475].
Kerdock code— Kerdock codes can be obtained by Hensel-lifting Hamming codes to \(\mathbb{Z}_4\) [11].
Batch code— Hamming codes can be used to construct batch codes [12][13; Exam. 10.9].
Majorana stabilizer code— Majorana Hamming codes are codes closely related to the classical Hamming codes [14].
\([[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 [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.
\([[2^r+r, 2^r-r-2, 3]]\) Ring CPC code— The ring CPC code is obtained from the shortened Hamming code via the CPC construction [16].
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.
Subsystem color code— The \([10,6,3]\) shortened Hamming code can be converted into an EAOAQECC [17].

Member of code lists

Primary Hierarchy

Classical Domain

Binary Kingdom

Binary codeECC

Nearly perfect codeECC

Perfect binary codePerfect OA \(t\)-design ECC

Parents

Perfect binary code

\(q\)-ary Hamming codePerfect Linear \(q\)-ary Universally optimal Small-distance block ECC

Primitive narrow-sense BCH codeEvaluation Linear \(q\)-ary AG Cyclic Constacyclic Skew-cyclic ECC

Binary Hamming codes are binary primitive narrow-sense BCH codes [18; Corr. 5.1.5]. Binary Hamming codes can be written in cyclic form [19; Thm. 12.22].

Binary BCH codeLinear \(q\)-ary Cyclic Constacyclic Skew-cyclic ECC

Binary Hamming codes are binary primitive narrow-sense BCH codes [18; Corr. 5.1.5]. Binary Hamming codes can be written in cyclic form [19; Thm. 12.22].

Lexicographic codeECC

Hamming codes are lexicodes [20].

Universally optimal \(q\)-ary codeUniversally optimal ECC

Binary Hamming codes and several of their extended, punctured, and shortened versions are LP universally optimal codes [21].

\([2^r-1,2^r-r-1,3]\) Hamming code

Children

\([7,4,3]\) Hamming code

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]: Kløve, Torleiv. Error correcting codes for the asymmetric channel. Department of Pure Mathematics, University of Bergen, 1981.
[8]: 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
[9]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[10]: J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[11]: 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
[12]: T. Baumbaugh, Y. Diaz, S. Friesenhahn, F. Manganiello, and A. Vetter, “Batch Codes from Hamming and Reed-Müller Codes”, (2017) arXiv:1710.07386
[13]: I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
[14]: M. B. Hastings, “Small Majorana Fermion Codes”, (2017) arXiv:1703.00612
[15]: A. B. Khesin, J. Z. Lu, and P. W. Shor, “Universal graph representation of stabilizer codes”, (2024) arXiv:2411.14448
[16]: 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
[17]: 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
[18]: W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[19]: R. Hill. A First Course In Coding Theory. Oxford University Press, 1988.
[20]: J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
[21]: H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 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

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