SUNY Geneseo Department of Computer Science

Hamming Distance and Error Detection/Correction

Previous Lecture

Questions?

Error Correction/Detection

Error detection: Are one or more bits in a word read from memory not what were stored?

• e.g., parity bit

Error correction: If not, what bits were stored?

Typical cost measure: how many bits of error detection/correction information do you need, as a function of the number of bits protected.

• e.g., parity requires 1 bit to protect n

Typical performance measure is how many bit errors are detected/corrected

Theoretical basis for error detection and correction, esp. minimum costs

• Hamming Distance
• Mini-assignment: find out what Hamming Distance is
  • Number of bit positions in which two bit strings differ
  • e.g., Hamming distance 1 between
    • 10000000
    • 10000001
• Code = subset of possible bit strings
  • e.g., parity on 8 data bits
  • Possible strings (data + parity) are 9 bits
  • i.e., 512 possible words
  • Only 256 are valid, meaningful
  • e.g., even parity = set of 9 bit strings w/ even number of 1's
• Hammming distance for a code is minimum Hamming distance between valid words in that code
  • e.g., parity
  • Imagine a code word
  • What's the fewest bits that could possibly change to give a different code word?
    • 2 (keep # of ones even)
  • i.e., Hamming distance for parity is (at least) 2

To detect n bit errors, code needs Hamming distance n+1

• Why?

• Changing n bits isn't enough to make a new code word

To correct n bit errors code needs Hamming distance 2n + 1

• n changes leaves word closer to original code word than any other

Claim: to detect n errors (in n-bit word), keep 2 copies of the word

• But minimum Hamming distance is actually only 2

Error correction (Hamming code)

• Mini-assignment: Does this have Hamming distance 3?

Next Lecture