Fundamentals of Convolutional Coding

Rolf Johannesson is Professor Emeritus of Information Theory at Lund University, Sweden, and a Fellow of the IEEE. He was awarded the honor of Professor, honoris causa, from the Institute for Information Transmission Problems, Russian Academy of Sciences, and elected member of the Royal Swedish Academy of Engineering Sciences. Dr. Johannesson's research interests include information theory, coding theory, and cryptography.Kamil Sh. Zigangirov is Professor Emeritus of Telecommunication Theory at Lund University, Sweden, and a Fellow of the IEEE. He is widely published in the areas of information theory, coding theory, mathematical statistics, and detection theory. Dr. Zigangirov is the inventor of the stack algorithm for sequential decoding and the co-inventor of the LDPC convolutional codes.

• Preface xiAcknowledgement xiv1 Introduction 11.1 Why error control? 11.2 Block codes—a primer 81.3 Codes on graphs 211.4 A first encounter with convolutional codes 281.5 Block codes versus convolutional codes 351.6 Capacity limits and potential coding gain revisited 361.7 Comments 39Problems 412 Convolutional encoders—Structural properties 492.1 Convolutional codes and their encoders 492.2 The Smith form of polynomial convolutional generator matrices 582.3 Encoder inverses 672.4 Encoder and code equivalences 762.5 Basic encoding matrices 792.6 Minimalbasic encoding matrices 822.7 Minimal encoding matrices and minimal encoders 902.8 Canonical encoding matrices* 1092.9 Minimality via the invariantfactor theorem* 1272.10 Syndrome formers and dual encoders 1312.11 Systematic convolutional encoders 1392.12 Some properties of generator matrices—an overview 1502.13 Comments 150Problems 1523 Distance properties of convolutional codes 1613.1 Distance measures—a first encounter 1613.2 Active distances 1713.3 Properties of convolutional codes via the active distances 1793.4 Lower bound on the distance profile 1813.5 Upper bounds on the free distance 1863.6 Timevarying convolutional codes 1913.7 Lower bound on the free distance 1953.8 Lower bounds on the active distances* 2003.9 Distances of cascaded concatenated codes* 2073.10 Path enumerators 2133.11 Comments 220Problems 2214 Decoding of convolutional codes 2254.1 The Viterbi algorithm revisited 2264.2 Error bounds for timeinvariant convolutional codes 2354.3 Tighter error bounds for timeinvariant convolutional codes 2504.4 Exact bit error probability for Viterbi decoding 2554.5 The BCJR algorithm for APP decoding 2714.6 The oneway algorithm for APP decoding 2834.7 A simple upper bound on the bit error probability for extremely noisy channels 2884.8 Tailbiting trellises 2934.9 Decoding of tailbiting codes 3024.10 BEAST decoding of tailbiting codes 3084.11 Comments 323Problems 3245 Random ensemble bounds for decoding error probability 3335.1 Upper bounds on the output error burst lengths 3335.2 Bounds for periodically timevarying convolutional codes 3455.3 Lower error probability bounds for convolutional codes 3555.4 General bounds for timevarying convolutional codes 3635.5 Bounds for finite backsearch limits 3755.6 Quantization of channel outputs 3795.7 Comments 384Problems 3846 List decoding 3876.1 List decoding algorithms 3886.2 List decoding—performance 3916.3 The list minimum weight 3976.4 Upper bounds on the probability of correct path loss 4076.5 Lower bound on the probability of correct path loss 4166.6 Correct path loss for timeinvariant convolutional codes 4186.7 Comments 422Problems 4237 Sequential decoding 4257.1 The Fano metric 4267.2 The stack algorithm 4317.3 The Fano algorithm 4337.4 The Creeper algorithm* 4367.5 Simulations 4487.6 Computational analysis of the stack algorithm 4507.7 Error probability analysis of the stack algorithm 4607.8 Analysis of the Fano algorithm 4717.9 Analysis of Creeper* 4777.10 Comments 480Problems 4818 Lowdensity paritycheck codes 4858.1 LDPC block codes 4868.2 LDPC convolutional codes 4968.3 Block and convolutional permutors 5088.4 Lower bounds on distances of LDPC codes 5178.5 Iterative decoding of LDPC codes 5298.6 Iterative limits and thresholds 5388.7 Braided block codes* 5538.8 Comments 562Problems 5629 Turbo coding 5679.1 Parallel concatenation of two convolutional codes 5679.2 Distance bounds of turbo codes 5709.3 Parallel concatenation of three and more convolution codes 5739.4 Iterative decoding of turbo codes 5829.5 Braided convolutional codes* 5869.6 Comments 591Problems 59110 Convolutional codes with good distance properties 59310.1 Computing the Viterbi spectrum using FAST 59410.2 The magnificient BEAST 59810.3 Some classes of rate R = 1=2 convolutional codes 60410.4 Low rate convolutional codes 60810.5 High rate convolutional codes 62110.6 Tailbiting trellis encoders 62210.7 Comments 622Appendix A: Minimal encoders 627Appendix B: Wald’s identity 635References 647Index 659