Low-density parity-check code

A block code whose parity-check matrix H is sparse: every row and column has a small, fixed number of ones. A regular (j,k) Gallager code puts j ones in each column and k in each row and is otherwise constructed at random subject to that constraint. The rate-¼ example in the book has blocklength 16, twelve checks, j = 3, k = 4 — each transmitted bit takes part in three parity checks and each check forces four bits to sum to zero mod 2.

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

Invented, forgotten, rediscovered

Gallager published them in 1962. MacKay's account: they "were promptly forgotten by most of the coding theory community," were rediscovered in 1995, and turned out to be the best block codes known for Gaussian channels. The thirty-three-year gap is the sharpest fact in this corner of the subject — the construction was never lost or wrong, it was published before the machines that make its decoder cheap and before the turbo-code result (1993) that made anyone look again.

Why they work, and the catch

Theoretically. For any column weight j ≥ 3 these codes are good under an optimal decoder, and have good distance. Sequences in which j grows slowly with N (slowly enough that j/N → 0) are very good — arbitrarily small error at any rate up to capacity.

The catch, stated by MacKay in one sentence: "However, we don't have an optimal decoder, and decoding low-density parity-check codes is an NP-complete problem."

Practically. All the effective decoders are message-passing algorithms, the best being the sum–product algorithm — belief propagation on the code's factor graph, also called iterative probabilistic decoding. The decoding problem is written as an inference problem, find the x maximising P(x)·[Hx = z], and solved approximately. Sparsity is what makes each message cheap; the random construction is what keeps the code good. Approximate inference on a problem whose exact version is NP-complete is not a compromise here, it is the entire method.

How close to the limit

Density evolution gives thresholds for the sum–product decoder on a binary symmetric channel. For rate ½ the Shannon limit is a flip probability of f = 0.11; the regular families reach:

Regular codes therefore leave a visible margin, and the ways to close it are known: irregular constructions (varying the column weights) and codes over larger fields GF(q). On the rate-¼ Gaussian channel, where the Shannon limit is about 0.79 dB, MacKay's comparison chart puts an irregular GF(8) code at blocklength 48,000 in front, followed by the JPL turbo code and a regular GF(16) code — with the Galileo code, best known in 1992, well behind them all. As of the book's writing in 2003, better sparse-graph codes had already been built.

Note what the table is really saying: a family invented in 1962 and ignored, decoded by an approximate algorithm on a randomly generated graph, beat a code that needed a room of custom hardware.

Related

coding-theory · error-correcting-code · fountain-code · noisy-channel-coding-theorem · information-theory · information-theory-inference-learning-algorithms · mathematics · synthesis