FUNDAMENTALS OF CONVOLUTIONAL CODING

Convolutional codes, among the main error control codes, are routinely used in applications for mobile telephony, satellite communications, and voice-band modems. Written by two leading authorities in coding and information theory, this book brings you a clear and comprehensive discussion of the basic principles underlying convolutional coding. FUNDAMENTALS OF CONVOLUTIONAL CODING is unmatched in the field for its accessible analysis of the structural properties of convolutional encoders.

Other essentials covered in FUNDAMENTALS OF CONVOLUTIONAL CODING include:

• Distance properties of convolutional codes
• Viterbi, list, sequential, and iterative decoding
• Modulation codes
• Tables of good convolutional encoders
• An extensive set of homework problems

The authors draw on their own research and more than twenty years of teaching experience to present the fundamentals needed to understand the types of codes used in a variety of applications today. This book can be used as a textbook for graduate-level electrical engineering students. It will be of key interest to researchers and engineers of wireless and mobile communications, satellite communication, and data communication.

Sponsored by:
IEEE Communications Society, IEEE Information Theory Society, IEEE Vehicular Technology Society.

Rolf Johannesson holds the Chair of Information Theory at Lund University, Sweden. He has written two textbooks on switching theory and digital design, as well as a textbook on information theory. Dr. Johannesson s research interests include information theory, error-correcting codes, and cryptography. He is a Fellow of the IEEE.

Kamil Sh. Zigangirov holds the Chair of Telecommunication Theory at Lund University, Sweden. He is widely published in the areas of information theory, coding theory, detection theory, and mathematical statistics. Dr. Zigangirov is the inventor of the stack algorithm for sequential decoding.

PREFACE.

ACKNOWLEDGMENTS.

CHAPTER 1 INTRODUCTION.

1.1 Why Error Control?

1.2 Block Codes--A Primer.

1.3 A First Encounter with Convolutional Codes.

1.4 Block Codes versus Convolutional Codes.

1.5 Capacity Limits and Potential Coding Gain Revisited.

1.6 Comments.

Problems.

CHAPTER 2 CONVOLUTIONAL ENCODERSSTRUCTURAL PROPERTIES.

2.1 Convolutional Codes and Their Encoders.

2.2 The Smith Form of Polynomial Convolutional Generator Matrices.

2.3 Encoder Inverses.

2.4 Equivalent and Basic Encoding Matrices.

2.5 Minimal-Basic Encoding Matrices.

2.6 Minimal Encoding Matrices and Minimal Encoders.

2.7 Canonical Encoding Matrices.

2.8 Minimality via the Invariant-Factor Theorem.

2.9 Syndrome Formers and Dual Encoders.

2.10 Systematic Convolutional Encoders.

2.11 Comments.

Problems.

CHAPTER 3 DISTANCE PROPERTIES OF CONVOLUTIONAL CODES.

3.1 Distance Measures--A First Encounter.

3.2 Active Distances.

3.3 Properties of Convolutional Codes via the Active Distances.

3.4 Lower Bound on the Distance Profile.

3.5 Upper Bounds on the Free Distance.

3.6 Time-Varying Convolutional Codes.

3.7 Lower Bound on the Free Distance.

3.8 Lower Bounds on the Active Distances.

3.9 Distances of Cascaded Concatenated Codes.

3.10 Path Enumerators.

3.11 Comments.

Problems.

CHAPTER 4 VITERBI DECODING.

4.1 The Viterbi Algorithm Revisited.

4.2 Error Bounds for Time-Invariant Convolutional Codes.

4.3 Tighter Error Bounds for Time-Invariant Convolutional Codes.

4.4 Upper Bounds on the Output Error Burst Lengths.

4.5 Error Bounds for Periodically Time-Varying Convolutional Codes.

4.6 Lower Error Bounds for Convolutional Codes.

4.7 Error Bounds for Time-Varying Convolutional Codes.

4.8 Error Bounds for Finite Back-Search Limits.

4.9 Tailbiting Trellises.

4.10 Quantization of Channel Outputs.

4.11 Comments.

Problems.

CHAPTERS LIST DECODING.

5.1 List Decoding Algorithms.

5.2 List Decoding--Performance.

5.3 The List Minimum Weight.

5.4 Upper Bounds on the Probability of Correct Path Loss.

5.5 Lower Bound on the Probability of Correct Path Loss.

5.6 Correct Path Loss for Time-Invariant Convolutional Codes.

5.7 Comments.

Problems.

CHAPTER 6 SEQUENTIAL DECODING.

6.1 The Fano Metric.

6.2 The Stack Algorithm.

6.3 The Fano Algorithm.

6.4 The Creeper Algorithm.

6.5 Simulations.

6.6 Computational Analysis of the Stack Algorithm.

6.7 Error Probability Analysis of the Stack Algorithm.

6.8 Analysis of the Fano Algorithm.

6.9 Analysis of Creeper.

6.10 Comments.

Problems.

CHAPTER 7 ITERATIVE DECODING.

7.1 Iterative Decoding--A Primer.

7.2 The Two-Way Algorithm for APP Decoding.

7.3 The Two-Way Algorithm for Tailbiting Trellises.

7.4 The One-Way Algorithm for APP Decoding.

7.5 Low-Density Parity-Check Convolutional Codes.

7.6 Comments.

Problems.

CHAPTER 8 CONVOLUTIONAL CODES WITH GOOD DISTANCE PROPERTIES.

8.1 Computing the Distance Spectrum.

8.2 Some Classes of Rate R = 111 Convolutional Codes.

8.3 Low-Rate Convolutional Codes.

8.4 High-Rate Convolutional Codes.

8.5 Tailbiting Trellis Encoders.

8.6 Comments.

CHAPTER 9 MODULATION CODES.

9.1 Bandlimited Channels and QAM.

9.2 Coding Fundamentals.

9.3 Lattice-Type Trellis Codes.

9.4 Geometrically Uniform Trellis Codes.

9.5 Decoding of Modulation Codes.

9.6 Comments.

Problems.

APPENDIX A MINIMAL ENCODERS.

APPENDIX B WALD'S IDENTITY.

BIBLIOGRAPHY.

INDEX.

ABOUT THE AUTHORS.