What Is Iterative Decoding?

Iterative decoding is a class of algorithms for correcting transmission errors in digital communication systems by passing probabilistic information back and forth between decoding components until the most likely codeword is identified. The approach works by treating the decoding problem as inference on a graphical model, where each iteration refines soft estimates of the transmitted bits based on constraints imposed by the code structure. Unlike one-pass maximum-likelihood decoding, which becomes computationally intractable for long codes, iterative methods achieve near-optimal performance at manageable complexity.

The technique traces its modern roots to two parallel developments in the early 1990s. Claude Berrou and colleagues introduced turbo codes in 1993, demonstrating error correction performance within a fraction of a decibel of the Shannon theoretical limit using two component codes exchanging soft information in alternating passes. Separately, David MacKay and Radford Neal revived Robert Gallager's 1963 work on low-density parity-check (LDPC) codes, showing that LDPC codes decoded iteratively also approached the Shannon limit. These results established iterative decoding as the central technique for practical channel coding.

Turbo Codes and Component Interleaving

Turbo codes use two or more convolutional encoders connected by a pseudorandom interleaver. At the receiver, two soft-input soft-output decoders exchange extrinsic information in repeated passes, with each decoder treating the other's output as a prior probability for the next iteration. The output of each decoder is a log-likelihood ratio expressing the probability that each transmitted bit was a zero or a one. After a fixed number of iterations, typically 6 to 18, the decoder commits to a hard decision. The IEEE Journal on Selected Areas in Communications editorial on turbo codes traces how this exchange of extrinsic information, rather than the full posterior, prevents the two decoders from reinforcing their own errors. Turbo codes are specified in 3GPP standards for 3G and 4G LTE data channels.

LDPC Codes and Belief Propagation

Low-density parity-check codes are linear block codes defined by sparse parity-check matrices. Decoding proceeds on a bipartite Tanner graph, where variable nodes represent transmitted bits and check nodes represent parity constraints. In each iteration, variable nodes and check nodes exchange messages expressing updated probability beliefs about the transmitted values. This message-passing procedure is the sum-product algorithm, also called belief propagation. A comparative analysis of LDPC codes, turbo codes, and polar codes over AWGN channels shows that LDPC codes typically converge to low bit-error rates in 20 to 50 iterations for moderate code lengths. The sparsity of the parity-check matrix keeps per-iteration complexity linear in the code length, making LDPC practical for very long codes. The 802.11n, 802.11ac, and DVB-S2 standards all use LDPC codes with iterative decoding.

Convergence and Code Design

The reliability of iterative decoding depends on the cycle structure of the Tanner graph and on the degree distributions of variable and check nodes. Short cycles in the graph cause messages to carry correlated information by the time they return to their origin node, degrading convergence. Code designers use density evolution and EXIT chart analysis to predict how belief estimates evolve across iterations and to select degree-distribution polynomials that drive error floors to acceptably low levels. An IEEE conference paper on iterative decoding in turbo, LDPC, and polar codes examines how design choices in graph structure affect iterative performance across these code families.

Applications

Iterative decoding has applications in a wide range of fields, including:

• Cellular wireless networks, where 5G NR uses LDPC codes for data channels and polar codes with successive cancellation list decoding for control channels
• Satellite communications and deep-space probes, where turbo codes provide reliable links at very low signal-to-noise ratios
• Magnetic and flash storage systems, where LDPC codes correct errors in high-density recording
• Optical fiber transmission, where soft-decision FEC based on iterative decoding extends reach
• Digital video broadcasting, where DVB-S2 and DVB-T2 standards specify LDPC-based iterative decoding