CM · Noise and information

Error Coding

Shannon promised that below capacity the errors could be driven close to 0, but he did not reveal how. This unit shows that appending extra bits, computed from the data by a rule, lets the receiver notice bits flipped by noise, and even point to the wrong bit and fix it.

A flipped bit, three codes respond

The blue cells are the received data bits, the gold cells are the appended check bits, and the cell with the red border is the bit flipped by noise. Press No code, Parity, and Hamming in turn to compare how the three codes handle the same single-bit error. With data alone the error goes unnoticed, a single parity bit only notices that something is wrong, and Hamming points to the exact bit and fixes it.

Code length and minimum distance

n = 4, k = 4 · d_min = 1

No protection

Noise flips bits

Noise at the receiver occasionally turns a 0 into a 1 or a 1 into a 0. In the plot the original data is 1011, but its second bit flipped and it arrived as 1111. Had only the data bits been sent, 1111 would look like perfectly good 4-bit data, and the receiver would have no way to tell that an error even happened. Every bit pattern is equally plausible as data.

Extra bits stand guard

Append check bits computed from the data by a rule, and the situation changes. The simplest, a parity bit, is the XOR of all data bits, which always makes the count of 1s even. The original data 1011 has three 1s, so its parity is 1; when the second bit flips, the count becomes five 1s, an odd number, and the check fails. That tells the receiver an error occurred, but a single parity bit cannot say which bit is wrong.

Observep = d₁ ⊕ d₂ ⊕ d₃ ⊕ d₄

Parity is the XOR of the data bits.

Choosedetect 1: d_min ?

Detecting a single-bit error needs a minimum distance of 2.

Distance makes correction

Picture codewords as points: a good code keeps its valid points well apart. The number of bit positions in which two codewords differ is called the Hamming distance; if the minimum distance between valid codewords is 2, a single-bit error can be detected, and if it is 3, the error can even be corrected, because a word with one wrong bit still lies closest to its original codeword. Hamming (7,4) uses 3 check bits to locate an error in any one of the 7 bits. Each of the three check bits guards a different group of data bits, so the pattern of which checks fail points to a single flipped position. The price is a code rate R = k/n = 4/7: sending 4 bits of information costs 3 bits of overhead.

Fill incorrect 1: d_min ≥ ?

Correcting a single-bit error needs a minimum distance of 3.

On your ownR = kn = ?

The code rate is the number of data bits divided by the total number of bits.

Back to the first screen

With no protection, the flipped bit passed for valid data and showed red. Adding one parity bit raised a signal that something was off, but not which bit, so it showed orange; when Hamming's check bits pooled their mismatches, pinpointed that bit, and flipped it back, it turned gold. One thing to remember: when extra bits keep valid words far apart, a word nudged one step by noise still returns to the nearest original. This is how the reliability below capacity that Shannon promised is actually kept.

Error coding appends extra check bits, computed from the data by a rule, to detect and correct bits flipped by noise. A single parity bit (minimum distance 2) detects a single-bit error, and a code with minimum Hamming distance 3 or more (for example Hamming (7,4)) locates and corrects a single-bit error. The farther apart the valid codewords, the stronger the code, but the price is a code rate R = k/n below 1. This is the constructive side of Shannon's capacity theorem.

Closing the communications track

Starting from why we modulate, this track has followed one message all the way along its path. The small swings of the baseband were loaded onto a carrier and lifted up the frequency axis (AM·FM), turned into numbers (sampling·PCM), and used as bits to shake a carrier (ASK·FSK·PSK). Then came the bandwidth ceiling, the measurement of noise and SNR, taming randomness with probability, Shannon's absolute limit, and finally codes that undo errors below that limit. Communication, in the end, is the art of handing a message across a noisy world without losing it.