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

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

Description

Member of an infinite family of binary linear codes with parameters \([2^r,2^r-r-1, 4]\) for \(r \geq 2\) that are extensions of the Hamming codes by a parity-check bit.

Cousins

Universally optimal \(q\)-ary code— Several extended Hamming codes are LP universally optimal codes [4].
\([2^m,m+1,2^{m-1}]\) First-order RM code— Extended Hamming and first-order RM codes are dual to each other.
Dual linear code— Extended Hamming and first-order RM codes are dual to each other.
Combinatorial design— Weight-four codewords of the \([2^r,2^r-r-1, 4]\) extended Hamming code support the Steiner system \(S(3,4,2^r)\) [5; pg. 89].
\([2^r-1,2^r-r-1,3]\) Hamming code— Extended Hamming codes are extensions of Hamming codes by a parity-check bit. Puncturing extended Hamming codes yields the Hamming codes.
Preparata code— Any code with the same parameters as the Preparata code must be a distance invariant subcode of a (possibly nonlinear) code with the same parameters as the extended Hamming code [6,7].
ZRM code— The weight-four codewords of the binary image of the dual of ZRM\((1,m)\) form a Steiner system that is identical to that formed by the weight-four codewords of an extended Hamming code [8].

Member of code lists

Primary Hierarchy

Classical Domain

Binary Kingdom

Binary codeECC

Binary group-orbit codeECC

Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC

Karlin double circulant codeSelf-dual linear Self-dual additive Linear \(q\)-ary ECC

Parents

Karlin double circulant code

The extended Hamming code is equivalent to the Karlin double circulant code for \(m=3\) [9; Ch. 16].

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

The extended Hamming code is an extended binary quadratic-residue code [9; Ch. 16].

Small-distance block codeECC

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

Children

\([8,4,4]\) extended 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]: H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[5]: J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[6]: N. V. Semakov, V. A. Zinoviev, G. V. Zaitsev, “Uniformly Packed Codes”, Probl. Peredachi Inf., 7:1 (1971), 38–50; Problems Inform. Transmission, 7:1 (1971), 30–39
[7]: Zaitsev, G. V., Zinoviev, V. A., & Semakov, N. V. (1973). Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-error-correcting codes. In Proc. 2nd International Symp. Inform. Theory (pp. 257-263).
[8]: A. R. Hammons Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
[9]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.

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,2^r-r-1,4]\) Extended Hamming code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/extended_hamming

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