Study guide: Coding Theory
Overview
Coding theory is about sending data reliably over noisy channels. The idea is to add structured redundancy so that errors can be detected or even corrected. Hamming distance measures how different two codewords are, and it determines how many errors a code can handle.
Key ideas explained
Hamming distance
The Hamming distance between two equal-length strings is the number of positions where they differ. A code with minimum distance d can detect up to d − 1 errors and correct up to ⌊(d − 1)/2⌋ errors.
Parity bits
An even-parity bit is chosen so the total number of 1s is even. It detects any odd number of flipped bits but cannot correct, and it misses an even number of flips. It gives minimum distance 2.
The Hamming(7,4) code
Four data bits plus three parity bits form a 7-bit codeword with minimum distance 3, so any single-bit error can be corrected. In the standard layout the parity bits sit at positions 1, 2 and 4, and each covers the positions whose binary index includes that bit. The syndrome, read as a binary number, is the position of the error.
Efficiency and perfect codes
More redundancy means more protection but a lower rate; Hamming(7,4) has rate 4/7. It is a perfect code: 2⁴ codewords × (1 + 7) single-error patterns fill all 2⁷ words. Real systems use stronger codes such as CRC, Reed–Solomon and LDPC.
Worked examples
A Hamming distance
Problem. Find the distance between 10110 and 11100.
- Compare position by position: 1/1 same, 0/1 differ, 1/1 same, 1/0 differ, 0/0 same.
Answer. Distance 2.
Encoding and correcting with Hamming(7,4)
Problem. Encode data bits d₁d₂d₃d₄ = 1011 using the layout p₁ p₂ d₁ p₄ d₂ d₃ d₄, then correct a received word with position 6 flipped.
- p₁ covers positions 1, 3, 5, 7: d₁ + d₂ + d₄ = 2, so p₁ = 0.
- p₂ covers 2, 3, 6, 7: d₁ + d₃ + d₄ = 3, so p₂ = 1.
- p₄ covers 4, 5, 6, 7: d₂ + d₃ + d₄ = 2, so p₄ = 0. Codeword: 0110011.
- Received 0110001: check 1 (positions 1,3,5,7) is even → 0; check 2 (2,3,6,7) is odd → 1; check 4 (4,5,6,7) is odd → 1.
- Syndrome 110 in binary is 6, so flip bit 6 to restore 0110011.
Answer. Codeword 0110011; the syndrome 6 identifies and fixes the error.
Enter these same values in the calculator above and compare each step with the working shown here.
Common mistakes to avoid
- Thinking a parity bit can correct errors. It only detects an odd number of them.
- Misplacing parity bits. In Hamming codes they sit at positions 1, 2, 4, 8, and so on.
- Confusing detection (d − 1) with correction (⌊(d − 1)/2⌋).
- Expecting Hamming(7,4) to handle two errors. It may silently “correct” to the wrong codeword.
- Comparing strings of different lengths. Hamming distance is undefined for them.
Where this shows up in computer science
- ECC memory and storage systems use Hamming-style and Reed–Solomon codes to survive bit flips.
- Networking uses CRC checks to detect corrupted frames.
- QR codes and optical discs include error-correcting codes so damaged areas can still be read.
Test yourself
Try each question before opening the answer.
A code has minimum distance 5. How many errors can it detect and correct?
Detect 4 and correct 2.
Add an even-parity bit to 1101001.
It has four 1s, so append 0: 11010010.
What is the rate of Hamming(7,4)?
4/7 ≈ 0.571.