Error Correction (Hamming Code)

While CRC and checksums can only detect errors, Hamming Code can both detect and correct single-bit errors. This is critical in systems where retransmission is impractical (satellite communication, memory ECC).

1. The Concept

Hamming Code works by inserting redundant parity bits at specific positions in the data. Each parity bit covers a specific subset of data bits. If a single bit flips during transmission, the combination of parity checks uniquely identifies the position of the error, allowing automatic correction.

2. How Hamming(7,4) Works

The most common example encodes 4 data bits into 7 bits (3 parity bits + 4 data bits).

Parity Bit Positions:

Parity bits are placed at positions that are powers of 2: positions 1, 2, and 4. Data bits fill the remaining positions: 3, 5, 6, 7.

Parity Coverage:

• P1 (position 1): Checks positions whose binary representation has a 1 in the least significant bit: 1, 3, 5, 7.
• P2 (position 2): Checks positions with a 1 in the second bit: 2, 3, 6, 7.
• P4 (position 4): Checks positions with a 1 in the third bit: 4, 5, 6, 7.

Error Detection and Correction:

1. The receiver recalculates all parity bits.
2. If all parities match, no error occurred.
3. If parities don't match, the binary combination of the failing parity bits gives the exact position of the error. Flip that bit to correct it.

Example: If P1 and P4 fail (positions 1 and 4), the error is at position $1 + 4 = 5$.

3. SEC-DED (Single Error Correction, Double Error Detection)

By adding one extra overall parity bit, Hamming Code can correct single-bit errors AND detect (but not correct) double-bit errors. This is the standard used in ECC RAM (Error-Correcting Code memory) in servers.

4. Number of Parity Bits

For $m$ data bits, the number of parity bits $r$ must satisfy: $2^r \geq m + r + 1$.