DE Notes
Complete guide to Hamming code: parity bit positions, encoding procedure, single-bit error detection and correction, distance-2 and distance-3 codes, and GATE-level problems.
Why Error Correction?
In digital transmission and storage, bits can get corrupted. Simple parity detects single-bit errors but cannot locate or correct them. Hamming code (invented by Richard Hamming, 1950) adds multiple parity bits that work together to both detect AND correct single-bit errors.
Parity Bit Positions
Parity bits are placed at positions that are powers of 2: positions 1, 2, 4, 8, 16, ...
For a message with m data bits, the number of parity bits r satisfies:
| Data bits (m) | Parity bits (r) | Total bits (m+r) |
|---|---|---|
| 1 | 2 | 3 |
| 2-4 | 3 | 5-7 |
| 5-11 | 4 | 9-15 |
| 12-26 | 5 | 17-31 |
Encoding — Step by Step (7-bit Hamming)
Example: Encode data bits 1011 using Hamming code.
Step 1: Determine parity bits needed m = 4 data bits → r = 3 parity bits → total = 7 bits
Step 2: Assign positions
- P1 at position 1, P2 at position 2, P3 at position 4
- D1=1, D2=0, D3=1, D4=1 (data 1011)
| Position | 7 6 5 4 3 2 1 |
| Bit | D4 D3 D2 P3 D1 P2 P1 |
| Value | 1 0 1 P3 1 P2 P1 |
Step 3: Calculate each parity bit
P1 covers positions with bit 1 set in binary: 1, 3, 5, 7
P2 covers positions with bit 2 set: 2, 3, 6, 7
P3 covers positions with bit 4 set: 4, 5, 6, 7
Step 4: Final Hamming code
Error Detection and Correction
Received code: Suppose 1010101 but bit 5 got flipped → received: 1000101
Step 1: Recalculate syndrome bits
Check P1 (positions 1,3,5,7): 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1 → C1 = 1 (error) Check P2 (positions 2,3,6,7): 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0 → C2 = 0 (no error) Check P3 (positions 4,5,6,7): 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1 → C3 = 1 (error)
Step 2: Syndrome = C3C2C1 = 101 = 5
Error is in bit position 5. Flip bit 5: 1000101 → 1010101 ✓ (corrected!)
Parity — Quick Review
| Type | Detects | Corrects | How |
|---|---|---|---|
| Single parity bit | 1-bit errors | Cannot correct | Adds 1 bit per message |
| Hamming code | 2-bit errors | 1-bit errors | Adds r parity bits (distance 3) |
| SEC-DED Hamming | 2-bit errors + detect | 1-bit errors | Adds extra overall parity bit |
Solved Problems
Q1: How many parity bits are needed for 11 data bits?
Q2: Received Hamming word (7-bit) is 1100110. Syndromes: C1=1, C2=1, C3=0. Which bit is in error?
Interview Questions
Q1: What is the minimum number of parity bits to correct single-bit errors in a 16-bit data word? 2^r ≥ 16 + r + 1 → try r=5: 32 ≥ 22 ✓. Answer: 5 parity bits (21 total bits).
Q2: Can Hamming code correct 2-bit errors? Standard Hamming code can detect 2-bit errors but not correct them. To correct 2-bit errors, you need a code with minimum Hamming distance 5 (which requires more redundancy).
Q3: What is SEC-DED? Single Error Correction, Double Error Detection. An extended Hamming code with one extra overall parity bit. It corrects any single-bit error and detects (but cannot correct) any double-bit error. Used in ECC memory (RAM modules).
Q4: What does a syndrome of 0 indicate? All syndrome bits being 0 (C1=C2=C3=0) indicates no error was detected. The received code word matches expected parity.
Q5: Where is Hamming code used in practice? ECC (Error Correcting Code) RAM uses Hamming-based codes. It's also used in satellite communication, disk storage (RAID systems), and QR codes use Reed-Solomon which is related. Any system where data must be reliably stored or transmitted uses some form of error-correcting code.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Hamming Code — Error Detection and Correction.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Digital Electronics topic.
Search Terms
digital-electronics, digital electronics, digital, electronics, codes, hamming, code, hamming code — error detection and correction
Related Digital Electronics Topics