The near-Shannon-limit codes that revolutionized digital communications and proved that Shannon's theoretical limits were practically achievable.
The 1993 ICC paper that shocked the world and the history behind parallel concatenation.
RSC encoders, interleavers, and the parallel concatenated structure.
Iterative MAP decoding, extrinsic information, and the turbo principle.
EXIT charts, convergence, waterfall/floor regions, and puncturing.
3G, 4G, deep space, satellite — turbo codes in the real world.
How turbo codes transformed coding theory and inspired modern codes.
ICC 1993, Geneva — Claude Berrou, Alain Glavieux, and Punya Thitimajshima presented:
"Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes"
Achieved BER = 10-5 at Eb/N0 = 0.7 dB from Shannon limit — with a practical decoder!
Initial reaction: disbelief. Many attendees assumed the results were wrong. It took months of independent verification.
| Rate | 1/2 |
| Block length | 65,536 bits |
| Iterations | 18 |
| Eb/N0 | 0.7 dB from capacity |
| Decoder | Iterative MAP |
For a rate-1/2 code on AWGN, Shannon limit is Eb/N0 = 0.187 dB.
Before turbo codes, the best practical codes operated 2-3 dB away from this limit.
Turbo codes achieved ~0.7 dB gap — an extraordinary leap.
| Code | Gap (dB) |
|---|---|
| Uncoded BPSK | ~9.6 |
| Convolutional (K=7) | ~3.0 |
| Concatenated RS+Conv | ~2.0 |
| Turbo (1993) | ~0.7 |
| Turbo (optimized) | ~0.3 |
A turbo code is a parallel concatenation of two (or more) constituent convolutional encoders, separated by an interleaver.
Transmitted codeword: [u, p1, p2] — systematic bits + two sets of parity bits.
Base rate = 1/3 (before puncturing). The systematic nature is crucial for iterative decoding.
Feedback in the encoder creates an infinite impulse response, ensuring that low-weight inputs produce high-weight outputs.
This is key — non-recursive encoders allow low-weight codewords that limit performance.
The input bits appear directly in the output. This enables the iterative decoder to exchange extrinsic information about the same set of information bits.
Typical generators for turbo codes:
| Standard | g0 | g1 | K |
|---|---|---|---|
| 3GPP | 138 | 158 | 4 |
| CCSDS | 238 | 338 | 5 |
| DVB-RCS | 138 | 158 | 4 |
def rsc_encode(data, g0=0b1101, g1=0b1111, K=4):
"""RSC encoder for 3GPP turbo code (octal 13, 15)"""
state = 0
systematic = []
parity = []
num_states = K - 1
for bit in data:
# Feedback: XOR input with feedback taps
fb = bit
for i in range(num_states):
if (g0 >> (i + 1)) & 1:
fb ^= (state >> i) & 1
# Parity output
p = fb
for i in range(num_states):
if (g1 >> (i + 1)) & 1:
p ^= (state >> i) & 1
systematic.append(bit)
parity.append(p)
# Shift state register
state = ((state >> 1) | (fb << (num_states - 1))) & ((1 << num_states) - 1)
return systematic, parityThe interleaver π permutes the input sequence before feeding it to the second encoder. This is what gives turbo codes their power — it decorrelates the inputs to the two encoders.
If input pattern has low weight through Encoder 1, the interleaver scrambles it so Encoder 2 likely produces high-weight parity.
Result: the combined codeword almost always has high weight — good minimum distance on average.
| Type | Properties |
|---|---|
| Random | Best performance, hard to implement |
| S-random | Random with spread constraint |
| QPP | Quadratic permutation polynomial — 3GPP |
| Block | Simple but suboptimal |
The interleaver design is critical: a poor interleaver can waste 1-2 dB of performance. 3GPP standardized QPP interleavers for deterministic, parallelizable operation.
import numpy as np
def turbo_encode(data, interleaver_perm):
"""
Complete turbo encoder: 2 RSC encoders + interleaver
Returns: systematic bits, parity1, parity2
"""
N = len(data)
# Encoder 1: operates on original data
sys1, parity1 = rsc_encode(data)
# Interleave the data
interleaved = [data[interleaver_perm[i]] for i in range(N)]
# Encoder 2: operates on interleaved data
_, parity2 = rsc_encode(interleaved)
# Overall rate = N / (N + N + N) = 1/3 before puncturing
return sys1, parity1, parity2
def generate_random_interleaver(N):
"""Generate a random interleaver permutation"""
perm = list(range(N))
np.random.shuffle(perm)
return perm
# Example usage
N = 1024
data = np.random.randint(0, 2, N).tolist()
perm = generate_random_interleaver(N)
sys_bits, p1, p2 = turbo_encode(data, perm)
print(f"Input: {N} bits -> Output: {3*N} bits (rate 1/3)")Trellis termination: each encoder must be driven to the zero state. 3GPP uses tail-biting to avoid rate loss from termination bits.
Each decoder produces soft outputs (log-likelihood ratios), not hard decisions. This is essential for iterative improvement.
The BCJR algorithm (Bahl, Cocke, Jelinek, Raviv, 1974) computes the a posteriori probability (APP) for each bit given the entire received sequence.
Forward recursion through the trellis. Probability of being in state s at time k given past observations.
Branch metrics from the channel observations and a priori information.
Backward recursion through the trellis. Probability from future observations.
Complexity: O(N · 2K-1) per iteration — linear in block length, exponential in constraint length. This is why short constraint lengths (K=4) are preferred.
Only extrinsic information is passed between decoders — information derived from the code constraints and parity, not from the systematic channel observation.
Passing the full LLR would cause positive feedback — the decoder would reinforce its own previous decisions, leading to overconfident wrong answers.
Lextrinsic = Ltotal - Lchannel - La priori
This is "new information" that one decoder has learned from its parity bits, which the other decoder hasn't seen yet.
The statistical independence assumption between the two decoders' extrinsic outputs is only approximate — it degrades with iterations, leading to diminishing returns.
Named after the turbo engine: exhaust gases (extrinsic information) are fed back to boost performance, just as a turbocharger recycles exhaust to compress intake air.
Iteration 1: Each decoder works with only channel information. Performance is modest.
Iteration 2-3: Decoders begin sharing useful extrinsic info. Rapid improvement.
Iteration 4-8: Refinement phase. Diminishing returns per iteration.
Iteration 8+: Convergence. Little further improvement.
Typical BER by Iteration
| Iteration | BER |
|---|---|
| 1 | 10-1 |
| 2 | 10-2 |
| 4 | 10-3 |
| 8 | 10-5 |
| 18 | 10-6 |
def turbo_decode(y_sys, y_p1, y_p2, interleaver, n_iterations=8):
"""
Iterative turbo decoder using log-MAP algorithm
"""
N = len(y_sys)
L_a = np.zeros(N) # A priori (initially zero)
for iteration in range(n_iterations):
# --- Decoder 1 ---
# Input: channel systematic + channel parity1 + a priori from Dec2
L_total_1 = map_decode(y_sys, y_p1, L_a)
# Extract extrinsic info: remove channel + a priori
L_e1 = L_total_1 - 2 * y_sys - L_a
# --- Interleave extrinsic for Decoder 2 ---
L_e1_interleaved = interleave(L_e1, interleaver)
y_sys_interleaved = interleave(y_sys, interleaver)
# --- Decoder 2 ---
L_total_2 = map_decode(y_sys_interleaved, y_p2, L_e1_interleaved)
L_e2 = L_total_2 - 2 * y_sys_interleaved - L_e1_interleaved
# --- De-interleave extrinsic for Decoder 1 ---
L_a = deinterleave(L_e2, interleaver)
# Final decision
L_final = deinterleave(L_total_2, interleaver)
decoded = (L_final < 0).astype(int)
return decodedThe log-MAP (max-log-MAP) approximation avoids costly exponentials while losing only ~0.1 dB compared to true MAP.
Introduced by Stephan ten Brink (2001), EXIT charts visualize the convergence behavior of iterative decoders by tracking mutual information.
X-axis: IA — mutual information of a priori input
Y-axis: IE — mutual information of extrinsic output
Plot transfer curves for both decoders (one flipped). Decoding converges if there's an open tunnel between the curves.
Open tunnel → convergence
Curves touch/cross → convergence failure
The tunnel width indicates how many iterations are needed — narrow tunnel means more iterations.
EXIT charts can be used to design better constituent codes by shaping the transfer curves.
At a threshold SNR, BER drops precipitously — the "waterfall." This is where iterative decoding converges successfully.
The waterfall threshold is predicted by EXIT chart analysis and density evolution.
At high SNR, BER decrease slows dramatically. Caused by low-weight codewords that the interleaver couldn't eliminate.
Floor typically at BER ~ 10-6 to 10-9 depending on interleaver design and block length.
| Factor | Waterfall | Floor |
|---|---|---|
| Block length ↑ | ↓ better | ↓ better |
| Iterations ↑ | ↓ better | No effect |
| Interleaver design | Moderate | Critical |
| Constraint length ↑ | Slight ↓ | ↓ better |
The error floor is turbo codes' Achilles' heel — it limits their use in applications requiring BER < 10-10 (e.g., fiber optics).
The base turbo code is rate 1/3. Puncturing — selectively deleting parity bits — increases the rate to match channel conditions.
Alternate which parity bits to keep:
Design puncturing so higher-rate patterns are subsets of lower-rate patterns. Enables HARQ: retransmit only the punctured bits.
| Rate | Use Case | Gap to Shannon |
|---|---|---|
| 1/3 | Cell edge, high protection | ~0.5 dB |
| 1/2 | Typical data | ~0.8 dB |
| 2/3 | Good channel | ~1.2 dB |
| 3/4 | High throughput | ~1.5 dB |
| 4/5 | Very good channel | ~2.0 dB |
Optimal bit-wise decisions. Requires log-sum-exp operations:
The correction term requires a lookup table. Best performance but highest complexity.
Approximation: drop the correction term.
~0.1-0.3 dB loss but dramatically simpler hardware. Most implementations use this.
Modified Viterbi that outputs reliability information. ~0.5 dB worse than MAP but even simpler. Used in early turbo decoder chips.
The trade-off: MAP gives optimal per-bit decisions; Max-Log-MAP trades ~0.2 dB for 50% complexity reduction; SOVA trades ~0.5 dB for further simplification.
First major standard to adopt turbo codes (Release 99, 1999).
| Constituent code | (13, 15)8, K=4 |
| Block sizes | 40 – 5114 bits |
| Interleaver | QPP |
| Iterations | Typically 6-8 |
Enhanced turbo code for higher throughput.
| Block sizes | 40 – 6144 bits |
| Interleaver | QPP (contention-free) |
| Max rate | ~0.95 with rate matching |
| HARQ | Chase combining + IR |
Near-capacity performance for the block sizes used in LTE (hundreds to thousands of bits).
Flexible rate matching via puncturing supports adaptive modulation and coding.
QPP interleaver enables parallel decoding — essential for high data rates.
5G NR replaced turbo codes with LDPC for data and polar codes for control — turbo codes' higher decoding latency became a bottleneck at 5G data rates.
CCSDS (Consultative Committee for Space Data Systems) adopted turbo codes in 2003 for deep space missions where every fraction of a dB matters.
| Constituent code | (23, 33)8, K=5 |
| Rates | 1/2, 1/3, 1/4, 1/6 |
| Block sizes | 1784, 3568, 7136, 8920 |
| Interleaver | Permutation polynomial |
Mars Reconnaissance Orbiter — high-res imagery from Mars
Messenger — Mercury orbit
New Horizons — Pluto flyby data
JWST — alongside RS codes
Signal from Mars: ~1 W transmitter, 225 million km distance. Every 0.5 dB saved doubles the data rate or halves the antenna size needed on Earth.
Digital Video Broadcasting — Return Channel via Satellite uses turbo codes for the return link from user terminals.
Rates: 1/3, 2/5, 1/2, 2/3, 3/4
Block sizes: 12 – 216 bytes
North American 3G standard independently adopted turbo codes with slightly different parameters than 3GPP.
Convolutional turbo codes (CTC) with duo-binary structure — processes pairs of bits for higher throughput.
MIL-STD-188-110C and Link 16 use turbo codes for low-SNR tactical communications.
| Property | Convolutional | RS + Conv | Turbo |
|---|---|---|---|
| Gap to Shannon | 3-4 dB | 2-3 dB | 0.3-0.7 dB |
| Decoding | Viterbi (hard) | Algebraic + Viterbi | Iterative MAP (soft) |
| Latency | Low | Medium | High (iterative) |
| Error Floor | None | Very low | Exists (~10-7) |
| Complexity | O(2K) | O(n2) + O(2K) | O(N · 2K · I) |
| Flexibility | Fixed rate | Fixed rate | Rate-compatible |
Turbo codes' weakness: the error floor and high decoding latency. These drove the search for alternatives — leading to the rediscovery of LDPC codes and invention of polar codes.
Coding theory was considered a "mature" field. Shannon's limit seemed a theoretical ideal, forever out of practical reach.
Research funding was declining. The field was losing momentum.
Iterative decoding was the breakthrough concept — not just turbo codes themselves. The idea that simple decoders exchanging soft information could approach optimality.
Rediscovery of LDPC codes (1996)
Turbo equalization
Iterative MIMO detection
Turbo source-channel coding
EXIT chart analysis framework
Factor graph / message passing unification
"Turbo codes didn't just give us a better code — they gave us a new way of thinking about decoding." — David Forney
| Year | Milestone |
|---|---|
| 1974 | BCJR algorithm published (foundation for MAP decoding) |
| 1993 | Berrou, Glavieux, Thitimajshima present turbo codes at ICC |
| 1995 | Independent verification; turbo code theory develops rapidly |
| 1999 | 3GPP Release 99 (UMTS) adopts turbo codes |
| 2000 | CDMA2000 standard adopts turbo codes |
| 2001 | EXIT charts introduced by ten Brink |
| 2003 | CCSDS adopts turbo codes for deep space |
| 2008 | 3GPP LTE Release 8 uses enhanced turbo codes |
| 2018 | 5G NR replaces turbo codes with LDPC/Polar |
Turbo codes reigned as the state-of-the-art for 25 years — an extraordinary run in a fast-moving field. Their iterative decoding principle lives on in every modern communication system.