CM · Noise and information

Error Coding

Shannon promised the error can be driven near zero below capacity, but not how. Learn that adding extra bits computed from the data by a rule lets you detect the bits noise flipped — and even pinpoint and correct which one went wrong.

A flipped bit, three codes respond

Tap none, parity, Hamming in turn. Faced with the same single-bit error, data alone cannot even notice it, one parity bit only detects it, and Hamming pinpoints which bit and corrects it.

Code length and minimum distance

n = 4, k = 4 · d_min = 1

No protection

Noise flips bits

As we saw, noise at the receiver occasionally flips a 0 to a 1 or a 1 to a 0. If you send the data bits bare, there is no way to tell whether a received 1011 was really 1011 or a one-bit-flipped 1001. Every 4-bit pattern is an equally plausible message, so you cannot even know an error happened.

Extra bits stand guard

Adding a check bit computed from the data by a rule changes everything. The simplest, a parity bit, is the XOR of all the data bits, keeping the number of ones always even. When noise flips any one bit the count turns odd, the parity check breaks, and the receiver knows an error occurred. But a single parity bit cannot say which bit went wrong.

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

Parity is the XOR of the data bits.

Choosedetect 1: d_min ?

Detecting one error needs minimum distance 2.

Distance makes correction

Picture codewords as points; a good code keeps the valid points far apart. The number of bit positions in which two codewords differ is their Hamming distance. If the minimum distance among all valid codewords is 2, a single-bit error can be detected; if it is 3, a single-bit error can even be corrected — because the corrupted word is still nearest its original codeword. Hamming(7,4) uses 3 check bits to pinpoint and fix any single error among 7 bits. The price is the code rate R = k/n = 4/7, paying 3 redundant bits for every 4 of information.

Fill incorrect 1: d_min ≥ ?

Correcting one error needs minimum distance 3.

On your ownR = kn = ?

The code rate is data bits over total bits.

Back to the first screen

With no code the flipped bit looked like valid data, leaving no trace — red; adding one parity bit raised a flag that something broke but not which bit — orange; and when Hamming’s check bits gathered the discrepancy, pinpointed that bit and flipped it back, it turned gold. The one thing to hear in error coding is this: spread the valid messages far apart with extra bits, and a message that noise nudged one step still falls back to the nearest original. This is how Shannon’s promise — reliability below capacity — is actually kept.

Error coding adds redundant check bits computed from the data by a rule, to detect and correct the bits noise flips. A single parity bit (minimum distance 2) detects one error, and a code with minimum Hamming distance 3 or more (e.g. Hamming(7,4)) pinpoints and corrects one. The farther apart the valid codewords, the stronger the code, at the cost of 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, we have followed one message all the way here. We lifted a small baseband wiggle onto a carrier and up the frequency axis (AM, FM), turned it into numbers (sampling, PCM), shook a carrier with the bits (ASK, FSK, PSK), met the ceiling of bandwidth, measured noise and SNR, tamed randomness with probability, saw Shannon’s absolute limit, and at last undid the errors with codes below that limit. Communication, in the end, is the craft of handing a message across a noisy world without losing it.