Hamming Code

Hamming code is the algorithm inside every ECC RAM module and RAID controller that silently fixes single-bit errors before your CPU sees corrupted data. Richard Hamming invented it in 1950 at Bell Labs, and the same principle still runs in DDR5 ECC DIMMs today.

Core Concept

Hamming code places parity check bits at positions that are powers of 2 (1, 2, 4, 8, …). Each parity bit covers all positions whose binary index has that power-of-2 bit set. The number of parity bits r needed for m data bits satisfies: 2^r >= m + r + 1. For 4 data bits, r=3, giving the Hamming (7,4) code.

During error checking, the receiver computes a syndrome — a multi-bit value formed by re-checking each parity group. A syndrome of zero means no error. A non-zero syndrome gives the binary position of the flipped bit. The receiver flips that bit to correct the error. This is single-error correction (SEC).

ECC DRAM uses Hamming (72,64): 64 data bits plus 8 check bits. The chip produces a 8-bit syndrome and can correct any single-bit error. Access time penalty for ECC is typically 1–2 ns. All server-grade DDR4 and DDR5 DIMMs require ECC; typical ECC DIMM power is 3–5 W at 1.1 V supply.

Boolean Expression

Each parity bit is computed as the XOR of the data bits it covers. For Hamming (7,4): P1 = D1 XOR D2 XOR D4; P2 = D1 XOR D3 XOR D4; P3 = D2 XOR D3 XOR D4. The syndrome S = (S3 S2 S1) where each Si is the re-check of parity bit Pi. The syndrome value equals the bit position of the error in binary — so syndrome 011 (decimal 3) means bit 3 is in error.

Given:
  Data bits D1=1, D2=0, D3=1, D4=1
  Hamming (7,4) with even parity
  Received codeword: 0 1 1 0 0 0 1  (bit 6 flipped from 1 to 0)

Parity coverage:
  P1 covers positions 1,3,5,7 → P1 XOR D1 XOR D2 XOR D4
  P2 covers positions 2,3,6,7 → P2 XOR D1 XOR D3 XOR D4
  P3 covers positions 4,5,6,7 → P3 XOR D2 XOR D3 XOR D4

Syndrome calculation on received word 0110001:
  S1 = P1 XOR r3 XOR r5 XOR r7 = 0 XOR 1 XOR 0 XOR 1 = 0
  S2 = P2 XOR r3 XOR r6 XOR r7 = 1 XOR 1 XOR 0 XOR 1 = 1
  S3 = P3 XOR r5 XOR r6 XOR r7 = 0 XOR 0 XOR 0 XOR 1 = 1

Syndrome S3 S2 S1 = 1 1 0 = 6 (decimal)

Final Answer:
  Error in bit position 6.
  Flip bit 6: received 0110001 → corrected 0110011.

Exam Tip: GATE regularly asks you to compute the syndrome and identify the error position. The syndrome is read as a binary number where S1 is the LSB and Sr is the MSB. Syndrome = 0 means no error. A very common mistake is reading the syndrome bits in reverse order and getting the wrong position. Also, Hamming code corrects only single-bit errors — a two-bit error produces a non-zero syndrome pointing to a wrong position, not detection of both errors, unless you use the extended Hamming code that adds a global parity bit.

Key Properties

• Parity bits at positions 1, 2, 4, 8, 16, … (powers of 2).
• Number of check bits r: must satisfy 2^r >= m + r + 1 for m data bits.
• Hamming (7,4): 4 data bits, 3 parity bits, Hamming distance = 3.
• ECC RAM uses Hamming (72,64): 64 data + 8 check bits, 1–2 ns latency overhead.
• Syndrome = binary address of the erroneous bit; 0 = no error.
• Extended Hamming adds global parity bit: detects 2-bit errors (double-error detection, SECDED).
• Code rate for (7,4): 4/7 ≈ 0.57; for (72,64): 64/72 ≈ 0.89.

Quick Revision

• Hamming code: SEC (single-error correction), Hamming distance = 3.
• Parity bits at power-of-2 positions; data bits fill remaining positions.
• Formula: 2^r >= m + r + 1 to find minimum parity bits.
• Syndrome bits = re-checks of each parity group XORed together.
• Syndrome value (binary) = position of error bit.
• Extended Hamming (SECDED): adds one global parity bit, achieves d=4.
• ECC DRAM: Hamming (72,64), standard in all server memory.
• Exam trap: reading syndrome bits MSB-first instead of LSB-first gives the wrong error position — always write S1 as LSB.