This book provides a comprehensive overview of the subject of channel coding. It starts with a description of information theory, focusing on the quantitative measurement of information and introducing two fundamental theorems on source and channel coding. The basics of channel coding in two chapters, block codes and convolutional codes, are then discussed, and for these the authors introduce weighted input and output decoding algorithms and recursive systematic convolutional codes, which are used in the rest of the book. Trellis coded modulations, which have their primary applications in high spectral efficiency transmissions, are then covered, before the discussion moves on to an advanced coding technique called turbocoding. These codes, invented in the 1990s by C. Berrou and A. Glavieux, show exceptional performance. The differences between convolutional turbocodes and block turbocodes are outlined, and for each family, the authors present the coding and decoding techniques, together with their performances. The book concludes with a chapter on the implementation of turbocodes in circuits. As such, anyone involved in the areas of channel coding and error correcting coding will find this book to be of invaluable assistance.

Table of Contents:
Homage to Alain Glavieux xv Chapter 1. Information Theory 1 Gérard BATTAIL 1.1. Introduction: the Shannon paradigm 1 1.2. Principal coding functions 5 1.2.1. Source coding 5 1.2.2. Channel coding 6 1.2.3. Cryptography 7 1.2.4. Standardization of the Shannon diagram blocks 8 1.2.5. Fundamental theorems 9 1.3. Quantitative measurement of information 9 1.3.1. Principle 9 1.3.2. Measurement of self-information 10 1.3.3. Entropy of a source 11 1.3.4. Mutual information measure 12 1.3.5. Channel capacity 14 1.3.6. Comments on the measurement of information 15 1.4. Source coding 15 1.4.1. Introduction 15 1.4.2. Decodability, Kraft-McMillan inequality 16 1.4.3. Demonstration of the fundamental theorem 17 1.4.4. Outline of optimal algorithms of source coding 18 1.5. Channel coding 19 1.5.1. Introduction and statement of the fundamental theorem 19 1.5.2. General comments 20 1.5.3. Need for redundancy 20 1.5.4. Example of the binary symmetric channel 21 1.5.5. A geometrical interpretation 25 1.5.6. Fundamental theorem: Gallager’s proof 26 1.6. Channels with continuous noise 32 1.6.1. Introduction 32 1.6.2. A reference model in physical reality: the channel with Gaussian additive noise 32 1.6.3. Communication via a channel with additive white Gaussian noise 35 1.6.4. Channel with fadings 37 1.7. Information theory and channel coding 38 1.8. Bibliography 40 Chapter 2. Block Codes 41 Alain POLI 2.1. Unstructured codes 41 2.1.1. The fundamental question of message redundancy 41 2.1.2. Unstructured codes 42 2.2. Linear codes 44 2.2.1. Introduction 44 2.2.2. Properties of linear codes 44 2.2.3. Dual code 46 2.2.4. Some linear codes 50 2.2.5. Decoding of linear codes 51 2.3. Finite fields 53 2.3.1. Basic concepts 53 2.3.2. Polynomial modulo calculations: quotient ring 53 2.3.3. Irreducible polynomial modulo calculations: finite field 54 2.3.4. Order and the opposite of an element of F2[X]/(p(X)) 54 2.3.5. Minimum polynomials 59 2.3.6. The field of nth roots of unity 60 2.3.7. Projective geometry in a finite field 61 2.4. Cyclic codes 62 2.4.1. Introduction 62 2.4.2. Base, coding, dual code and code annihilator 63 2.4.3. Certain cyclic codes 68 2.4.4. Existence and construction of cyclic codes 74 2.4.5. Applications of cyclic codes 82 2.5. Electronic circuits 82 2.5.1. Basic gates for error correcting codes 82 2.5.2. Shift registers 83 2.5.3. Circuits for the correct codes 83 2.5.4. Polynomial representation and representation to the power of a primitive representation for a field 87 2.6. Decoding of cyclic codes 88 2.6.1. Meggitt decoding (trapping of bursts) 88 2.6.2. Decoding by the DFT 89 2.6.3. FG-decoding 94 2.6.4. Berlekamp-Massey decoding 99 2.6.5. Majority decoding 105 2.6.6. Hard decoding, soft decoding and chase decoding 110 2.7. 2D codes 111 2.7.1. Introduction 111 2.7.2. Product codes 112 2.7.3. Minimum distance of 2D codes 112 2.7.4. Practical examples of the use of 2D codes 112 2.7.5. Coding 112 2.7.6. Decoding 113 2.8. Exercises on block codes 113 2.8.1. Unstructured codes 113 2.8.2. Linear codes 114 2.8.3. Finite bodies 117 2.8.4. Cyclic codes 119 2.8.5. Exercises on circuits 123 Chapter 3. Convolutional Codes 129 Alain GLAVIEUX and Sandrine VATON 3.1. Introduction 129 3.2. State transition diagram, trellis, tree 135 3.3. Transfer function and distance spectrum 137 3.4. Perforated convolutional codes 140 3.5. Catastrophic codes 142 3.6. The decoding of convolutional codes 142 3.6.1. Viterbi algorithm 143 3.6.2. MAP criterion or BCJR algorithm 156 3.6.3. SubMAP algorithm 169 3.7. Performance of convolutional codes 172 3.7.1. Channel with binary input and continuous output 173 3.7.2. Channel with binary input and output 180 3.8. Distance spectrum of convolutional codes 182 3.9. Recursive convolution codes 184 Chapter 4. Coded Modulations 197 Ezio BIGLIERI 4.1. Hamming distance and Euclidean distance 197 4.2. Trellis code 200 4.3. Decoding 201 4.4. Some examples of TCM 201 4.5. Choice of a TCM diagram 205 4.6. TCM representations 207 4.7. TCM transparent to rotations 209 4.7.1. Partitions transparent to rotations 211 4.7.2. Transparent trellis with rotations 212 4.7.3. Transparent encoder 213 4.7.4. General considerations 215 4.8. TCM error probability 215 4.8.1. Upper limit of the probability of an error event 215 4.8.2. Examples 226 4.8.3. Calculation of áfree 228 4.9. Power spectral density 232 4.10. Multi-level coding 234 4.10.1. Block coded modulation 235 4.10.2. Decoding of multilevel codes by stages 237 4.11. Probability of error for the BCM 238 4.11.1. Additive Gaussian channel 239 4.11.2. Calculation of the transfer function 240 4.12. Coded modulations for channels with fading 241 4.12.1. Modeling of channels with fading 241 4.12.2. Rayleigh fading channel: Euclidean distance and Hamming distance 247 4.13. Bit interleaved coded modulation (BICM) 251 4.14. Bibliography 253 Chapter 5. Turbocodes 255 Claude BERROU, Catherine DOUILLARD, Michel JÉZÉQUEL and Annie PICART 5.1. History of turbocodes 255 5.1.1. Concatenation 256 5.1.2. Negative feedback in the decoder 256 5.1.3. Recursive systematic codes 258 5.1.4. Extrinsic information 258 5.1.5. Parallel concatenation 259 5.1.6. Irregular interleaving 260 5.2. A simple and convincing illustration of the turbo effect 260 5.3. Turbocodes 265 5.3.1. Coding 265 5.3.2. The termination of constituent codes 272 5.3.3. Decoding 275 5.3.4. SISO decoding and extrinsic information 280 5.4. The permutation function 287 5.4.1. The regular permutation 288 5.4.2. Statistical approach 290 5.4.3. Real permutations 291 5.5. m-binary turbocodes 297 5.5.1. m-binary RSC encoders 298 5.5.2. m-binary turbocodes 300 5.5.3. Double-binary turbocodes with 8 states 302 5.5.4. Double-binary turbocodes with 16 states 303 5.6. Bibliography 304 Chapter 6. Block Turbocodes 307 Ramesh PYNDIAH and Patrick ADDE 6.1. Introduction 307 6.2. Concatenation of block codes 308 6.2.1. Parallel concatenation of block codes 309 6.2.2. Serial concatenation of block codes 313 6.2.3. Properties of product codes and theoretical performances 318 6.3. Soft decoding of block codes 323 6.3.1. Soft decoding of block codes 324 6.3.2. Soft decoding of block codes (Chase algorithm) 326 6.3.3. Decoding of block codes by the Viterbi algorithm 334 6.3.4. Decoding of block codes by the Hartmann and Rudolph algorithm 338 6.4. Iterative decoding of product codes 340 6.4.1. SISO decoding of a block code 341 6.4.2. Implementation of the weighting algorithm 345 6.4.3. Iterative decoding of product codes 347 6.4.4. Comparison of the performances of BTC 349 6.5. Conclusion 367 6.6. Bibliography 367 Chapter 7. Block Turbocodes in a Practical Setting 373 Patrick ADDE and Ramesh PYNDIAH 7.1. Introduction 373 7.2. Implementation of BTC: structure and complexity 373 7.2.1. Influence of integration constraints 373 7.2.2. General architecture and organization of the circuit 376 7.2.3. Memorizing of data and results 380 7.2.4. Elementary decoder 384 7.2.5. High flow structure 392 7.3. Flexibility of turbo block codes 397 7.4. Hybrid turbocodes 404 7.4.1. Construction of the code 404 7.4.2. Binary error rates (BER) function of the signal-to-noise ratio in a Gaussian channel 406 7.4.3. Variation of the size of the blocks 408 7.4.4. Variation of the total rate 409 7.5. Multidimensional turbocodes 409 7.6. Bibliography 412 List of Authors 415 Index 417