Understanding Turbo Codes and Iterative Decoding

Turbo codes are a class of high-performance forward error correction (FEC) codes that revolutionized digital communications by enabling data transmission rates exceptionally close to the theoretical Shannon limit. By combining parallel convolutional encoders with an interleaver and employing an iterative decoding mechanism, turbo codes allow receivers to reconstruct original binary data streams with remarkable accuracy, even across channels with severe signal noise and interference.

The Structure of Turbo Codes

A standard turbo encoder processes an input sequence of binary digits (bits) using two constituent convolutional encoders separated by an interleaver:

1. Systematic Stream: The original binary input is transmitted directly without alteration.
2. First Parity Stream: The first convolutional encoder processes the binary input in its original sequence to produce a set of parity bits.
3. Interleaver: The binary input is rearranged into a pseudo-random order. This step decorrelates the sequence and prevents localized bursts of channel noise from affecting both encoders simultaneously.
4. Second Parity Stream: The second convolutional encoder processes the interleaved binary sequence to generate a second set of parity bits.

These three components—the systematic bits and both sets of parity bits—are combined and transmitted across the communication channel.

How Iterative Decoding Works

At the receiving end, channel noise often corrupts the transmitted signal, turning discrete binary values into noisy, continuous analog samples. The turbo decoder interprets these samples using iterative decoding, which operates on probabilities rather than making immediate “hard” binary decisions (0 or 1).

1. Soft-Input Soft-Output (SISO) Decoders

The turbo decoder consists of two component decoders that work collaboratively using algorithms such as the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm or Maximum A Posteriori (MAP) estimation. These decoders accept soft channel information and output refined probability estimates known as Log-Likelihood Ratios (LLRs). An LLR represents the logarithm of the ratio of the probability that a bit is a 0 versus a 1.

2. Information Exchange and Feedback Loops

The iterative decoding cycle functions as follows:

• Decoder 1: Receives the noisy systematic data and the first parity stream to compute initial LLR values for each bit. It subtracts its inputs to isolate new statistical insights, known as extrinsic information.
• Interleaving: The extrinsic information from Decoder 1 is interleaved to match the shuffled structure of the second encoder.
• Decoder 2: Uses the interleaved systematic data, the second parity stream, and the extrinsic information provided by Decoder 1. It refines the probabilities and produces its own extrinsic information.
• Deinterleaving and Feedback: Decoder 2’s extrinsic information is deinterleaved back to the original bit order and fed back to Decoder 1 as a priori probability for the next cycle.

3. Convergence to Binary Decisions

This exchange repeats for a predetermined number of iterations (typically between 4 and 10) or until the probability values stabilize. With each cycle, the decoders cross-validate their estimates, systematically reducing uncertainty caused by noise.

Once the iterations are complete, the final LLRs undergo a hard threshold decision: positive values are resolved to binary 0 (or 1, depending on signaling convention), and negative values are resolved to the opposite binary state. This final step yields a clean, reconstructed binary data stream identical to the original transmission.