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

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

Description

Second-smallest member of the Hamming code family.

Its generator matrix is \begin{align} \left(\begin{array}{ccccccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right)~. \tag*{(1)}\end{align} Up to equivalence, this is the only nontrivial length-seven perfect binary code containing the zero vector. The automorphism group of the code is \(GL_{3}(\mathbb{F}_{2})\), the second-smallest simple group.

The Hamming code can be extended by a parity-check bit to yield the \([8,4,4]\) extended Hamming code, the smallest doubly even self-dual code. It can be shortened to yield the \([6,3,3]\) shortened Hamming code. The \([7,3,4]\) simplex code is the dual of the Hamming code and also its even-weight subcode [4,5].

Protection

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

Cousins

Incidence-matrix projective code— The \([7,4,3]\) Hamming code parity-check matrix corresponds to points in the Fano plane \(PG_2(2)\) [6; Exam. 21.4.2].
\([8,4,4]\) extended Hamming code— The Hamming code can be extended by a parity-check bit to yield the \([8,4,4]\) extended Hamming code, the smallest doubly even self-dual code.
Dual linear code— The \([7,3,4]\) simplex code is the dual of the Hamming code and also its even-weight subcode [4,5].
\([[7,1,3]]\) Steane code— The Steane code is constructed from the \([7,4,3]\) classical Hamming code via the CSS construction.
Griesmer code— Starting with the \([6,3,3]\) shortened Hamming code and applying the \((u|u+v)\) construction recursively using the repetition code yields a family of \([2^m,m+1,2^{m-1}]\) codes for \(m\geq1\) that saturate the Griesmer bound [7; pg. 90].
\(E_7\) root lattice— The \([7,4,3]\) Hamming code yields the \(E_7^{\perp}\) root lattice via Construction A [8].
Combinatorial design— Weight-three and weight-four codewords of the \([7,4,3]\) Hamming code support combinatorial \(2\)-\((7,3,1)\) and \(2\)-\((7,4,2)\) designs, respectively [9; Exam. 5.2.5].
\([7,3,4]\) simplex code— The \([7,3,4]\) simplex code is the dual of the Hamming code and also its even-weight subcode [4,5].
\((u|u+v)\)-construction code— Starting with the \([6,3,3]\) shortened Hamming code and applying the \((u|u+v)\) construction recursively using the repetition code yields a family of \([2^m,m+1,2^{m-1}]\) codes for \(m\geq1\) that saturate the Griesmer bound [7; pg. 90].
Octacode— The octacode can be obtained by Hensel-lifting the \([7,4,3]\) Hamming code to \(\mathbb{Z}_4\) [10].

Member of code lists

Primary Hierarchy

Classical Domain

Binary Kingdom

Binary codeECC

Nearly perfect codeECC

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

\([2^r-1,2^r-r-1,3]\) Hamming codeCyclic Linear code over \(\mathbb{Z}_q\) Evaluation Linear \(q\)-ary AG Perfect Constacyclic Skew-cyclic Universally optimal Small-distance block ECC

Parents

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

Binary quadratic-residue (QR) codeQR Linear \(q\)-ary Linear code over \(\mathbb{Z}_q\) Cyclic Constacyclic Skew-cyclic ECC

The \([7,4,3]\) Hamming code is a quadratic-residue code with generator polynomial \(1+x+x^3\) [11].

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

References

[1]: C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948) DOI
[2]: R. W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal 29, 147 (1950) DOI
[3]: M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) 657.
[4]: W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
[5]: C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
[6]: C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[7]: J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[8]: J. H. Conway and N. J. A. Sloane, “On the Voronoi Regions of Certain Lattices”, SIAM Journal on Algebraic Discrete Methods 5, 294 (1984) DOI
[9]: V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[10]: 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
[11]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.

Page edit log

Victor V. Albert (2022-12-21) — most recent

Cite as:

“\([7,4,3]\) Hamming code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/hamming743

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