Coding Theory
Hamming Distance
Even Parity Bit
Hamming(7,4) Encode
Encodes 4 data bits into a 7-bit error-correcting codeword.
Hamming(7,4) Decode & Correct
Detects and corrects a single-bit error in a 7-bit codeword.
Understanding Coding Theory
Coding theory studies how to encode information so that errors introduced during transmission or storage can be detected, and ideally corrected, without needing to resend the data. Every time a CD plays despite a scratch, a QR code scans despite partial damage, or a deep-space probe sends a clean image across billions of miles, an error-correcting code is doing the work behind the scenes.
Key Definitions & Formulas
- Hamming distance: the number of positions in which two equal-length strings differ — the basic measure of how "far apart" two codewords are.
- Error detection: a code can detect up to d-1 errors, where d is the minimum Hamming distance between any two codewords.
- Error correction: a code can correct up to ⌊(d-1)/2⌋ errors.
- Parity bit: a simple extra bit added so the total number of 1s is even (or odd), catching single-bit errors.
- Hamming code: a classic scheme using multiple parity bits placed at specific positions to both detect and correct single-bit errors.
Worked Example
The codewords 0000 and 1111 have Hamming distance 4. If only these two codewords are used, up to 3 bit-flips can be detected (since no combination of 3 flips turns one into the other), and up to 1 error can be corrected by always assuming the closer codeword is the intended one.
Where This Is Used
- CDs, DVDs, and hard drives, which use error-correcting codes to survive physical damage/wear.
- Wireless and satellite communication, where signal noise causes bit errors.
- QR codes, which remain scannable even when partially obscured.
- RAID storage systems and network data transmission protocols (e.g. checksums in TCP/IP).