3.4 Hamming Codes & Error Correction

Theory: Hamming Codes & Error Correction

Detecting an error is enough when the data can simply be sent again. In computer memory and long-term storage that is not possible: the original is gone. To keep data correct over the long term we need codes that can detect and correct errors. The two most important are Hamming codes (used for memory, our focus here) and Reed-Solomon codes, which are good at correcting burst errors (a series of adjacent damaged bits), which is why easily scratched CD-ROMs use a Reed-Solomon code.

Code words: m data bits + r check bits

A Hamming code forms code words by adding redundant check bits (parity bits) to each data word:

$n = m + r \qquad \begin{cases} m = \text{data bits} \\ r = \text{redundant (check/parity) bits} \\ n = \text{bits in the code word} \end{cases}$

Hamming distance

The Hamming distance between two code words is the number of bit positions in which they differ. To compute it, XOR the words and count the 1s in the result.

Mini-example

  1 0 0 0 1 0 0 1
⊕ 1 0 1 1 0 0 0 1
  ---------------
  0 0 1 1 1 0 0 0   → three 1s → Hamming distance 3

Minimum Hamming distance, D(min)

The minimum Hamming distance $D(\min)$ of a code is the smallest Hamming distance between all pairs of legal code words. It determines what the code can do:

Why? Think of legal code words as islands.

• If they are at least $k + 1$ apart, then $k$ flips can never turn one legal word into another, so the receiver always sees an illegal word: detected.
• If they are at least $2k + 1$ apart, then a word with up to $k$ flips is still closer to the original than to any other legal word (the other one is at least $k + 1$ away), so the receiver corrects it to the nearest legal code word.

Turning the rules around: a code with distance $D(\min)$ detects $D(\min) - 1$ errors and corrects $\lfloor (D(\min) - 1)/2 \rfloor$ errors.

Mini-example (as in the lecture)

Two data bits + one even parity bit: the legal words are 000, 011, 101, 110, so $D(\min) = 2$ → it detects $k = 1$ error but corrects none. If 010 is received it has odd parity, so an error is detected. It cannot be corrected: 010 is distance 1 from 000, from 011 and from 110, so we cannot tell which was sent. A received 000 is legal and accepted, but it could still be a 2-bit error (e.g. 011 → 000), which this code cannot see.

How many check bits? $(m + r + 1) \le 2^r$

Take any legal code word of $n$ bits. An error can hit any one of its $n$ bits, giving $n$ different illegal words at distance 1 (e.g. for the 3-bit word 100 they are 000, 110 and 101). So each legal word “owns” $n + 1$ patterns: itself plus its $n$ one-bit-error neighbours. To correct single-bit errors these groups must not overlap. There are $2^m$ legal words and only $2^n$ patterns in total:

$(n + 1)\,2^m \le 2^n \quad\Longrightarrow\quad (m + r + 1)\,2^m \le 2^{m+r} \quad\Longrightarrow\quad \boxed{(m + r + 1) \le 2^r}$

This gives the lower limit on the number of check bits. Find the smallest $r$ that satisfies it:

So an 8-bit data word that must survive any single-bit error needs 4 check bits, giving 12-bit code words.

Where the check bits go: the lecturer’s layout

1. Number the bit positions 1 to n from the right.
2. Put the check bits at the positions that are powers of 2: 1, 2, 4, 8, … .
3. Fill the remaining positions with the data bits from the highest position down, in the order the data word is written (leftmost data bit → highest non-power-of-2 position).

For $m = 8$, $n = 12$:

position :  12  11  10   9   8   7   6   5   4   3   2   1
binary   : 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
contents :  d   d   d   d   P8  d   d   d   P4  d   P2  P1

Which positions each check bit covers

Write each position number in binary. The check bit at position $c$ covers every position whose binary number has the $c$ bit set.

Read the other way round, each position is covered by exactly the check bits that add up to its number: position $11 = 8 + 2 + 1$ is covered by P8, P2 and P1. That is the whole trick: if position 11 goes wrong, exactly P8, P2 and P1 fail, and $8 + 2 + 1 = 11$ points straight at it.

Generating the check bits (even parity)

Each check bit is the modulo-2 sum (XOR) of the data bits it covers, so its group (check bit + covered data bits) has an even number of 1s.

$m = 4$, data 1011 → $r = 3$, $n = 7$, data in positions 7, 6, 5, 3 = 1, 0, 1, 1. P1 (3, 5, 7) $= 1 \oplus 1 \oplus 1 = 1$; P2 (3, 6, 7) $= 1 \oplus 0 \oplus 1 = 0$; P4 (5, 6, 7) $= 1 \oplus 0 \oplus 1 = 0$. Code word (positions 7 → 1): 1 0 1 0 1 0 1 = 1010101.

Locating and correcting a single-bit error

The error-correcting function in memory works like this: when a word is written, a function $f$ computes the key $K$ from the data $M$ and both are stored. When the word is read, $f$ is applied again to the data read out, and the new key is compared with the stored key:

Procedure

An equivalent way to get the same syndrome: for each check bit $c$, XOR all bits of its group including the stored check bit. A group with even parity gives 0, a failed group gives 1, and the failed groups add up to the bad position.

A Hamming code with $D(\min) = 3$ corrects one error. If two bits flip, the syndrome is non-zero but points at the wrong position, and “correcting” it makes things worse. Memory systems often add one more overall parity bit (SEC-DED: single-error-correct, double-error-detect) so that double errors are at least detected.

Worked Examples

  10001001
⊕ 10110001
  --------
  00111000   → 3 ones

position : 12 11 10  9  8  7  6  5  4  3  2  1
contents :  1  1  0  1 P8  0  1  1 P4  0 P2 P1

position : 12 11 10  9  8  7  6  5  4  3  2  1
bit      :  1  1  0  1  1  0  1  1  1  0  0  1

  stored K   1 1 0 1
⊕ new K'     1 0 0 0
  ---------------
  syndrome   0 1 0 1   = 5

position : 7  6  5  4  3  2  1
bit      : 1  0  1  0  1  0  1