Editing Hamming code (section)

{{distinguish|text=[[Huffman coding|Huffman code]]}}
{{short description|Family of linear error-correcting codes}}
{{More footnotes needed|date=March 2013}}

{{Infobox code
 | name           = Binary Hamming codes
 | image          = [[File:Hamming(7,4).svg|160px]]
 | image_caption  = The Hamming(7,4) code (with {{Math|''r'' {{=}} 3}})
 | namesake       = [[Richard W. Hamming]]
 | type           = [[Linear block code]]
 | block_length   = {{Math|2<sup>''r''</sup> − 1}} where {{Math|''r'' ≥ 2}}
 | message_length = {{Math|2<sup>''r''</sup> − ''r'' − 1}}
 | rate           = {{Math|1 − {{Sfrac|''r''|(2<sup>''r''</sup> − 1)}}}}
 | distance       = {{Math|3}}
 | alphabet_size  = {{Math|2}}
 | notation       = {{Math|[2<sup>''r''</sup> − 1, 2<sup>''r''</sup> − ''r'' − 1, 3]<sub>2</sub>}}-code
 | properties     = [[perfect code]]
}}

In [[computer science]] and [[telecommunications]], '''Hamming codes''' are a family of [[linear code|linear error-correcting codes]]. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the simple [[parity code]] cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are [[perfect code]]s, that is, they achieve the highest possible [[Block code#The rate R|rate]] for codes with their [[block length]] and [[Block code#The distance d|minimum distance]] of three.<ref>[https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes1.pdf See Lemma 12 of]</ref>
[[Richard W. Hamming]] invented Hamming codes in 1950 as a way of automatically correcting errors introduced by [[punched card]] readers. In his original paper, Hamming elaborated his general idea, but specifically focused on the [[Hamming(7,4)]] code which adds three parity bits to four bits of data.{{Sfnp|Hamming|1950|pp=153&ndash;154}}

In [[mathematical]] terms, Hamming codes are a class of binary linear code. For each integer {{Math|''r'' ≥ 2}} there is a code-word with [[block length]] {{Math|''n'' {{=}} 2<sup>''r''</sup> − 1}} and [[Block code#The message length k|message length]] {{Math|''k'' {{=}} 2<sup>''r''</sup> − ''r'' − 1}}. Hence the rate of Hamming codes is {{Math|''R'' {{=}} ''k'' / ''n'' {{=}} 1 − ''r'' / (2<sup>''r''</sup> − 1)}}, which is the highest possible for codes with minimum distance of three (i.e., the minimal number of bit changes needed to go from any code word to any other code word is three) and block length {{Math|2<sup>''r''</sup> − 1}}. The [[parity-check matrix]] of a Hamming code is constructed by listing all columns of length {{Math|''r''}} that are non-zero, which means that the [[dual code]] of the Hamming code is the [[Hadamard code|shortened Hadamard code]], also known as a Simplex code. The parity-check matrix has the property that any two columns are pairwise [[linearly independent]].

Due to the limited redundancy that Hamming codes add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory (usually RAM), where bit errors are extremely rare and Hamming codes are widely used, and a RAM with this correction system is an ECC RAM ([[ECC memory]]). In this context, an extended Hamming code having one extra parity bit is often used. Extended Hamming codes achieve a Hamming distance of four, which allows the decoder to distinguish between when at most one one-bit error occurs and when any two-bit errors occur. In this sense, extended Hamming codes are single-error correcting and double-error detecting, abbreviated as '''SECDED'''.