Description
Member of an infinite family of perfect linear \(q\)-ary codes with parameters \([(q^r-1)/(q-1),(q^r-1)/(q-1)-r, 3]_q\) for \(r \geq 2\).
The automorphism group is known [3].
Protection
Can detect 1-bit and 2-bit errors, and can correct 1-dit errors.Cousins
- Incidence-matrix projective code— Columns of a Hamming parity-check matrix correspond to one-dimensional subspaces of \(GF(q)^n\).
- Cyclic linear \(q\)-ary code— Hamming codes are equivalent to cyclic codes when \(q\) and \(r\) are relatively prime ([4], pg. 194).
- Binary BCH code— Some narrow sense BCH codes of length \(n=(q^r-1)/(q-1)\) such that \(\text{gcd}(r,q-1)=1\) are \(q\)-ary Hamming codes ([5], Thm. 5.1.4).
- Generalized RM (GRM) code— \(q\)-ary Hamming codes are dual to first-order GRM codes [6; pg. 45].
- Maximum distance separable (MDS) code— The \([4,2,3]_3\) Hamming code is a unique MDS code [7,8].
- \(E_8\) Gosset lattice— The \([4,2,3]_3\) ternary Hamming code can be used to obtain the \(E_8\) Gosset lattice [9; Exam. 10.5.5].
- \([6,3,4]_4\) Hexacode— The hexacode is an extended quaternary Hamming code [5; Exer. 578].
- \(q\)-ary simplex code— \(q\)-ary Hamming and \(q\)-ary simplex codes are dual to each other.
- Perfect quantum code— For qubits (\(q=2\)), the only nontrivial perfect codes are the stabilizer code family \([[(4^r-1)/3, (4^r-1)/3 - 2r, 3]]\) for \(r \geq 2\), obtained from Hamming codes over \(GF(4)\) via the Hermitian construction [10,11]. These codes are related to partial spreads in projective geometry [12].
Primary Hierarchy
Parents
Hamming codes and their punctured and shortened versions are LP universally optimal codes [13].
\(q\)-ary Hamming code
Children
The tetracode is equivalent to the \(r=2\) \(3\)-ary Hamming code.
References
- [1]
- R. A. FISHER, “A SYSTEM OF CONFOUNDING FOR FACTORS WITH MORE THAN TWO ALTERNATIVES, GIVING COMPLETELY ORTHOGONAL CUBES AND HIGHER POWERS”, Annals of Eugenics 12, 283 (1943) DOI
- [2]
- M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) 657.
- [3]
- E. V. Gorkunov, “The group of permutation automorphisms of a q-ary hamming code”, Problems of Information Transmission 45, 309 (2009) DOI
- [4]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [5]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [6]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
- [7]
- Taussky, Olga, and John Todd. "Covering theorems for groups." Bulletin of the American Mathematical Society. Vol. 54. No. 3. 201 CHARLES ST, PROVIDENCE, RI 02940-2213: AMER MATHEMATICAL SOC, 1948.
- [8]
- J. G. Kalbfleisch and R. G. Stanton, “A Combinatorial Problem in Matching”, Journal of the London Mathematical Society s1-44, 60 (1969) DOI
- [9]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [10]
- D. Gottesman, “Pasting Quantum Codes”, (1996) arXiv:quant-ph/9607027
- [11]
- A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, “Quantum Error Correction via Codes over GF(4)”, (1997) arXiv:quant-ph/9608006
- [12]
- J. Bierbrauer, G. Faina, M. Giulietti, S. Marcugini, and F. Pambianco, “The geometry of quantum codes”, Innovations in Incidence Geometry: Algebraic, Topological and Combinatorial 6, 53 (2008) DOI
- [13]
- 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
Cite as:
“\(q\)-ary Hamming code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_hamming