The parity bit and Hamming distance

A channel is never perfect

When bits travel (cable, radio waves, disk), some of them flip: a 0 becomes 1, a 1 becomes 0. Without precautions, you receive a corrupted message without even knowing it. The idea of error-correcting codes is to add calculated redundancy, first to detect, then sometimes to correct these errors.

The parity bit

The simplest approach: add a parity bit at the end of a block, chosen so that the total number of 1s is even. On reception, you count again: if the total is odd, a bit has been altered.

data: 1 0 1 1  ->  number of 1s = 3 (odd)
parity bit added: 1   (to make the total even)
transmitted word: 1 0 1 1 1   ->  four 1s, that's even (correct)

on reception, if an odd number of 1s is counted -> an error is detected

Its limitation

The parity bit detects any odd number of errors (1, 3, 5...), but misses an even number of errors: if two bits flip, the parity stays correct and the error goes unnoticed. Above all, it detects without being able to correct: it signals that an error exists, without saying where.

Hamming distance

The Hamming distance between two binary words is the number of positions in which they differ. For example, between 1011 and 1110, it is 2 (positions 2 and 3 differ). It is the key tool for reasoning about codes.

  1 0 1 1
  1 1 1 0
  -------
  = . X . X    (2 differing positions -> Hamming distance = 2)

Why the minimum distance matters

A code does not use all possible words, only some of them, called valid words (codewords). The smallest distance between two valid words is called the minimum distance of the code. It decides everything: to detect up to d errors, you need a minimum distance of at least d+1; to correct up to d errors, you need at least 2d+1.

Classic pitfall

Detecting and correcting are not the same thing. A simple parity bit detects an error but cannot correct it, since it does not know which bit is at fault. Correcting requires more redundancy: that is the whole point of the Hamming code, in the next lesson.