Hamming codes and their properties

Hamming codes

Hamming codes are linear block codes that can detect up to two-bit errors and correct all single-bit errors. For r ≥ 2 parity bits the code is (n, k) = (2ʳ − 1, 2ʳ − 1 − r), e.g. (7,4) and (15,11). The parity bits are placed at positions 1, 2, 4, 8, … and each checks the positions that contain it in their binary index.

Properties

• Block length n = 2ʳ − 1 and k = n − r data bits; rate k/n = 1 − r/n approaches 1 for large r.
• Minimum Hamming distance d_min = 3: detects 2 errors or corrects 1 error.
• They are perfect codes: all 2ⁿ words lie within distance 1 of exactly one codeword.
• Linear (sum of codewords is a codeword), and can be made cyclic.
• Syndrome decoding: the r-bit syndrome gives the exact position of a single-bit error (0 = no error).
• Adding an overall parity bit gives an extended Hamming code with d_min = 4 (single-error correction, double-error detection).
• Simple to implement with XOR gates; used in ECC memory.

Visualising 3-bit words as code vectors

All 3-bit words are the 8 vertices of a cube; the Hamming distance between two words is the number of edges on the shortest path between them.

       011 ---------- 111
       /|             /|
      / |            / |
    010 ---------- 110 |
     |  001 -------|-- 101
     | /           | /
     |/            |/
    000 ---------- 100

• Repetition code {000, 111}: the two vertices are 3 edges apart, d_min = 3, corrects 1 error (any word one step from 000 decodes to 000, one step from 111 decodes to 111).
• Even-parity code {000, 011, 101, 110}: every pair is 2 edges apart, d_min = 2, detects 1 error but cannot correct it.