EC-23.4 Modern Codes: Turbo, Low-Density Parity-Check and Polar

What this is and why it exists

For forty years there was a gap of several decibels between what theory promised and what codes delivered.

Three families closed it, and all three now appear in standards a learner will meet. What they share is that decoding is iterative and approximate rather than exact, and that the structure is described by a graph.

This topic is about the idea rather than the derivations. The idea is what transfers, and the derivations belong in a course of their own.

The vocabulary

• Iterative decoding — repeatedly refining a decision using exchanged information.
• Extrinsic information — what one decoder learned that the other did not already know.
• Interleaver — the permutation that separates the two views of the data.
• Sparse matrix — a parity check matrix with very few non-zero entries.
• Tanner graph — the graph connecting bits to the checks they take part in.
• Belief propagation — passing probabilities along the edges of that graph.
• Channel polarisation — a transform making some channels reliable and others useless.
• Frozen bit — a position set to a known value because its channel is unreliable.
• Error floor — the level at which an iterative decoder's improvement flattens.

The mental model

Iterative decoding is the shared idea. Two decoders each work on a differently arranged view of the same data. Each passes to the other only what it learned that the other did not already know. On the next pass, each does better. Nothing guarantees this converges, and in practice it converges remarkably well.

The turbo construction is the first realisation. Take two ordinary convolutional codes, and feed the second one an interleaved version of the same information. The interleaver is what makes the two decoders' errors independent enough for the exchange to help. Two mediocre codes together become far stronger than either alone.

Low-density parity-check codes take the graph view directly. A sparse parity check matrix is drawn as a graph connecting bits to checks. Decoding passes probabilities along the edges. Each check tells its bits what it thinks they should be, each bit combines what it hears, and this repeats. The sparsity is what keeps each message cheap.

Polar codes come from a different idea. A transform turns a set of identical channels into a set where some are almost perfect and the rest almost worthless. Information goes only on the good ones, and the bad ones carry known values. It was the first construction proved to reach capacity.

The practical caution is the error floor. Iterative decoders often improve rapidly and then flatten at an error rate well above zero. For voice that is irrelevant; for storage it is fatal. Knowing whether an application cares is part of choosing a code.

Finally, standards choose on decoding complexity, latency and flexibility of rate as much as on raw performance. Reading a standard's choice in that light explains decisions that otherwise look arbitrary.

What you should now be able to explain or do

• Describe iterative decoding as an exchange of extrinsic information.
• Say what the interleaver contributes to a turbo code.
• Describe a low-density code as a graph and say what passes along its edges.
• Explain polarisation and what a frozen bit is for.
• Say what an error floor is and which applications it rules a code out of.
• Explain why a standards body may choose a weaker code on purpose.

Check yourself