The Hamming code
The Hamming distance and what it lets a code detect and correct, the Hamming (7,4) code: check bits, encoding, syndrome, correcting one error, and the false correction when two bits have flipped.
- 21 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Hamming distance: what is it?
Show the answer
The number of positions where two words of the same length differ.
Between 1011001 and 1001011, two positions differ (the third and the sixth): the distance is 2. It is the number of bits that must flip to go from one to the other.
In a Hamming (7,4) word, at which positions are the check bits?
- At positions 1, 2 and 4
- At positions 5, 6 and 7, after the data
- At positions 1, 2 and 3, before the data
- At positions 1, 4 and 7, at both ends and in the middle
Show the answer
At positions 1, 2 and 4
The powers of two: one check bit per power of two, covering the positions whose binary representation includes that bit. The data bits 3, 5, 6 and 7 take the other places.
A code with minimum distance d detects … errors and corrects ….
Show the answer
A code with minimum distance d detects d − 1 errors and corrects (d − 1) / 2, rounded down.
For d = 3: 2 errors are detected and 1 is corrected. To correct, the altered word must be closer to the right word than to any other; to detect, it must not land on any other valid word.
Error-correcting code: what is it?
Show the answer
A code whose words are far enough apart that the receiver can recover the word sent, without a retransmission, from an altered received word.
An altered word must stay closer to the word sent than to any other valid word. It costs more redundancy bits than a code that merely detects.