## Turbo CodingWhen the 50th anniversary of the birth of Information Theory was celebrated at the 1998 IEEE International Symposium on Informa tion Theory in Boston, there was a great deal of reflection on the the year 1993 as a critical year. As the years pass and more perspec tive is gained, it is a fairly safe bet that we will view 1993 as the year when the "early years" of error control coding came to an end. This was the year in which Berrou, Glavieux and Thitimajshima pre sented "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes" at the International Conference on Communications in Geneva. In their presentation, Berrou et al. claimed that a combi nation of parallel concatenation and iterative decoding can provide reliable communications at a signal to noise ratio that is within a few tenths of a dB of the Shannon limit. Nearly fifty years of striving to achieve the promise of Shannon's noisy channel coding theorem had come to an end. The implications of this result were immediately apparent to all -coding gains on the order of 10 dB could be used to dramatically extend the range of communication receivers, increase data rates and services, or substantially reduce transmitter power levels. The 1993 ICC paper set in motion several research efforts that have permanently changed the way we look at error control coding. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

11 Coding Gain | 2 |

12 The Shannon Limit on Performance | 5 |

13 Turbo Coding | 6 |

Bibliography | 10 |

Binary Codes Graphs and Trellises | 11 |

22 Graphs and Trellises | 15 |

23 Labeled Trellises | 19 |

43 Generic Description for Concatenated Codes | 78 |

Bibliography | 85 |

BCE and PCE Performance | 89 |

52 Weight Enumerators and Performance Bounds | 96 |

53 BCE Information Weight Distribution | 102 |

54 PCE Information Weight Distribution | 106 |

55 Summary | 117 |

Bibliography | 118 |

24 Finite State Machines and BCEs | 20 |

241 Minimal Convolutional Encoders | 24 |

242 Systematic Encoders for Convolutional Codes | 27 |

243 The Number of Minimal Encoders | 28 |

25 Trellis Description of a Linear Block Code | 29 |

Bibliography | 33 |

Interleaving | 35 |

31 A Framework for Interleaving | 36 |

32 Block Interleavers | 37 |

321 Classical Block Interleavers | 38 |

33 Multiplex Interleavers | 39 |

331 Classical Convolutional Interleaves | 40 |

341 Decomposition of interleavers | 41 |

342 Interleaver Generator Matrices | 42 |

35 The Shuffle Interleaver | 44 |

36 Interleaver Parameters | 47 |

362 The Memory of an Interleaver | 48 |

363 The Spreading Factors of an Interleaver | 50 |

364 The Dispersion of an Interleaver | 52 |

37 Some Specific Block Interleavers | 53 |

372 WelchCostas Interleaves | 54 |

373 Other Algebraic Interleavers | 55 |

374 PN Random and sRandom Interleavers | 58 |

38 Simulation Results | 59 |

Bibliography | 62 |

Concatenated Codes | 65 |

411 The CCSDS Deep Space Telemetry Standard | 66 |

42 Parallel Concatenated Encoders | 77 |

Turbo Decoding | 121 |

62 Symbol Detection | 124 |

621 Detection by Partitions | 126 |

622 Channels and Sources | 130 |

63 Soft Symbol Detection A DMS over a DMC | 133 |

631 Derivations of Recursions for DMS over DMC | 135 |

632 Soft Symbol Detection FSM Encoder over a DMC | 138 |

64 The Generalized VA and the BCJR | 140 |

641 A Trellis Labeled by a Semiring | 141 |

642 The Generalized Viterbi Algorithm | 144 |

643 The Equivalence of the BCJR and the VA | 147 |

65 Turbo Decoding | 149 |

651 Basic Computation | 150 |

Final Detection Process | 156 |

66 Imperfectly Known Channels | 157 |

Bibliography | 162 |

Belief Propagation and Parallel Decoding | 165 |

71 Reasoning and Probabilistic Networks | 166 |

72 Beliefs and Belief Propagation | 173 |

722 Belief Propagation on Loopy Graphs | 179 |

73 Parallel Turbo Decoding | 182 |

731 The Basic Algorithm | 184 |

74 Variations on a Parallel Theme | 188 |

741 Detailed Descriptions of EP1 and EP2 | 190 |

75 Final Thoughts | 195 |

Bibliography | 196 |

199 | |

### Common terms and phrases

associated Bayesian Network BCE's BCJR algorithm belief propagation Berrou binary bit error rate Blocklength BPSK chapter classical block interleaver codewords coding gain component encoders compute Concatenated Codes convolutional codes D-separated de-interleaver decoder error decoding algorithms defined denote described directed graph Equation equivalent error control coding error events error-correcting coding example finite function given Glavieux Hamming code Hamming distance IEEE Transactions information bit information block information sequence Information Theory information weight IRWEF iterative decoding label Markov matrix McEliece memory messages metric modulation nodes non-catastrophic Note outer output Parallel Concatenated Encoder parallel mode parity partition path PCE's performance permutation polynomial probabilistic probability distribution puncturing random variable recursive serial concatenated Shannon limit shown in Figure soft decision spreading factors subsets symbol systematic IIR encoder tion Transactions on Information turbo coding Turbo Decoding vector Viterbi Algorithm Viterbi decoder weight enumerator weight-2