What is Hamming code?
The best-known error-correcting code that corrects 1-bit errors. With r check bits, a codeword is 2^r − 1 bits long, of which 2^r − 1 − r bits carry data. The Hamming (7, 4) code, with r = 3, adds 3 check bits to 4 bits of data. Each check bit is the parity of an overlapping group of bits, and the result of redoing the checks at the receiver (the syndrome) gives the position of the wrong bit as a binary number. Its minimum Hamming distance is 3, and SECDED, which adds 1 bit of overall parity, can also detect 2-bit errors. It is used, for example, for ECC in server memory.
Japanese name: ハミング符号
Hamming code appears in 5 practice questions across 2 topics, including Information Theory and Coding Basics, Logic circuits.
Field: Information Theory and Coding Basics
How the (7, 4) code works
The bit positions are numbered 1 to 7, and the power-of-2 positions 1, 2 and 4 are the check bits. Check 1 makes the number of 1s even over the positions whose number has a 1 in the ones place when written in binary (1, 3, 5, 7), check 2 over those with a 1 in the twos place (2, 3, 6, 7), and check 4 over those with a 1 in the fours place (4, 5, 6, 7). Only the checks corresponding to the binary digits that are 1 in the number of the wrong position fail, so adding the weights of the failing checks gives the wrong position.
Code rate and length
With r check bits the codeword is 2^r − 1 bits long, and the longer the code, as in (7, 4), (15, 11) and (31, 26), the higher the code rate: 4/7 ≈ 0.57, 11/15 ≈ 0.73 and 26/31 ≈ 0.84. In exchange, one codeword can correct only 1 bit, so the longer the codeword, the more likely it is to receive an error of 2 or more bits.
FAQ
What happens with a Hamming code when a 2-bit error occurs?
In a Hamming code without overall parity, a 2-bit error still makes the syndrome point to some nonzero position, so a correct bit is flipped and the error grows to 3 bits. To prevent this, memories and similar devices use SECDED, which adds overall parity, and report a 2-bit error as an error instead of correcting it.
Are Hamming codes still used today?
Yes. They are simple and fast to compute, so they are widely used where latency must be kept small, such as ECC for memory and the protection of caches and registers. Where many errors must be corrected efficiently, as in communication, more powerful codes such as LDPC codes are used.