46.08.02 · information-theory / modern-codes

Turbo Codes: Parallel Concatenated Convolutional Codes and Iterative Decoding

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1-7.4; Berrou, Glavieux & Thitimajshima 1993 Near Shannon Limit Error-Correcting Coding and Decoding; Richardson & Urbanke 2008 Modern Coding Theory Ch. 1-2

Intuition Beginner

In 1993, three French engineers did something everyone thought was impossible. Claude Berrou, Alain Glavieux, and Punya Thitimajshima built a code that came within 0.5 dB of the Shannon limit — the theoretical best — using a surprisingly simple idea. They called it a "turbo code" because the decoder feeds information back to itself, like a turbocharger feeding exhaust back into an engine.

The idea is to take two simple encoders and run them in parallel on the same data, but with the bits rearranged between them. The first encoder reads the data in order. The second encoder reads the same data in a scrambled order (through an "interleaver"). Each encoder produces parity bits — extra information that helps detect and correct errors.

The decoder is where the magic happens. Instead of decoding all at once, it decodes iteratively. The first decoder does its best to recover the data, producing soft decisions — not just "this bit is 0 or 1" but "this bit is 0 with 87% confidence." It passes this soft information to the second decoder, which uses it as a starting point. The second decoder then passes its improved soft information back to the first. After several rounds, the two decoders converge on a consistent answer.

Each round of iteration improves the estimates, like two students checking each other's homework. The first student finds some errors and tells the second, who finds more and tells the first, and after a few passes the answer is correct. The key is that the interleaver ensures the two decoders make different kinds of mistakes, so they can correct each other.

Turbo codes transformed communications. They were adopted in 3G cellular standards (UMTS), satellite links, and deep-space communication (NASA's Mars rovers). The turbo principle — iterative exchange of soft information — is now the standard approach in all modern coding schemes.

Visual Beginner

Component	Role
RSC encoder 1	Encodes data in original order, produces parity bits
Interleaver	Scrambles data order for second encoder
RSC encoder 2	Encodes scrambled data, produces second set of parity bits
MAP decoder 1	Decodes using channel output + extrinsic info from decoder 2
MAP decoder 2	Decodes using interleaved channel output + extrinsic info from decoder 1
Iteration	Decoders exchange soft information for 5-18 rounds

Figure: A block diagram of a turbo encoder and decoder. The encoder shows the input data $u_{k}$ feeding into RSC encoder 1 (producing systematic bits $u_{k}$ and parity bits $p_{k}^{(1)}$ ) and, through an interleaver $Π$ , into RSC encoder 2 (producing parity bits $p_{k}^{(2)}$ ). The decoder shows two MAP decoder blocks connected in a loop, with the interleaver and de-interleaver between them. Arrows show extrinsic information flowing from decoder 1 to decoder 2 and back. Below the decoder, a plot of bit-error rate versus $E_{b} / N_{0}$ shows the turbo code performance curve: a sharp "waterfall" dropping from $1 0^{- 2}$ to $1 0^{- 6}$ within about 0.5 dB, sitting just 0.5 dB from the Shannon limit.

Worked example Beginner

A turbo code with rate $R = 1/2$ transmits a block of $N = 1000$ data bits. Each bit $u_{k}$ is encoded by two recursive systematic convolutional (RSC) encoders.

The first RSC encoder takes the data bits in order: $u_{1}, u_{2}, \dots, u_{1000}$ . It produces parity bits $p_{1}^{(1)}, p_{2}^{(1)}, \dots, p_{1000}^{(1)}$ . The second RSC encoder takes the interleaved data bits: $u_{Π (1)}, u_{Π (2)}, \dots, u_{Π (1000)}$ , where $Π$ is a random permutation. It produces parity bits $p_{1}^{(2)}, p_{2}^{(2)}, \dots, p_{1000}^{(2)}$ .

To get rate $R = 1/2$ , we puncture (delete) half the parity bits: keep only even-indexed parity bits from encoder 1 and odd-indexed parity bits from encoder 2. The transmitted codeword is: $u_{1}, p_{1}^{(1)}, u_{2}, p_{3}^{(1)}, u_{3}, p_{5}^{(1)}, \dots$ and so on, for a total of about 2000 transmitted symbols encoding 1000 data bits.

At the decoder, MAP decoder 1 receives the channel values for the systematic bits and encoder-1 parity bits. It computes log-likelihood ratios (LLRs) $L_{1} (u_{k})$ for each bit. It extracts the "extrinsic" part — the new information it learned beyond what the channel told it — and sends this to decoder 2 through the interleaver.

MAP decoder 2 receives the interleaved systematic bits, the encoder-2 parity bits, and the interleaved extrinsic information from decoder 1. It computes its own LLRs $L_{2} (u_{Π (k)})$ and sends extrinsic information back to decoder 1 through the de-interleaver.

After 8 iterations, the decisions stabilize. The decoder outputs the hard decisions: $\overset{u}{^}_{k} = 0$ if the final LLR is positive, $\overset{u}{^}_{k} = 1$ if negative. At an $E_{b} / N_{0}$ of 0.7 dB (just above the Shannon limit of 0.2 dB for rate 1/2), the bit-error rate drops below $1 0^{- 5}$ — practical reliability.

Check your understanding Beginner

Formal definition Intermediate+

Let $u = (u_{1}, u_{2}, \dots, u_{N})$ be the information block of binary data.

Definition (Recursive systematic convolutional encoder). A rate- $1/2$ RSC encoder with memory $m$ is defined by generator polynomials $(g_{1} (D), g_{2} (D))$ where $g_{1} (D) = 1$ (systematic output) and $g_{2} (D) = 1 + g^{(1)} D + \dots + g^{(m)} D^{m}$ (feedback/parity). The encoder state at time $k$ is $s_{k} = (s_{k}^{(1)}, \dots, s_{k}^{(m)})$ , updated by:

s_{k}^{(1)} = u_{k} \oplus g^{(1)} s_{k - 1}^{(1)} \oplus \dots \oplus g^{(m)} s_{k - 1}^{(m)},

with the parity output $p_{k} = s_{k}^{(1)}$ . The "recursive" part means the encoder has feedback: previous outputs feed back into the state update.

Definition (Parallel concatenation). A turbo code with block length $N$ and interleaver $Π : {1, \dots, N} \to {1, \dots, N}$ consists of:

RSC encoder 1 acting on $(u_{1}, \dots, u_{N})$ , producing parity $(p_{1}^{(1)}, \dots, p_{N}^{(1)})$ .
RSC encoder 2 acting on $(u_{Π (1)}, \dots, u_{Π (N)})$ , producing parity $(p_{1}^{(2)}, \dots, p_{N}^{(2)})$ .

The transmitted codeword includes the systematic bits $u$ and punctured parity bits.

Definition (Log-likelihood ratio). The LLR for bit $u_{k}$ given observations $y$ is:

L (u_{k}) = lo g \frac{Pr ( u _{k} = 0 ∣ y )}{Pr ( u _{k} = 1 ∣ y )} .

Positive LLR means bit 0 is more likely; negative means bit 1 is more likely. The magnitude indicates confidence.

Definition (Extrinsic information). The extrinsic LLR from decoder 1 about bit $u_{k}$ is:

L_{e}^{(1)} (u_{k}) = L^{(1)} (u_{k}) - L_{c} (u_{k}) - L_{a}^{(1)} (u_{k}),

where $L^{(1)} (u_{k})$ is the total output LLR, $L_{c} (u_{k})$ is the channel LLR, and $L_{a}^{(1)} (u_{k})$ is the a-priori LLR received from decoder 2. Extrinsic information is the new information produced by the decoder, excluding what it received.

Counterexamples to common slips

Turbo codes do not achieve the Shannon limit exactly. They get within 0.5 dB of it at practical block lengths. The gap is due to the suboptimality of iterative decoding (compared to optimal maximum-likelihood decoding) and the finite block length.
The BCJR algorithm is not the same as Viterbi. Viterbi finds the most likely sequence (hard decisions). BCJR computes the a-posteriori probability for each individual bit (soft decisions). Turbo decoding requires the soft-output BCJR, not Viterbi.
More iterations do not always help. After 8-18 iterations (depending on the code and channel conditions), the decoder converges and further iterations provide negligible improvement. The convergence is monitored by watching the LLR magnitudes stabilize.

Key theorem with proof Intermediate+

Theorem (BCJR / Forward-Backward algorithm). For a convolutional code with trellis states ${0, 1, \dots, 2^{m} - 1}$ and received sequence $y = (y_{1}, \dots, y_{N})$ , the a-posteriori LLR for bit $u_{k}$ is:

L (u_{k}) = lo g \frac{\sum _{(s^{'}, s) : u_{k} = 0} α _{k - 1} ( s ^{'} ) \cdot γ _{k} ( s ^{'} , s ) \cdot β _{k} ( s )}{\sum _{(s^{'}, s) : u_{k} = 1} α _{k - 1} ( s ^{'} ) \cdot γ _{k} ( s ^{'} , s ) \cdot β _{k} ( s )},

where the forward metric $α$ , backward metric $β$ , and branch metric $γ$ satisfy:

α_{k} (s) = s^{'} \sum α_{k - 1} (s^{'}) \cdot γ_{k} (s^{'}, s), α_{0} (s) = 1 [s = 0],

β_{k - 1} (s^{'}) = s \sum γ_{k} (s^{'}, s) \cdot β_{k} (s), β_{N} (s) = 1 [s = 0],

γ_{k} (s^{'}, s) = Pr (s_{k} = s, y_{k} ∣ s_{k - 1} = s^{'}) .

Proof sketch. The computation factors the joint probability:

Pr (s_{k - 1} = s^{'}, s_{k} = s, y) = Pr (s_{k - 1} = s^{'}, y_{1}^{k - 1}) \cdot Pr (s_{k} = s, y_{k} ∣ s_{k - 1} = s^{'}) \cdot Pr (y_{k + 1}^{N} ∣ s_{k} = s) .

The three factors are $α_{k - 1} (s^{'})$ , $γ_{k} (s^{'}, s)$ , and $β_{k} (s)$ respectively. The forward recursion computes $α$ from left to right, the backward recursion computes $β$ from right to left, and $γ$ is the branch metric determined by the trellis structure and the channel. Summing over all state transitions consistent with $u_{k} = 0$ gives the numerator; summing over $u_{k} = 1$ gives the denominator. $□$

Bridge. The BCJR algorithm builds toward the iterative turbo decoder by providing the soft-output MAP computation that each component decoder must perform. The forward-backward structure appears again in the sum-product algorithm for LDPC codes 46.08.01 as the same message-passing on a trellis (which is a chain-structured factor graph). The foundational reason turbo codes work is that the interleaver decorrelates the errors between the two decoders, ensuring that the extrinsic information exchanged is genuinely new — this is exactly the "turbo principle" of iterative refinement. The central insight is that two weak decoders, when coupled through iterative soft-information exchange, can collectively achieve near-optimal performance. Putting these together, the BCJR algorithm is the load-bearing component that turns a convolutional code from a hard-decision device into a soft-information generator, and the parallel concatenation with interleaving ensures that the soft information from each decoder is informative for the other.

Exercises Intermediate+

Exercise (hard, short answer).

Show that the extrinsic information $L_{e}$ is the correct quantity to pass between decoders. Specifically, show that if decoder 2 treats $L_{e}^{(1)}$ as a-priori information, the resulting LLR is $L^{(2)} = L_{c} + L_{a}^{(2)} + L_{e}^{(2)}$ where $L_{a}^{(2)} = L_{e}^{(1)}$ .

Answer

The total LLR from decoder 1 is $L^{(1)} = L_{c} + L_{a}^{(1)} + L_{e}^{(1)}$ . The extrinsic part $L_{e}^{(1)} = L^{(1)} - L_{c} - L_{a}^{(1)}$ strips out the channel information (which decoder 2 already has) and the a-priori information (which came from decoder 2, so feeding it back would create a feedback loop without new information).

Decoder 2 receives the channel LLR $L_{c}$ directly from the channel, plus $L_{e}^{(1)}$ as a-priori information (after interleaving). Its total output is $L^{(2)} = L_{c} + L_{e}^{(1)} + L_{e}^{(2)} = L_{c} + L_{a}^{(2)} + L_{e}^{(2)}$ where $L_{a}^{(2)} = L_{e}^{(1)}$ . This decomposition ensures each decoder contributes genuinely new information at each iteration.

Exercise (hard, short answer).

Trace one iteration of the turbo decoder on a tiny block of 4 bits. Suppose the transmitted data is $(0, 0, 0, 0)$ and the channel LLRs are $(+ 2.0, + 1.5, - 0.3, + 1.8)$ (bit 3 is wrong — negative LLR for a transmitted 0). The interleaver maps indices $(1, 2, 3, 4) \to (3, 1, 4, 2)$ . Show how decoder 1's extrinsic information for bit 3, after interleaving, helps decoder 2 correct the error.

Answer

Decoder 1 runs BCJR on the trellis with channel LLRs $(+ 2.0, + 1.5, - 0.3, + 1.8)$ and no a-priori information. The strong positive LLRs at positions 1, 2, 4 and the weak negative at position 3 create ambiguity. BCJR produces total LLRs roughly $(+ 2.5, + 2.0, + 0.5, + 2.3)$ . The extrinsic LLRs are $L_{e}^{(1)} = L^{(1)} - L_{c} = (+ 0.5, + 0.5, + 0.8, + 0.5)$ .

After interleaving: $L_e^{(1)}_\Pi = (+0.8, +0.5, +0.5, +0.5)$ (rearranged according to $Π$ ).

Decoder 2 sees the interleaved systematic channel LLRs: $(- 0.3, + 2.0, + 1.8, + 1.5)$ and the a-priori from decoder 1: $(+ 0.8, + 0.5, + 0.5, + 0.5)$ . For interleaved position 1 (which is original position 3), the channel says $- 0.3$ (bit 1) but the a-priori says $+ 0.8$ (bit 0). BCJR on decoder 2's trellis resolves this in favor of bit 0 because the surrounding positions strongly support all-zeros. The output for interleaved position 1 will be positive, correcting the error.

After de-interleaving, the extrinsic information from decoder 2 reinforces the correction at original position 3. In subsequent iterations, both decoders converge on the correct all-zeros codeword.

Lean formalization Intermediate+

Mathlib does not define convolutional codes, trellis structures, the BCJR algorithm, parallel concatenation with interleavers, or iterative turbo decoding. The Fin type and finite state machines exist, but there is no trellis representation (a directed graph labelled with input/output pairs), no forward-backward dynamic programming on a trellis, and no LLR computation. The interleaver (a permutation on ${1, \dots, N}$ ) can be represented as a Equiv.Perm (Fin N), but the turbo code construction and the iterative decoder are absent. A Codex.CodingTheory.TurboCodes module would need to define convolutional encoders as state machines with feedback, the trellis structure, the BCJR algorithm, and the iterative exchange of extrinsic information. This unit ships without formalization.

Advanced results Master

The EXIT chart analysis

The convergence of the turbo decoder can be visualised using the EXtrinsic Information Transfer (EXIT) chart, introduced by Stephan ten Brink in 1999. The EXIT chart plots the mutual information at the output of each decoder as a function of the mutual information at its input.

For decoder 1, the transfer characteristic is $I_{E_{1}} = T_{1} (I_{A_{1}}, E_{b} / N_{0})$ , where $I_{A_{1}}$ is the mutual information of the a-priori LLRs and $I_{E_{1}}$ is the mutual information of the extrinsic LLRs. Similarly for decoder 2: $I_{E_{2}} = T_{2} (I_{A_{2}}, E_{b} / N_{0})$ .

Since the extrinsic output of decoder 1 becomes the a-priori input of decoder 2 (after interleaving), and vice versa, the iterative process traces a trajectory between the two transfer curves. Convergence to zero error occurs when the two curves do not intersect before $I = 1$ — there is an open "tunnel" through which the iteration can reach perfect decoding.

The EXIT chart predicts the convergence threshold: the minimum $E_{b} / N_{0}$ at which the tunnel opens. For well-designed turbo codes, this threshold is within 0.5-1.0 dB of the Shannon limit. The EXIT chart also guides the design of component codes and interleavers by showing how changes to the constituent codes affect the tunnel shape.

The weight distribution and error floor

Turbo codes exhibit a characteristic "waterfall" region (rapid improvement in BER with small increases in $E_{b} / N_{0}$ ) followed by an "error floor" region (slow improvement at high $E_{b} / N_{0}$ ). The error floor is caused by low-weight codewords in the turbo code's weight distribution.

The interleaver determines which low-weight input sequences produce low-weight codewords. An input sequence of weight $w$ (with $w$ nonzero bits) produces a codeword whose parity weight depends on the positions of the nonzero bits. If the interleaver places these $w$ bits in positions that generate low parity weight for both encoders, the resulting codeword has low total weight and causes errors at high $E_{b} / N_{0}$ .

Designing interleavers that avoid low-weight codewords is the key to lowering the error floor. The S-random interleaver (diversity interleaver) ensures that any two positions within distance $S$ in the original sequence are mapped to positions at least $S$ apart in the interleaved sequence. This prevents the creation of low-weight codewords for input weights 2 and 3, which dominate the error floor.

The turbo principle beyond coding

The turbo principle — iterative exchange of soft information between coupled processors — extends far beyond channel coding:

Turbo equalisation: Iterative equalisation and decoding for channels with intersymbol interference. The equaliser and decoder exchange soft information, jointly combating ISI and noise.
Turbo synchronisation: Iterative estimation of carrier phase, timing, and channel parameters jointly with decoding.
Source-channel coding: Iterative decoding of the channel code and source code, exploiting residual redundancy in the source.
Multi-user detection: Iterative detection and decoding in CDMA systems, where the multi-user detector and the channel decoders exchange soft information.

In each case, the turbo principle transforms a joint estimation problem into an iterative procedure that decomposes into manageable subproblems. The convergence is governed by the same mutual-information transfer mechanism captured by the EXIT chart.

Synthesis. Turbo codes achieve near-Shannon-limit performance through parallel concatenation of two RSC codes with an interleaver, decoded by iterative exchange of extrinsic information via the BCJR algorithm — the central insight is that two weak decoders become strong when coupled through iterative soft-information exchange. The BCJR forward-backward computation is the foundational reason each decoder can produce soft outputs; the interleaver ensures the two decoders' errors are decorrelated, and this is exactly the mechanism that makes the extrinsic information genuinely informative. The EXIT chart analysis builds toward a general convergence theory for iterative decoders, where the mutual-information transfer curves determine the decoding threshold. The turbo principle generalises beyond coding to equalisation, synchronisation, and multi-user detection. Putting these together, the turbo code represents the engineering realisation of Shannon's coding theorem: a practical construction that approaches the theoretical limit through the iterative soft-information principle.

Full proof set Master

Proposition (LLR decomposition for turbo decoding). The total a-posteriori LLR $L (u_{k})$ from the BCJR algorithm decomposes as:

L (u_{k}) = L_{c} (u_{k}) + L_{a} (u_{k}) + L_{e} (u_{k}),

where $L_{c}$ is the channel LLR, $L_{a}$ is the a-priori LLR, and $L_{e}$ is the extrinsic LLR.

Proof. The BCJR algorithm computes:

L (u_{k}) = lo g \frac{\sum _{(s^{'}, s) : u_{k} = 0} α _{k - 1} ( s ^{'} ) γ _{k} ( s ^{'} , s ) β _{k} ( s )}{\sum _{(s^{'}, s) : u_{k} = 1} α _{k - 1} ( s ^{'} ) γ _{k} ( s ^{'} , s ) β _{k} ( s )} .

The branch metric decomposes as $γ_{k} (s^{'}, s) = P (u_{k}) \cdot p (y_{k} ∣ x_{k} (s^{'}, s))$ , where $x_{k} (s^{'}, s)$ is the transmitted symbol associated with the transition. In LLR form:

lo g γ_{k} (s^{'}, s) = const + \frac{1}{2} u_{k} L_{a} (u_{k}) + \frac{1}{2} L_{c} (u_{k}) \cdot (parity contribution) .

Summing over all transitions, the terms separate into three additive components: the channel contribution $L_{c}$ , the a-priori contribution $L_{a}$ , and the extrinsic contribution $L_{e}$ from the trellis structure. The extrinsic term captures information from the code constraints (the relationships between bits enforced by the convolutional structure) that is not available from the channel or the a-priori input alone. $□$

Proposition (Convergence of iterative decoding). Let $T_{1}$ and $T_{2}$ be the EXIT transfer functions of the two component decoders. If $T_{1} (I, E_{b} / N_{0}) > 1 - T_{2}^{- 1} (1 - I, E_{b} / N_{0})$ for all $I \in [0, 1)$ , then the iterative decoder converges to $I = 1$ (zero error).

Proof sketch. The iteration maps $I_{n + 1} = T_{2} (T_{1} (I_{n}))$ . The condition states that the composed map $T_{2} \circ T_{1}$ maps every $I < 1$ to a strictly larger value: $T_{2} (T_{1} (I)) > I$ . This means the mutual information is strictly increasing at each iteration. Since $I \leq 1$ , the sequence $I_{0}, I_{1}, I_{2}, \dots$ is bounded above by 1 and strictly increasing, hence converges. The only fixed point satisfying $T_{2} (T_{1} (I)) = I$ under the strict inequality condition is $I = 1$ . Therefore the decoder converges to zero error. $□$

Connections Master

46.08.01 — LDPC codes use belief propagation on a bipartite graph; turbo codes use BCJR on a trellis. Both are iterative soft-information decoders with the same threshold behaviour.
46.03.01 — Channel capacity provides the Shannon limit that turbo codes approach within 0.5 dB.
46.03.02 — Shannon's achievability proof shows codes exist; turbo codes are the first practical construction approaching the limit.
37.01.01 — The BCJR algorithm is a dynamic-programming computation on a Markov chain (the trellis), using the same forward-backward structure as hidden Markov model inference.
45.02.01 — The MAP criterion for turbo decoding is the Bayesian estimator that minimises symbol error rate, connected to the Neyman-Pearson framework for hypothesis testing.

Historical & philosophical context Master

Claude Berrou and Alain Glavieux developed turbo codes at the Ecole Nationale Superieure des Telecommunications de Bretagne (now Telecom Bretagne) in the early 1990s. Their 1993 ICC paper "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes" (with Punya Thitimajshima) reported a coding scheme that achieved a bit-error rate of $1 0^{- 5}$ at $E_{b} / N_{0} = 0.7$ dB on the AWGN channel for rate 1/2, within 0.5 dB of the Shannon limit (0.19 dB). The result was met with widespread scepticism — many researchers suspected an error in the simulation.

The BCJR algorithm that turbo decoding relies on was published twenty years earlier by Bahl, Cocke, Jelinek, and Raviv in "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate" (IEEE Transactions on Information Theory 20, 1974, 284-287). It was considered computationally impractical for real-time decoding because it requires forward and backward passes over the entire block, plus soft-output computation. Berrou and Glavieux's innovation was to use BCJR not as a standalone decoder but as a component in an iterative scheme, where the computational cost per iteration is moderate and the total cost (8-18 iterations) is feasible.

The turbo principle had been anticipated in the signal-processing literature (iterative equalisation by Douillard et al., 1995, and in the multiuser detection literature by Moher, 1993), but Berrou and Glavieux were the first to apply it to channel coding with dramatic results. The name "turbo" was chosen because the feedback loop of extrinsic information resembles a turbocharger.

Turbo codes were adopted in the 3GPP UMTS standard in 1999 for the forward and reverse link channels, replacing convolutional codes with Viterbi decoding. They were also adopted in the CCSDS standard for deep-space communication, the DVB-RCS standard for satellite return channels, and in IEEE 802.16 (WiMAX). In the 5G NR standard (2017), turbo codes were replaced by LDPC codes for the data channel (LDPC offers better throughput at high rates and lower latency for short blocks), but turbo codes remain in the 5G control channel.

The philosophical lesson is that the gap between information-theoretic limits and practical constructions can be closed not by building ever more complex algebraic codes but by embracing iterative processing of soft information. The turbo principle converts a hard optimisation problem (maximum-likelihood decoding of a concatenated code) into a sequence of tractable subproblems (MAP decoding of each component), and the iterative structure ensures that the subproblems collectively converge to a near-optimal solution.

Bibliography Master

@inproceedings{berrou-glavieux-thitimajshima1993,
  author    = {Berrou, C. and Glavieux, A. and Thitimajshima, P.},
  title     = {Near {Shannon} Limit Error-Correcting Coding and Decoding: {Turbo-Codes}},
  booktitle = {Proc. IEEE Int. Conf. Communications (ICC)},
  pages     = {1064--1070},
  year      = {1993},
}
@article{bahl-cocke-jelinek-raviv1974,
  author  = {Bahl, L. R. and Cocke, J. and Jelinek, F. and Raviv, J.},
  title   = {Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate},
  journal = {IEEE Transactions on Information Theory},
  volume  = {20},
  pages   = {284--287},
  year    = {1974},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{richardson-urbanke2008,
  author    = {Richardson, T. and Urbanke, R.},
  title     = {Modern Coding Theory},
  publisher = {Cambridge University Press},
  year      = {2008},
}
@article{tenbrink1999,
  author  = {ten Brink, S.},
  title   = {Convergence of Iterative Decoding},
  journal = {Electronics Letters},
  volume  = {35},
  pages   = {806--808},
  year    = {1999},
}
@article{berrou-glavieux1996,
  author  = {Berrou, C. and Glavieux, A.},
  title   = {Near Optimum Error Correcting Coding and Decoding: {Turbo-Codes}},
  journal = {IEEE Transactions on Communications},
  volume  = {44},
  pages   = {1261--1271},
  year    = {1996},
}

Prerequisites

46.08.01
46.03.01

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1 intro (turbo codes as concatenated codes with iterative decoding, the 1993 breakthrough)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1-7.4 (parallel concatenation, recursive systematic convolutional encoders, MAP/BCJR decoding, iterative exchange of extrinsic information)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1-7.4; Berrou, Glavieux & Thitimajshima 1993 Near Shannon Limit Error-Correcting Coding and Decoding; Richardson & Urbanke 2008 Modern Coding Theory Ch. 1-2

References

Berrou, C., Glavieux, A. & Thitimajshima, P. — Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes · Proceedings of IEEE International Conference on Communications (ICC 1993) Geneva, 1064-1070. Introduced turbo codes: parallel concatenation of two recursive systematic convolutional (RSC) codes with an interleaver between them, iterative decoding using the MAP/BCJR algorithm, demonstrated bit-error rate $1 0^{- 5}$ at $E_{b} / N_{0} = 0.7$ dB on the AWGN channel, within 0.5 dB of the Shannon limit for rate $R = 1/2$ .
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 7.1: channel coding context, the gap between algebraic codes and capacity. Turbo codes and LDPC codes as the two families that close this gap. The iterative decoding principle: exchange of soft information between component decoders.
Bahl, L. R., Cocke, J., Jelinek, F. & Raviv, J. — Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate · IEEE Transactions on Information Theory 20 (1974) 284-287. The BCJR (Bahl-Cocke-Jelinek-Raviv) algorithm for computing the a-posteriori probability of each bit given the entire received sequence. The forward-backward algorithm computes $Pr (s_{t} = i, s_{t + 1} = j ∣ y)$ for all states $i, j$ and times $t$ , giving the APP $L (b_{t} ∣ y) = lo g [Pr (b_{t} = 0∣ y) / Pr (b_{t} = 1∣ y)]$ in time $O (n \cdot ∣ states ∣)$ .
Richardson, T. & Urbanke, R. — Modern Coding Theory · Cambridge University Press (2008). Chapter 1: the turbo principle as iterative processing of soft information. Chapter 2: density evolution for turbo codes, the convergence condition, and the relation to the EXIT chart analysis.

Estimated time

beginner: 15m
intermediate: 50m
master: 90m