Hamming code (error correction)

Why it exists

The CRC and the checksum detect that a frame was damaged; the cure is to send it again. That is expensive or impossible when the round trip is long (a space probe), when there is no return channel (broadcast, a CD), or when the data are stored (computer memory, where there is nobody to ask for a second copy). Error-correcting codes add enough redundancy that the receiver can find which bits are wrong and flip them back: forward error correction. The Hamming code is the classic and simplest one. It is not named in the official syllabus, but the idea of the distance of a code and the check-bit formulas appear in the data-link-layer questions of the exam.

Prerequisites

You need the idea of redundancy from error detection: parity bits, and a codeword that is a data word with extra bits.

Precise definitions

Hamming distance of two words of equal length: the number of positions in which they differ. For $10110$ and $11100$ it is 2.

Code with $m$ data bits and $r$ check bits: the set of the $2^m$ valid codewords of length $n = m + r$ out of all $2^n$ words. Minimum distance $d$ of the code: the smallest distance between two different codewords.

What the distance buys.

• It detects every error pattern of up to $d - 1$ flipped bits (no such pattern can turn a codeword into another codeword).
• It corrects every pattern of up to $t = \lfloor (d - 1) / 2 \rfloor$ flipped bits (the received word is nearer to the sent codeword than to any other).
• It corrects up to $t$ and at the same time detects up to $s \ge t$ errors if $d \ge s + t + 1$.

Hamming code. Number the positions $1, 2, \dots, n$ from the right. The positions that are powers of two (1, 2, 4, 8, ...) hold the check bits $c_1, c_2, c_4, c_8, \dots$; all other positions hold the data bits $d_1, d_2, \dots$ in order. The check bit $c_{2^k}$ is chosen so that the group of positions whose binary index has bit $k$ set contains an even number of ones (even parity; with odd parity the number of ones must be odd). The groups for a 12-bit word:

Syndrome. The receiver re-checks the groups; a group whose parity is wrong gives a 1. Read as a binary number (check of group 8 first), the result is the syndrome: 0 means every check passes, otherwise it is the position of a single wrong bit.

Number of check bits. A single error can be in any of the $n$ positions, or there is none: $n + 1$ cases, each needing its own syndrome out of $2^r$. So $2^r \ge m + r + 1$.

How it works

Encoding

The data $d_4 d_3 d_2 d_1 = 1011$ go to positions 7, 6, 5, 3; the check bits are computed one at a time. Each data bit takes part in the groups given by the ones of its position's binary index: position 3 = 011 is in the groups of $c_1$ and $c_2$, position 7 = 111 in all three. That is why a single flipped bit is recognised by which groups it spoils.

Decoding: the syndrome is the position

Position 5 (101 in binary) is in the groups of $c_1$ and $c_4$, so exactly those two checks fail, and the failed checks read $101 = 5$ (check 4 on the left). In general, flipping position $p$ spoils exactly the groups that contain $p$, which are the groups of the one-bits of $p$: the syndrome is the binary number $p$ itself. If the syndrome is 0 either there is no error or the pattern is invisible.

Two flipped bits at positions $p$ and $q$ give the syndrome $p \oplus q$, which is non-zero and is mistaken for a single error at that position: the decoder flips a third bit and delivers wrong data. The plain Hamming code corrects one error and cannot recognise two; its minimum distance is 3, so it detects two errors only if it is not asked to correct.

How many check bits?

The cost of the redundancy falls as the words get longer: 3 check bits for 4 data bits, but only 7 for 120. The codes of length $2^r - 1$ (7, 15, 31, 63, 127) use the syndromes completely and are perfect: every word is either a codeword or one flip away from exactly one. In a computer memory, 64 data bits need 7 check bits for single-error correction and 8 for the extended code below (72 bits stored for 64 of data).

Distance, detection and correction

Each row was found by comparing all pairs of codewords and confirmed with all error patterns. Observe: an even-parity bit gives $d = 2$ (detects one error, corrects none), the repetition code 000, 111 gives $d = 3$, and the Hamming code gives $d = 3$ however long it is. The balls of radius 1 around the codewords of the Hamming $(7,4)$ code cover all $2^7 = 128$ words, so it is perfect; the extended code with $d = 4$ is not (it has $d$ even, so a word can be at distance 2 from two codewords).

Detecting double errors as well: the extended code

Add one more parity bit over all the bits of the Hamming word. The minimum distance rises to 4, so the code corrects 1 error and detects 2 ($4 \ge 2 + 1 + 1$).

The decoder looks at the syndrome of the Hamming bits and at the overall parity. Overall parity odd: one error (the syndrome gives its position; syndrome 0 means the overall bit itself). Overall parity even and syndrome not zero: two errors, detected but not corrected. With three errors the code can be fooled (the last row); the guarantee covers one and two only. This single-error-correcting, double-error-detecting scheme (SEC-DED) is the one used in error-correcting memory.

Conventions that change the answer

• Odd parity: each group must hold an odd number of ones. The check bits are the complement of the even-parity ones, and an all-zero data word does not give an all-zero codeword (for 1011 the word is 1011110 instead of 1010101). The syndrome still names the position.
• Position numbering: from the right (c1 at the far right), as above, or from the left. Read the question's layout; the rule "check bits at the powers of two, group = positions with that bit set in the index" holds in both, it only changes where the word is written.
• A word with an error in a check bit: the syndrome names that check bit's position; the correction flips it. The data bits were never wrong.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Error detection and correction are two uses of the same redundancy, the distance between valid words: a code with distance $d$ detects $d - 1$ errors, and uses the same space to correct fewer. Detection plus retransmission suits links with feedback (see the sliding-window protocols); correction suits links where retransmission is costly. The same SEC-DED codes protect main memory.

PYQs

Assume that a 12-bit Hamming codeword
consisting of 8-bit data and 4 check bits is
d8d7d6d5c8d4d3d2c4d1c2c1, where the data
bits and the check bits are given in the
following tables:

Data Bits d8 d7 d6 d5 d4 d3 d2 d1

1
1
0
x
0
1
0
1

Check Bits
c8
c4
c2
c1

y
0
1
0

Which one of the following choices gives the
correct values of x and y?

Consider a binary code that consists of only four
valid
codewords
as
given
below:
00000, 01011, 10101, 11110.

Let the minimum Hamming distance of the code be
p and the maximum number of erroneous bits that
can be corrected by the code be q. Then the values
of p and q are:

Self-check

Revision card

References