2.4Hamming code and distance
The idea
A Hamming code adds check bits placed at positions 1, 2, 4, 8, ... so that the failed checks, read as a binary number, point at the flipped bit. The minimum Hamming distance d decides how many errors a code can detect and correct.
Think of it like this: A game of twenty questions: each check bit answers one yes or no question about the position, and together the answers name the bad position.
Why it exists
GATE asks to find a missing data or check bit in a given codeword, or how many errors a code of distance d can fix.
How it works
- Positions run 1 to n. A check bit at position 2i covers every position that has bit i set in its binary form.
- Set each check bit so its group has even (or odd) parity.
- At the receiver recompute each group. Failed groups give a binary syndrome = position of the flipped bit.
- Distance d: detects d − 1 errors, corrects ⌊(d − 1)/2⌋.
Worked example: 8 data bits: how many check bits?
Smallest r with 2r ≥ 8 + r + 1: r = 4 (16 ≥ 13). The codeword has 12 bits.
Now play with it
- →Click a bit to flip it and read off the syndrome.
- →Flip two bits and notice the wrong position: Hamming (d = 3) corrects only one error.
4 data bits need r = 3 parity bits (smallest r with 2r ≥ m + r + 1), placed at positions 1, 2, 4, 8, ... Click any bit below to flip it as a channel error.
| parity bit | covers positions | check at receiver |
|---|---|---|
| p1 | 1, 3, 5, 7 | ok (0) |
| p2 | 2, 3, 6, 7 | ok (0) |
| p4 | 4, 5, 6, 7 | ok (0) |
Minimum Hamming distance d: detect up to d − 1 errors, correct up to ⌊(d − 1)/2⌋. This code has d = 3, so it corrects 1 and detects 2.
m = 8 gives r = 4 and a 12-bit codeword, as in the GATE 2021 question.
Check yourself
A code has minimum distance 5. It can correct and detect up to
Exam notes (the dense version)
The Hamming distance d between two codewords is the number of differing bits; a code detects up to d − 1 errors and corrects up to ⌊(d − 1)/2⌋. For single-error correction with m data bits you need r check bits with 2ʳ ≥ m + r + 1. Check bits sit at positions 1, 2, 4, 8, ...; check bit p covers every position whose binary form has bit p set. The syndrome (the failed checks read as a binary number) is the position of the flipped bit.
Previous year questions: Framing & Error Control (2)
PYQs are grouped by topic, so this is the full set for Framing & Error Control; try the ones that match this subtopic. Open all 2 on the topic page.