Coding theory
The constructive half of information-theory: given that Shannon proved good codes exist, build one that can actually be encoded and decoded. The subject is organised around a fifty-year embarrassment — the theorems arrived in 1948 and the codes that come close to them arrived in the mid-1990s — and its vocabulary exists to name degrees of failure.
Sourced from information-theory-inference-learning-algorithms, held in ../machine-learning-wiki
(see the provenance note on information-theory).
The taxonomy that organises the subject
MacKay's four terms, and the reason each is needed (ch. 11):
| Term | Definition |
|---|---|
| Very good | A family that achieves arbitrarily small error at any rate up to capacity |
| Good | Arbitrarily small error at some non-zero rate, possibly below capacity |
| Bad | Cannot achieve arbitrarily small error except by driving the rate to zero |
| Practical | Can be encoded and decoded in time and space polynomial in the blocklength |
The terms are independent, which is the whole problem. Repetition codes are practical and bad —
R₆₁ reaches a bit error rate of about 10⁻¹⁵ on a 10%-noise channel by spending sixty bits per bit.
Random codes are very good and not practical. For fifty years nothing was known to be both.
"Nearly all codes are good, but nearly all codes require exponential look-up tables for practical implementation of the encoder and decoder."
Linear codes, and why they are not the obstacle
An (N,K) block code is a list of 2^K codewords of length N; its rate is R = K/N. It is
linear when the codewords form a K-dimensional subspace of F₂^N, so encoding is a matrix
product t = Gᵀs (mod 2) and the codewords are exactly the solutions of Ht = 0 for the
parity-check matrix H. Nearly every established construction is linear —
error-correcting-code covers Hamming, Reed–Solomon, Reed–Muller, Goppa, convolutional.
Linearity is not what costs the Shannon limit: the channel coding theorem can be proved for linear
codes too (ch. 14, Very Good Linear Codes Exist), non-constructively as before. What costs is
decoding. Finding the maximum-likelihood s given Gᵀs + n = r is NP-complete (Berlekamp,
McEliece and van Tilborg 1978), so the subject narrows to families that admit a fast decoder.
The obsession the subject had to drop
Classical coding theory ranks a code by its minimum distance d — the smallest Hamming distance
between two codewords — because a decoder guaranteed to correct any t = ⌊(d−1)/2⌋ errors follows
immediately. Whence the search for perfect codes, whose spheres of radius t tile the space
exactly.
There are almost none. The complete list of nontrivial binary perfect codes is: the Hamming codes
(t = 1, rate → 1), the odd-blocklength repetition codes (rate → 0), and the single (23, 12)
Golay code correcting 3 errors. That is all of them. A ternary Golay code of length 11 was found
in 1947 by Juhani Virtakallio, a Finnish football-pool enthusiast, and published in a betting
magazine before the coding theorists got there.
The deeper finding is that the distance framing costs you half the channel. A bounded-distance
decoder returns the nearest codeword when it lies within t and declares failure otherwise. MacKay
computes what that refusal costs: for a good rate-R code the noise level a bounded-distance decoder
tolerates is exactly half the level Shannon's decoder tolerates, f_bd = f*/2. He does not treat
this as a technicality.
"This defeatist attitude is an example of worst-case-ism, a widespread mental ailment which this book is intended to cure. … You have to be able to decode way beyond the minimum distance of a code to get to the Shannon limit!"
The geometry behind it: near capacity the typical number of flipped bits is about fN and the
minimum distance is also about fN, so the decoding spheres overlap badly — each nearly contains its
neighbour's centre. That is survivable because in high dimensions the overlapping volume is a
vanishing fraction of either sphere, so the probability of landing in it is tiny. Guaranteed
correction of every pattern up to t and small average error are different objectives, and
Shannon's theorem is about the second. Which is why the codes that finally reached capacity are
decoded probabilistically, by inference on a graph, rather than by distance.
What the answer turned out to be
MacKay's own summary of chapter 11, three lines that describe every modern code:
"The best practical codes (a) employ very large block sizes; (b) are based on semi-random code constructions; and (c) make use of probability-based decoding algorithms."
Large blocks because the theorems are asymptotic. Semi-random construction because randomness is what made Shannon's average good, and structure is what makes decoding cheap — sparse random graphs supply both. Probabilistic decoding because exact decoding is NP-complete and approximate inference is not.
The families that satisfy all three: low-density-parity-check-code (Gallager 1962, forgotten, rediscovered 1995), turbo codes (Berrou, Glavieux and Thitimajshima, 1993), repeat–accumulate codes, and fountain-code for erasure channels.
Where this is used across the hub
../cryptography-wiki— Reed–Solomon codes, proximity gaps and list decoding appear there as the material a proof system is built from. That spoke owns the construction and its cost; the coding theorems and the classification of codes are here.../machine-learning-wiki— the decoder is the inference algorithm. monte-carlo-methods and the sum–product algorithm live in the same book for that reason.../embedded-iot-wikiand../platform-ops-wiki— erasure coding at the packet layer is fountain-code's subject; neither spoke pages it.
Related
information-theory · error-correcting-code · low-density-parity-check-code · fountain-code · noisy-channel-coding-theorem · abstract-algebra · information-theory-inference-learning-algorithms · mathematics · synthesis