Hamming Code

Hamming codes H(m, b) (introduced in [1] and [2]) are linear single-error-correcting [s, s−m, 3]-codes over Fb with

s = $\displaystyle {\frac{{b^{m}−1}}{{b−1}}}$

for all m ≥ 2.

The dual orthogonal array A = H(m, b)⊥ is a linear OA(bm, s, b, 2) with strength 2, which was already known by Rao [3]. An m×s generator matrix of A (and parity check matrix of H(m, b)) is constructed by using the s pairwise linearly independent vectors of Fbm. Such a set can be found, e.g. by choosing all non-zero vectors with leftmost non-zero coordinate equal to 1 from Fbm. When interpreted as a code, A is the [s, m, bm−1]-simplex code.

Optimality

Hamming codes are perfect codes, since they meet the Hamming or sphere packing bound. Alternatively, their dual OAs are tight.

See also

References

[1]Richard Wesley Hamming.
Error detecting and error correcting codes.
Bell System Technical Journal, 29:147–160, 1950.
[2]Marcel J. E. Golay.
Notes on digital coding.
Proceedings of the IEEE, 37:657, 1949.
[3]Calyampudi Radhakrishna Rao.
On a class of arrangements.
Proceedings of the Edinburgh Mathematical Society, 8:119–125, 1949.
[4]F. Jessie MacWilliams and Neil J. A. Sloane.
The Theory of Error-Correcting Codes.
North-Holland, Amsterdam, 1977.
[5]Jürgen Bierbrauer.
Introduction to Coding Theory.
Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, London, New York, Washington D.C., 2004.
MR2079734 (2005f:94001)

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Hamming Code.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CHamming.html

Show usage of this method