Librería Portfolio

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