Fundamentals of Convolutional Coding ROLF JOHANNESSON KAMIL Sh. ZIGANGIROV John B. Anderson, Series Editor IEEE Press 445 Hoes Lane, P.O. Box 1331 Piscataway, NJ 08855-1331 IEEE Press Editorial Board Roger F. Hoyt, Editor in Chief J. B. Anderson A. H. Haddad M. Padgett P. M. Anderson R. Herrick W. D. Reeve M. Eden S. Kartalopoulos G. Zobrist M. E. El-Hawary D. Kirk S. Furui P. Laplante Kenneth Moore, Director of IEEE Press John Griffin, Senior Acquisition Editor Marilyn G. Catis, Assistant Editor IEEE Communications Society, Sponsor COMM-S Liaison to IEEE Press, Salah Aidarous Information Theory Society, Sponsor IT-S Liaison to IEEE Press, Sanjeev Kulkarni Vehicular Technology Society, Sponsor VT-S Liaison to IEEE Press, J. R. Cruz Cover photo: After Gottfried Ungerboeck, Courtesy of IBM, Zurich Laboratory, Switzerland Cover design: William T. Donnelly, WT Design Technical Reviewers Daniel J. Costello, Jr., University of Notre Dame John Proakis, Northeastern University Books of Related Interest from the IEEE Press ... DIGITAL TRANSMISSION ENGINEERING John B. Anderson A volume in the Digital & Mobile Communication Series An IEEE Press book published in cooperation with Prentice Hall 1999 Hardcover 400 pp IEEE Order No. PC5714 ISBN 0-7803-3457-4 TRELLIS CODING Christian Schlegel 1997 Hardcover 304 pp IEEE Order No. PC4609 ISBN 0-7803-1052-7 AN INTRODUCTION TO STATISTICAL COMMUNICATION THEORY.- An IEEE Classic Reissue David Middleton 1996 Hardcover 1,184 pp IEEE Order No. PC5648 ISBN 0-7803-1178-7 REED-SOLOMON CODES AND THEIR APPLICATIONS Stephen B. Wicker and Vijay K. Bhargava 1994 Hardcover 336 pp IEEE Order No. PC3749 ISBN 0-7803-1025-X FUNDAMENTALS OF CONVOLUTIONAL CODING Rolf Johannesson Lund University, Sweden Kamil Sh. Zigangirov Lund University, Sweden IEEE Communications Society, Sponsor IEEE Information Theory Society, Sponsor IEEE Vehicular Technology Society, Sponsor IEEE PRESS John B. Anderson, Series Editor The Institute of Electrical and Electronics Engineers, Inc., New York This book and other books may be purchased at a discount from the publisher when ordered in bulk quantities. Contact: IEEE Press Marketing Attn: Special Sales Piscataway, NJ 08855-1331 Fax: (732) 981-9334 For more information about IEEE PRESS products, visit the IEEE Home Page: http://www.ieee.org/ © 1999 by The Institute of Electrical and Electronics Engineers, Inc. 3 Park Avenue, 17th floor, New York, NY 10016-5997. All rights reserved. No part of this book may be reproduced in any form, nor may it be stored in a retrieval system or transmitted in any form, without written permission from the publisher. Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 ISBN 0-7803-3483-3 IEEE Order Number: PC5739 Library of Congress Cataloging-in-Publication Data Johannesson, Rolf, 1946- Fundamentals of convolutional coding / Rolf Johannesson, Kamil Sh. Zigangirov. p. cm. -- (IEEE Press series on digital and mobile communication) "IEEE Communications Society, sponsor. IEEE Information Theory Society, sponsor. IEEE Vehicular Technology Society, sponsor." Includes bibliographical references and index. ISBN 0-7803-3483-3 1. Coding theory. 2. Convolutions (Mathematics). 3. Error- correcting codes (Information theory) I. Zigangirov, K. Sh. II. IEEE Communications Society. III. IEEE Information Theory Society. IV. Vehicular Technology Society. V. Title. VI. Series. TK5102.92.J64 1998 003' .54--dc21 98-36706 CIP To Regina, Katrin, Peter, and Hanna and Ira, Dima, and Valja Contents PREFACE xi ACKNOWLEDGMENTS xiii CHAPTER 1 INTRODUCTION 1 1.1 Why Error Control? 1 1.2 Block Codes-A Primer 6 1.3 A First Encounter with Convolutional Codes 16 1.4 Block Codes versus Convolutional Codes 21 1.5 Capacity Limits and Potential Coding Gain Revisited 23 1.6 Comments 25 Problems 26 CHAPTER 2 CONVOLUTIONAL ENCODERS- STRUCTURAL PROPERTIES 31 2.1 Convolutional Codes and Their Encoders 31 2.2 The Smith Form of Polynomial Convolutional Generator Matrices 38 2.3 Encoder Inverses 45 2.4 Equivalent and Basic Encoding Matrices 52 2.5 Minimal-Basic Encoding Matrices 55 2.6 Minimal Encoding Matrices and Minimal Encoders 61 2.7 Canonical Encoding Matrices* 73 2.8 Minimality via the Invariant-Factor Theorem* 87 vii viii Contents 2.9 Syndrome Formers and Dual Encoders 91 2.10 Systematic Convolutional Encoders 96 2.11 Comments 103 Problems 103 CHAPTER 3 DISTANCE PROPERTIES OF CONVOLUTIONAL CODES 109 3.1 Distance Measures-A First Encounter 109 3.2 Active Distances 117 3.3 Properties of Convolutional Codes via the Active Distances 123 3.4 Lower Bound on the Distance Profile 128 3.5 Upper Bounds on the Free Distance 132 3.6 Time-Varying Convolutional Codes 136 3.7 Lower Bound on the Free Distance 139 3.8 Lower Bounds on the Active Distances* 143 3.9 Distances of Cascaded Concatenated Codes* 149 3.10 Path Enumerators 153 3.11 Comments 158 Problems 159 CHAPTER 4 VITERBI DECODING 163 4.1 The Viterbi Algorithm Revisited 163 4.2 Error Bounds for Time-Invariant Convolutional Codes 168 4.3 Tighter Error Bounds for Time-Invariant Convolutional Codes 181 4.4 Upper Bounds on the Output Error Burst Lengths 186 4.5 Error Bounds for Periodically Time-Varying Convolutional Codes 195 4.6 Lower Error Bounds for Convolutional Codes 203 4.7 Error Bounds for Time-Varying Convolutional Codes 211 4.8 Error Bounds for Finite Back-Search Limits 220 4.9 Tailbiting Trellises 223 4.10 Quantization of Channel Outputs 230 4.11 Comments 233 Problems 234 CHAPTER 5 LIST DECODING 239 5.1 List Decoding Algorithms 239 5.2 List Decoding-Performance 242 5.3 The List Minimum Weight 247 5.4 Upper Bounds on the Probability of Correct Path Loss 255 Contents Ix 5.5 Lower Bound on the Probability of Correct Path Loss 261 5.6 Correct Path Loss for Time-Invariant Convolutional Codes 264 5.7 Comments 266 Problems 267 CHAPTER 6 SEQUENTIAL DECODING 269 6.1 The Fano Metric 269 6.2 The Stack Algorithm 274 6.3 The Fano Algorithm 276 6.4 The Creeper Algorithm* 278 6.5 Simulations 288 6.6 Computational Analysis of the Stack Algorithm 289 6.7 Error Probability Analysis of the Stack Algorithm 296 6.8 Analysis of the Fano Algorithm 305 6.9 Analysis of Creeper* 310 6.10 Comments 313 Problems 313 CHAPTER 7 ITERATIVE DECODING 317 7.1 Iterative Decoding-A Primer 317 7.2 The Two-Way Algorithm for APP Decoding 321 7.3 The Two-Way Algorithm for Tailbiting Trellises 330 7.4 The One-Way Algorithm for APP Decoding 334 7.5 Low-Density Parity-Check Convolutional Codes 337 7.6 Comments 344 Problems 344 CHAPTER 8 CONVOLUTIONAL CODES WITH GOOD DISTANCE PROPERTIES 347 8.1 Computing the Distance Spectrum 347 8.2 Some Classes of Rate R = 1/2 Convolutional Codes 351 8.3 Low-Rate Convolutional Codes 357 8.4 High-Rate Convolutional Codes 360 8.5 Tailbiting Trellis Encoders 362 8.6 Comments 370 CHAPTER 9 MODULATION CODES 371 9.1 Bandlimited Channels and QAM 373 9.2 Coding Fundamentals 378 9.3 Lattice-Type Trellis Codes 384 x Contents 9.4 Geometrically Uniform Trellis Codes 384 9.5 Decoding of Modulation Codes 387 9.6 Comments 388 Problems 389 APPENDIX A MINIMAL ENCODERS 393 APPENDIX B WALD'S IDENTITY 399 BIBLIOGRAPHY 407 INDEX 419 ABOUT THE AUTHORS 427