Short note: Hamming codes

Hamming codes are linear block codes that can detect up to two-bit errors or correct single-bit errors. For r parity bits, the code length is n = 2ʳ − 1 and the message length is k = n − r, e.g. (7,4) with r = 3 and (15,11) with r = 4. The minimum distance is 3 (an extra overall parity bit gives d_min = 4, called SECDED: single-error correction, double-error detection).

Construction (7,4)

Parity bits are placed at positions that are powers of 2 (1, 2, 4); data bits go at positions 3, 5, 6, 7:

 position : 1  2  3  4  5  6  7
 bit      : p1 p2 d3 p4 d5 d6 d7

Each parity bit checks the positions whose binary index contains it (even parity):

• p1 covers 1, 3, 5, 7
• p2 covers 2, 3, 6, 7
• p4 covers 4, 5, 6, 7

Example: data 1011 (d3 d5 d6 d7 = 1,0,1,1): p1 = 1⊕0⊕1 = 0, p2 = 1⊕1⊕1 = 1, p4 = 0⊕1⊕1 = 0 → codeword 0110011.

Error correction

The receiver recomputes the three checks c4 c2 c1. The binary number they form is the position of the erroneous bit (0 means no error). If bit 5 is received wrongly (0110011 → 0110111): c1 = 1, c2 = 0, c4 = 1 → 101 = 5, so flip bit 5.

Hamming codes are used in computer memory (ECC RAM) and data storage.