Error-correcting code

A map from K source bits to N transmitted bits, chosen so the receiver can recover the source after the channel has damaged the transmission. Rate R = K/N; the whole subject is the trade between rate, error probability, and the cost of decoding.

Sourced from information-theory-inference-learning-algorithms, held in ../machine-learning-wiki (see the provenance note on information-theory).

The two codes everything is measured against

Repetition. Send each bit three times, decode by majority vote. On a channel flipping 10% of bits, R₃ cuts the bit error rate to about 3% — and cuts the rate to ⅓. Reaching 10⁻¹⁵ needs R₆₁. It works, it is practical, and it is the textbook example of a bad code family in the sense of coding-theory: the error goes to zero only as the rate goes to zero.

Hamming (7,4). Four source bits, three parity bits, blocklength 7, rate 4/7. Each parity bit checks a different subset of the source bits; the pattern of violated checks is the syndrome, and the syndrome names the flipped bit. One error per block is corrected exactly; two are not. Block error goes as 21f² and bit error as 9f² to leading order, so on the same 10% channel about 7% of decoded bits come out wrong — worse than R₃, at nearly twice the rate. Coding theory begins here, with Hamming, and most classical constructions are generalisations of it: BCH, Reed–Muller, Reed–Solomon, Goppa.

Linear codes and the decoding wall

A linear (N,K) code is a K-dimensional subspace of F₂^N: encode by t = Gᵀs (mod 2), recognise codewords by Ht = 0. Almost every established code is linear, because encoding is then a matrix product and the code is described by H rather than by a list of 2^K codewords.

Decoding is the wall. Maximum-likelihood decoding of a general linear code is NP-complete, so a usable family is one with a fast decoder attached, not merely a good set of codewords. Two classical routes around it:

• Convolutional codes — no blocks at all. Source bits run through a shift register of constraint length k and the transmitted stream is a linear function of the register state. A constraint length 7 convolutional code was the de-facto standard for satellite communication.
• Concatenation — treat encoder–channel–decoder as a super-channel with a lower error rate and code that. Voyager used a convolutional inner code with a Reed–Solomon outer code over eight-bit symbols. Galileo used the same shape with constraint length 15, which in 1992 was the best known rate-¼ code; JPL never published the details and decoding it required, in MacKay's words, "a room full of special-purpose hardware."

That is the state of the art the sparse-graph codes displaced within a decade — low-density-parity-check-code, turbo codes and fountain-code all beat the Galileo code while being decodable by message passing on ordinary hardware.

What "good" means here

Precisely, and not colloquially: a family is very good if it achieves arbitrarily small error at any rate up to capacity, good if it does so at some non-zero rate, bad otherwise, and practical if encoding and decoding are polynomial in N. Nearly all codes are good; nearly all codes need exponential lookup tables. The taxonomy and the fifty-year gap it describes are on coding-theory; the limit the taxonomy is measured against is on noisy-channel-coding-theorem.

Related

coding-theory · low-density-parity-check-code · fountain-code · noisy-channel-coding-theorem · information-theory · abstract-algebra · information-theory-inference-learning-algorithms · mathematics · synthesis