Trellis and Turbo Coding

Christian B. Schlegel currently holds the NSERC Industrial Research Chair in Wireless Information Transmission and Networking at Dalhousie University. He holds PhD and MS degrees from the University of Notre Dame. Dr. Schlegel has authored several books including Trellis Coding (1997, IEEE Press) and Trellis and Turbo Coding (2004 Wiley-IEEE). Lance C. Pérez is a Professor, Dean of Graduate Studies, and Associate Vice Chancellor for Academic Affairs at the University of Nebraska-Lincoln. He received his PhD and MS in electrical engineering at the University of Notre Dame. He co-authored Trellis and Turbo Coding ( 2004 Wiley-IEEE Press) with Christian Schlegel.

1 Introduction 1 1.1 Modern Digital Communications 1

1.2 The Rise of Digital Communications 4

1.3 Communication Systems 4

1.4 Error Control Coding 7

1.5 Bandwidth, Power, and Complexity 12

1.6 A Brief History - The Drive Towards Capacity 20

2 Communications Basics 27

2.1 The Probabilistic Viewpoint 27

2.2 Vector Communication Channels 29

2.3 Optimum Receivers 31

2.4 Matched Filters 33

2.5 Message Sequences 35

2.6 The Complex Equivalent Baseband Model 39

2.7 Spectral Behavior 44

2.8 Advanced Modulation Methods 46

2.8.1 OFDM 46

2.8.2 Multiple Antenna Channels (MIMO Channels) 48

2.9 A Communications System Case Study 53

2.10 Appendix 2.A 61

3 Trellis-Coded Modulation 67

3.1 An Introductory Example 67

3.2 Construction of Codes 71

3.3 Lattices 80

3.4 Lattice Formulation of Trellis Codes 86

3.5 Rotational Invariance 92

3.6 V.fast 99

3.7 The IEEE 802.3an Standard 101

3.8 Historical Notes 106

4 Trellis Representations 111

4.1 Preliminaries 111

4.2 The Parity-Check Matrix 112

4.3 Parity-Check Trellis Representations 113

4.4 Convolutional Codes and Their Trellis 115

4.5 Minimal Trellises 120

4.6 Minimum-Span Generator Matrices 124

4.7 Systematic Construction of the PC-Trellis 127

4.8 Tail-Biting Trellises 129

4.9 The Minimal Trellis of Convolutional Codes 133

4.10 Fundamental Theorems from Basic Algebra 139

4.11 Systematic Encoders 149

4.12 Maximum Free-Distance Convolutional Codes 151

4.13 The Squaring Construction and the Trellis of Lattices 154

4.14 The Construction of Reed-Muller Codes 161

4.15 A Decoding Example 163

4.16 Polar Codes and Their Relationship to RM Codes 166

Appendix 4.A 171

5 Trellis and Tree Decoding 179

5.1 Background and Introduction 179

5.2 Tree Decoders 181

5.3 The Stack Algorithm 183

5.4 The Fano Algorithm 185

5.5 The M-Algorithm 186

5.6 Maximum Likelihood Decoding 197

5.7 A Posteriori Probability Symbol Decoding 200

5.8 Log-APP and Approximations 207

5.9 Error Analysis and Distance Spectrum 211

5.10 Random Coding Analysis of Optimal Decoding 222

5.11 Random Coding Analysis of Sequential Decoding 232

5.12 Some Final Remarks 238

6 Low-Density Parity-Check Codes 249

6.1 Introduction 249

6.2 LDPC Codes and Graphs 251

6.3 LDPC Decoding via Message Passing 255

6.4 Analysis Techniques 259

6.4.1 (Error) Probability Evolution for Binary Erasure Channels 259

6.4.2 Error Mechanism of LDPCs on BECs 265

6.4.3 Binary Symmetric Channels and the Gallager Algorithms 266

6.4.4 The AWGN Channel 270

6.5 Code Families and Construction 281

6.5.1 Constructions with Permutation Matrices 281

6.5.2 Cycle Reduction Design 286

6.5.3 RS-based Construction 287

6.5.4 Repeat-Accumulate Codes 289

6.6 Encoding of LDPC Codes 291

6.6.1 Triangular LDPC Codes 292

6.6.2 Specialized LDPC Codes 295

6.6.3 Approximate Triangularization 296

Appendix 6.A 298

7 Error Floors 319

7.1 The Error Floor Problem 319

7.2 Dynamics of the Absorption Sets 323

7.3 Code Design for Low Error Floors 331

7.4 Impact of the Decoding Algorithm 335

7.5 Importance Sampling (IS) 336

7.6 Computing Error Rates via Importance Sampling 340

8 Turbo Coding: Basic Principles 351

8.1 Introduction 351

8.2 Parallel Concatenated Convolutional Codes 353

8.3 Distance Spectrum Analysis of Turbo Codes 356

8.4 The Free Distance of a Turbo Code 358

8.5 Weight Enumerator Analysis of Turbo Codes 364

8.6 Iterative Decoding of Turbo Codes 371

8.7 EXIT Analysis 376

8.8 Serial Concatenation 383

8.9 Cascaded Convolutional Codes 383

8.10 Weight Enumerator Analysis of SCCCs 385

8.11 Iterative Decoding and Performance of SCCCs 394

8.12 EXIT Analysis of Serially Concatenated Codes 397

8.13 Viewpoint 401

8.14 Turbo-Trellis-Coded Modulation 402

8.15 Serial Concatenation 406

8.16 EXIT Analysis of Serial TTCM 408

8.17 Differential-Coded Modulation 409

8.18 Concatenated Space-Time Coding 414

8.19 Bit-Interleaved Coded and Generalized Modulation 418

9 Turbo Coding: Applications 431

9.1 Interleavers 431

9.2 Turbo Codes in Telecommunication Standards 439

9.2.1 The Space Data System Standard 439

9.2.2 3G Wireless Standards 440

9.2.3 Digital Video Broadcast Standards 443

9.3 Product Codes and Block Turbo Decoding 446

9.4 Approximate APP Decoding 448

9.5 Product Codes with High-Order Modulations 451

9.6 The IEEE 802.16 Standard 453

9.7 Decoding of Polar Codes 454

9.8 Polar Code Performance and Outlook 458

10 Convolutional LDPC Codes and Spatial Coupling 465

10.1 Capacity: The Ultimate Limit 465

10.2 Low-Density Parity-Check Convolutional Codes 467

10.2.1 New LDPC Codes from Old 467

10.2.2 Decoding Convolutional LDPC Codes 472

10.3 Spatial Coupling: A General View 474

10.4 Spatial Coupling: Convergence Analysis 482

10.4.1 Problem Setup 482

10.4.2 Lyapunov Approach 483