SLIDE 1 / 10
CSZone.co.uk
Click anywhere to advance · Arrow keys also work
AQA 7517 · Paper 2 · 4.5.4c

Hamming
Codes

Error detection AND correction · Section 4.5

WHAT YOU'LL LEARN
Single-error correction · Parity positions · Hamming distance · Worked examples
AQA SPEC LINK
4.5.4 — Error correction: Hamming codes
Beyond Parity

From Detection to Correction

Parity bits can detect a single-bit error — but not locate it or correct it
Hamming codes use multiple parity bits to both detect AND pinpoint (correct) a single-bit error
Invented by Richard Hamming at Bell Labs (1950)
Used in ECC (Error Correcting Code) RAM, satellite data, storage systems
Key Concept

Parity Check Positions

In a Hamming code, parity bits are placed at positions that are powers of 2: positions 1, 2, 4, 8, 16…
P1
P
P2
P
D3
D
P4
P
D5
D
D6
D
D7
D
P = parity bit (positions 1, 2, 4) · D = data bit (positions 3, 5, 6, 7)
Which Bits Each Parity Covers

Parity Bit Coverage

Each parity bit checks positions whose binary representation has a 1 in the same bit position.

P1 (bit 1 = 001): covers positions 1, 3, 5, 7
P2 (bit 2 = 010): covers positions 2, 3, 6, 7
P4 (bit 4 = 100): covers positions 4, 5, 6, 7
Each parity bit ensures even parity across its group. If a bit flips, one or more parity checks fail — the failing parity positions add up to the position of the error.
Worked Example

Encoding: Data = 1011

Data bits D3=1, D5=0, D6=1, D7=1 (placed at positions 3,5,6,7)
P1: covers pos 1,3,5,7 → data=1,0,1 → sum=2 (even) → P1=0
P2: covers pos 2,3,6,7 → data=1,1,1 → sum=3 (odd) → P2=1
P4: covers pos 4,5,6,7 → data=0,1,1 → sum=2 (even) → P4=0
P1
0
P2
1
D3
1
P4
0
D5
0
D6
1
D7
1
Transmitted: 0110011
Error Detection

Finding & Fixing the Error

Suppose bit at position 5 flips: received = 0110111
Re-run parity checks:
P1 (1,3,5,7): 0,1,1,1 → sum=3 (odd) → FAIL
P2 (2,3,6,7): 1,1,1,1 → sum=4 (even) → PASS
P4 (4,5,6,7): 0,1,1,1 → sum=3 (odd) → FAIL
P1 and P4 failed → error position = 1 + 4 = 5. Flip bit 5 back. Error corrected!
Hamming Distance

Hamming Distance

The Hamming distance between two code words is the number of bit positions where they differ
Example: 1011010 vs 1001110 differ in positions 3, 5, 6 → Hamming distance = 3
Minimum Hamming distance of 3 means any single-bit error produces a code at distance 1 — detectable and correctable
Minimum distance of 2 → detect single errors. Distance 3 → correct single errors
Real-World Use

Where Hamming Codes Are Used

ECC RAM (Error Correcting Code Memory)
Servers use ECC RAM — Hamming-based correction silently fixes single-bit errors in memory, critical for financial/medical systems
Satellite & Space Communications
NASA uses advanced Hamming-derived codes (like Reed-Solomon) for Voyager probe data transmissions over billions of miles
QR Codes
Reed-Solomon error correction (related concept) allows QR codes to remain readable even with up to 30% damage
AQA Exam Style

Practice Question

AQA 7517 — Paper 2 Style
(a) State the difference between error detection and error correction. [2]
(b) In a Hamming code with 7 bits (positions 1–7), state which positions are used for parity bits. [1]
(c) A Hamming code receives: 1 1 1 0 1 1 0 (positions 1–7). Parity checks: P1 fails, P2 fails, P4 passes. Identify the position of the error. [2]
[5 marks]
2 marks
(a) Error detection identifies that an error has occurred [1]; error correction additionally locates and fixes the erroneous bit [1]
1 mark
(b) Positions 1, 2, and 4 (powers of 2)
2 marks
(c) P1 (value 1) and P2 (value 2) failed → error at position 1+2 = 3
Summary

Key Points to Remember

Parity bits in Hamming codes placed at positions 1, 2, 4, 8… (powers of 2)
Each parity bit covers positions sharing its bit in binary (P1→1,3,5,7; P2→2,3,6,7; P4→4,5,6,7)
Error location = sum of failing parity bit positions → flip that bit to correct
Hamming distance ≥ 3 required for single-error correction
Used in ECC RAM, satellites, QR codes — anywhere reliable data is critical
🎉 Lesson complete — move to the quiz!