Hamming Code

Error control is a fundamental requirement in any digital communication system. When bits travel through noisy channels, some of them get corrupted. Hamming code is one of the earliest and most elegant solutions to this problem, capable of detecting and correcting single-bit errors automatically, making it a cornerstone topic in GATE and university examinations.

Core Concept of Hamming Code

A linear block code adds redundant bits to the original data so that the receiver can not only detect but also locate and correct errors. Hamming code is a specific linear block code designed to correct all single-bit errors. The key idea is that each parity bit is responsible for a specific subset of data bits, and together the parity bits form a binary address called the syndrome that directly points to the position of the erroneous bit.

In a (n, k) Hamming code, n is the total codeword length and k is the number of data bits. The number of parity bits r satisfies the condition that 2^r >= n + 1. For k = 4 data bits, r = 3 parity bits are needed, giving n = 7. This is called the (7,4) Hamming code. The parity bits are placed at positions that are powers of 2: positions 1, 2, and 4.

Each parity bit covers positions whose binary representation has a 1 in the same bit position as the parity bit. For example, p1 at position 1 (binary 001) checks all positions that have a 1 in the least significant bit: positions 1, 3, 5, 7. Similarly, p2 at position 2 (binary 010) checks positions 2, 3, 6, 7. And p4 at position 4 (binary 100) checks positions 4, 5, 6, 7. This systematic overlapping structure is what makes Hamming code work.

Mathematical Expression

The parity bits are computed using even parity (XOR) over their respective groups. For a (7,4) code with data bits d1, d2, d3, d4 placed at positions 3, 5, 6, 7:

• p1 = d1 XOR d2 XOR d4 (positions 3, 5, 7)
• p2 = d1 XOR d3 XOR d4 (positions 3, 6, 7)
• p4 = d2 XOR d3 XOR d4 (positions 5, 6, 7)

At the receiver, the syndrome S = s1 s2 s3 is computed by rechecking each parity group. If all checks pass, S = 000 means no error. If S is non-zero, its decimal value gives the exact bit position in error, which is then flipped to recover the correct codeword. The minimum Hamming distance of the (7,4) code is 3, which is what guarantees single error correction (SEC) and double error detection (DED).

Practical Understanding

Hamming codes are widely used in memory systems, particularly in ECC (Error Correcting Code) RAM modules found in servers and workstations. When a cosmic ray or power fluctuation flips a single bit in RAM, the hardware uses Hamming-based ECC to detect and silently correct it before the processor reads the data. This prevents silent data corruption, which can be catastrophic in financial or scientific computing systems.

In digital communication, the Hamming code trades bandwidth efficiency for reliability. Sending 7 bits instead of 4 means a code rate of R = k/n = 4/7 ≈ 0.571. While this is less efficient than uncoded transmission, it guarantees error-free reception in channels where only isolated single-bit errors occur, such as slow-speed serial links.

Given:
Data bits: d1=1, d2=0, d3=1, d4=1
Code: (7,4) Hamming code (even parity)

Why this formula applies:
Parity bits are computed by XOR over their coverage groups to ensure even parity.

Formula:
p1 = d1 XOR d2 XOR d4
p2 = d1 XOR d3 XOR d4
p4 = d2 XOR d3 XOR d4

Substitution:
p1 = 1 XOR 0 XOR 1 = 0
p2 = 1 XOR 1 XOR 1 = 1
p4 = 0 XOR 1 XOR 1 = 0

Calculation:
Codeword bit positions: 1=p1, 2=p2, 3=d1, 4=p4, 5=d2, 6=d3, 7=d4
Coded word = 0 1 1 0 0 1 1

Now suppose bit at position 5 gets flipped during transmission:
Received word = 0 1 1 0 1 1 1

Syndrome check:
s1 = r1 XOR r3 XOR r5 XOR r7 = 0 XOR 1 XOR 1 XOR 1 = 1
s2 = r2 XOR r3 XOR r6 XOR r7 = 1 XOR 1 XOR 1 XOR 1 = 0
s3 = r4 XOR r5 XOR r6 XOR r7 = 0 XOR 1 XOR 1 XOR 1 = 1

Final Answer:
Syndrome = s3 s2 s1 = 101 (binary) = 5 (decimal)
Error is at position 5. Flip bit 5 to correct the codeword.

Exam Tip: In GATE, syndrome value in decimal directly gives the error position. If syndrome = 0, codeword is error-free. The minimum Hamming distance of 3 means SEC-DED capability: never confuse detection with correction.

Quick Revision

• (7,4) Hamming code: 4 data bits, 3 parity bits, 7-bit codeword. Parity bits placed at positions 1, 2, 4 (powers of 2).
• Parity bit condition: 2^r >= n + 1, where r = parity bits and n = total bits.
• Syndrome = binary address of the erroneous bit. Syndrome = 000 means no error.
• Minimum distance d_min = 3 for (7,4) Hamming code. Corrects 1 error, detects 2 errors (SEC-DED).
• Code rate R = k/n = 4/7 for (7,4) code.
• Exam trap: Parity bits are at positions 1, 2, 4 not at 1, 2, 3. Do not place parity bits sequentially.
• Practical use: ECC RAM in servers uses Hamming-based codes to silently correct single-bit memory errors.