Turbo Codes

For decades after Shannon established the theoretical limits of reliable communication, practical codes could not approach the Shannon capacity limit without enormous complexity. Turbo codes, introduced by Berrou, Glavieux, and Thitimajshima in 1993, shattered this barrier by coming within a fraction of a decibel of the Shannon limit using a cleverly structured parallel concatenation of two convolutional codes with an iterative decoding algorithm. They revolutionized 3G, 4G LTE, and deep space communications.

Core Concept of Turbo Codes

Turbo codes use parallel concatenation of two Recursive Systematic Convolutional (RSC) encoders. The input message u is fed directly to Encoder 1, producing parity bits p1. The same message u is also passed through an interleaver (which randomly permutes the bit order) and then fed to Encoder 2, producing parity bits p2. The transmitted codeword consists of the systematic bits u, parity p1, and parity p2, giving a base code rate of 1/3. In practice, puncturing is used to raise the rate to 1/2 by periodically discarding some parity bits.

The reason RSC encoders are used instead of standard non-recursive convolutional encoders is that RSC codes produce codewords with higher effective free distance for low-weight input sequences. In a non-recursive encoder, a single 1 bit followed by zeros produces a finite weight codeword. In an RSC encoder, that same input causes the output weight to grow without bound (until the register is flushed), significantly improving the minimum distance of the code.

The interleaver is the key innovation of turbo codes. By interleaving, the two encoders see very different input patterns for the same message. A low-weight codeword for Encoder 1 will correspond to a high-weight input for Encoder 2, producing a high-weight parity sequence p2. Together, the two parity streams guarantee that all possible input sequences produce codewords with high total weight, translating directly to low bit error rate at the receiver.

Mathematical Expression

Turbo decoding uses the BCJR algorithm (also called MAP or SISO algorithm) as the inner decoder. Each SISO decoder computes the Log Likelihood Ratio (LLR) for each bit, given the received channel values and the a priori information from the other decoder. The LLR for bit u_k is:

• L(u_k) = L_a(u_k) + L_c . y_k + L_e(u_k)
• L_a = a priori LLR (extrinsic info from the other decoder, initialized to zero)
• L_c . y_k = channel LLR from received systematic bit y_k
• L_e = extrinsic LLR produced by this decoder, passed (after de/re-interleaving) to the other decoder

The two decoders exchange extrinsic information across multiple iterations. In each iteration, Decoder 1 passes its extrinsic output (after interleaving) to Decoder 2 as a priori input. Decoder 2 processes it and passes its extrinsic output (after de-interleaving) back to Decoder 1. After typically 6 to 18 iterations, the LLRs converge and a hard decision is made by taking the sign of each LLR. This iterative exchange resembles the cycling of a turbo engine, which inspired the name.

Practical Understanding

Turbo codes achieve performance within 0.5 dB of the Shannon limit for long block lengths (several thousand bits) on AWGN channels. This was considered nearly miraculous in 1993 when previous practical codes were 2 to 3 dB away. The 3G WCDMA and CDMA2000 standards adopted turbo codes for data channels, and 4G LTE uses them for all data transport blocks above a certain size threshold.

The main limitation of turbo codes is error floor: at very low BER (below 10^-5 or 10^-6), the BER curve stops declining steeply and levels off. This is caused by low-weight codewords associated with specific input patterns. The interleaver design critically affects where the error floor appears. For applications requiring BER below 10^-9 (such as optical fiber), LDPC codes are preferred over turbo codes due to a lower error floor. In 5G NR, LDPC replaced turbo codes for data channels for this reason.

Given:
Turbo code: Rate 1/3, K=3 RSC encoders
Message block length: N = 1000 bits
Eb/N0 required at BER = 10^-5 using turbo code ≈ 1.0 dB
Eb/N0 required at BER = 10^-5 uncoded BPSK ≈ 9.6 dB

Why this formula applies:
Coding gain = improvement in required Eb/N0 due to error correction coding.

Formula:
Coding gain (dB) = Eb/N0 (uncoded) - Eb/N0 (coded) [at same BER target]

Substitution:
Coding gain = 9.6 dB - 1.0 dB

Calculation:
Coding gain = 8.6 dB

Spectral efficiency check:
Code rate R = 1/3
So bandwidth requirement increases by factor 3 vs uncoded
Bandwidth-power tradeoff: 8.6 dB power saving costs 3x bandwidth

Final Answer:
Coding gain = 8.6 dB at BER = 10^-5 for rate 1/3 turbo code with N=1000 bits
This approaches Shannon limit (theoretical max gain at this rate and BER ≈ 9.0 dB)

Exam Tip: Turbo code base rate = 1/3 (u + p1 + p2). After puncturing it becomes 1/2. Key advantage over Viterbi-decoded convolutional codes is near-Shannon-limit performance at long block lengths. Main disadvantage is high decoding latency due to iterations.

Mechanism of Iterative Decoding

• Decoder 1 uses systematic bits and p1 along with a priori LLR from Decoder 2. It outputs extrinsic LLR for each bit.
• Extrinsic output of Decoder 1 is interleaved and fed as a priori input to Decoder 2. Decoder 2 uses it with p2 to produce its own extrinsic output.
• Extrinsic output of Decoder 2 is de-interleaved and fed back to Decoder 1. This completes one full iteration.
• After 6 to 18 iterations (typical), LLRs converge and hard decisions are made. More iterations give diminishing BER improvement beyond about 10 to 12 iterations.
• Convergence can be analyzed using EXIT (Extrinsic Information Transfer) charts, which plot mutual information transfer between SISO decoders as a function of a priori information quality.

Quick Revision

• Turbo code = parallel concatenation of two RSC encoders with an interleaver. Base rate = 1/3.
• RSC (Recursive Systematic Convolutional) encoder is used instead of non-recursive because it improves free distance for sparse input sequences.
• Interleaver ensures that a low-weight sequence for Encoder 1 maps to high-weight input for Encoder 2.
• Iterative decoding: two SISO (MAP/BCJR) decoders exchange extrinsic LLR information through an interleaver across multiple iterations.
• Performance: within 0.5 dB of Shannon limit for N > 1000 bits on AWGN.
• Error floor: BER stops improving below 10^-5 to 10^-6, which is why LDPC replaced turbo codes in 5G NR data channels.
• Exam trap: Turbo codes require many iterations and are high latency. They are not suitable for very short blocks where performance degrades.