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 11.2 The Rise of Digital Communications 41.3 Communication Systems 41.4 Error Control Coding 71.5 Bandwidth, Power, and Complexity 121.6 A Brief History - The Drive Towards Capacity 202 Communications Basics 272.1 The Probabilistic Viewpoint 272.2 Vector Communication Channels 292.3 Optimum Receivers 312.4 Matched Filters 332.5 Message Sequences 352.6 The Complex Equivalent Baseband Model 392.7 Spectral Behavior 442.8 Advanced Modulation Methods 462.8.1 OFDM 462.8.2 Multiple Antenna Channels (MIMO Channels) 482.9 A Communications System Case Study 532.10 Appendix 2.A 613 Trellis-Coded Modulation 673.1 An Introductory Example 673.2 Construction of Codes 713.3 Lattices 803.4 Lattice Formulation of Trellis Codes 863.5 Rotational Invariance 923.6 V.fast 993.7 The IEEE 802.3an Standard 1013.8 Historical Notes 1064 Trellis Representations 1114.1 Preliminaries 1114.2 The Parity-Check Matrix 1124.3 Parity-Check Trellis Representations 1134.4 Convolutional Codes and Their Trellis 1154.5 Minimal Trellises 1204.6 Minimum-Span Generator Matrices 1244.7 Systematic Construction of the PC-Trellis 1274.8 Tail-Biting Trellises 1294.9 The Minimal Trellis of Convolutional Codes 1334.10 Fundamental Theorems from Basic Algebra 1394.11 Systematic Encoders 1494.12 Maximum Free-Distance Convolutional Codes 1514.13 The Squaring Construction and the Trellis of Lattices 1544.14 The Construction of Reed-Muller Codes 1614.15 A Decoding Example 1634.16 Polar Codes and Their Relationship to RM Codes 166Appendix 4.A 1715 Trellis and Tree Decoding 1795.1 Background and Introduction 1795.2 Tree Decoders 1815.3 The Stack Algorithm 1835.4 The Fano Algorithm 1855.5 The M-Algorithm 1865.6 Maximum Likelihood Decoding 1975.7 A Posteriori Probability Symbol Decoding 2005.8 Log-APP and Approximations 2075.9 Error Analysis and Distance Spectrum 2115.10 Random Coding Analysis of Optimal Decoding 2225.11 Random Coding Analysis of Sequential Decoding 2325.12 Some Final Remarks 2386 Low-Density Parity-Check Codes 2496.1 Introduction 2496.2 LDPC Codes and Graphs 2516.3 LDPC Decoding via Message Passing 2556.4 Analysis Techniques 2596.4.1 (Error) Probability Evolution for Binary Erasure Channels 2596.4.2 Error Mechanism of LDPCs on BECs 2656.4.3 Binary Symmetric Channels and the Gallager Algorithms 2666.4.4 The AWGN Channel 2706.5 Code Families and Construction 2816.5.1 Constructions with Permutation Matrices 2816.5.2 Cycle Reduction Design 2866.5.3 RS-based Construction 2876.5.4 Repeat-Accumulate Codes 2896.6 Encoding of LDPC Codes 2916.6.1 Triangular LDPC Codes 2926.6.2 Specialized LDPC Codes 2956.6.3 Approximate Triangularization 296Appendix 6.A 2987 Error Floors 3197.1 The Error Floor Problem 3197.2 Dynamics of the Absorption Sets 3237.3 Code Design for Low Error Floors 3317.4 Impact of the Decoding Algorithm 3357.5 Importance Sampling (IS) 3367.6 Computing Error Rates via Importance Sampling 3408 Turbo Coding: Basic Principles 3518.1 Introduction 3518.2 Parallel Concatenated Convolutional Codes 3538.3 Distance Spectrum Analysis of Turbo Codes 3568.4 The Free Distance of a Turbo Code 3588.5 Weight Enumerator Analysis of Turbo Codes 3648.6 Iterative Decoding of Turbo Codes 3718.7 EXIT Analysis 3768.8 Serial Concatenation 3838.9 Cascaded Convolutional Codes 3838.10 Weight Enumerator Analysis of SCCCs 3858.11 Iterative Decoding and Performance of SCCCs 3948.12 EXIT Analysis of Serially Concatenated Codes 3978.13 Viewpoint 4018.14 Turbo-Trellis-Coded Modulation 4028.15 Serial Concatenation 4068.16 EXIT Analysis of Serial TTCM 4088.17 Differential-Coded Modulation 4098.18 Concatenated Space-Time Coding 4148.19 Bit-Interleaved Coded and Generalized Modulation 4189 Turbo Coding: Applications 4319.1 Interleavers 4319.2 Turbo Codes in Telecommunication Standards 4399.2.1 The Space Data System Standard 4399.2.2 3G Wireless Standards 4409.2.3 Digital Video Broadcast Standards 4439.3 Product Codes and Block Turbo Decoding 4469.4 Approximate APP Decoding 4489.5 Product Codes with High-Order Modulations 4519.6 The IEEE 802.16 Standard 4539.7 Decoding of Polar Codes 4549.8 Polar Code Performance and Outlook 45810 Convolutional LDPC Codes and Spatial Coupling 46510.1 Capacity: The Ultimate Limit 46510.2 Low-Density Parity-Check Convolutional Codes 46710.2.1 New LDPC Codes from Old 46710.2.2 Decoding Convolutional LDPC Codes 47210.3 Spatial Coupling: A General View 47410.4 Spatial Coupling: Convergence Analysis 48210.4.1 Problem Setup 48210.4.2 Lyapunov Approach 483