Bie Si IN/COSTELLO SHU LIN / DANIEL J. COSTELLO, Jr. Error Control Coding: TCL Wal loo bo) tT foie Moelle Bev Er | Sra iy a a 3 o i H rs > % = Fy i) PI a Cr} 8 PRENTICE-HALL SERIES IN COMPUTER APPLICATIONS IN ELECTRICAL ENGINEERING eae ag ee adERROR CONTROL CODING Fundamentals and ApplicationsPRENTICE-HALL COMPUTER APPLICATIONS IN ELECTRICAL ENGINEERING SERIES FRANKLIN F. KUO, editor ApkaMsoN and Kuo, Computer-Communication Networks Bowens and Sepore, Sceptre: A Computer Program for Circuit and Systems Anal Canzow, Discrete Time Systems: An Introduction with Interdisciplinary Applications Capzow and Martens, Discrete-Time and Computer Control Systems Davis, Computer Data Displays FRIEDMAN and MExoN, Fault Detection in Digital Circuits HueLsMan, Basic Circuit Theory Jensen and LieveRMaN, IBM Circuit Analysis Program: Techniques and Applications ‘Jensen and WATKINS, Network Analysis: Theory and Computer Methods KLINE, Digital Computer Design Kocnennurcer, Computer Simulation of Dynamic Systems Kuo, (ed.) Protocols and Techniques for Data Communication Networks Kvo and MaGNuson, Computer Oriented Circuit Design Lin, An Introduction to Error-Correcting Codes LIN and CosreLto, Error Control Coding: Fundamentals and Applications NAGLE, CanRoLt, and InwiN, An Introduction to Computer Logic Ruyye, Fundamentals of Digitals Systems Design SUFFERLEN and VARTANIAN, Digital Electronics with Engineering Applications ‘StAupHAMMER, Circuit Analysis by Digital Computer Srourewver, PL/I Programming for Engineering and ScienceERROR CONTROL CODING Fundamentals and Applications SHU LIN University of Hawaii Texas A&M University DANIEL J. COSTELLO, JR. Illinois Institute of Technology Prentice-Hall, Inc. Englewood Cliffs, New Jersey 07632Liar of Const Cattoing in Pulcton Das Lb tecicaensineson srs) Tnsldes biographical references nd inden 1 Erorcorrecting code (Information these) Qa26sLss poise s2nss ISBN O-D28796% AKcRa uitoral/production supervision and interior design by Anne Simpson Cover design by Marvin Warshaw Manufacturing buyer: Joyce Levatino © 1985 by Prentice-Hall, Inc, Englewood Cliffs, N.. 07632 All rights reserved. No part ofthis book may be reproduced in any form or by any means without permission in writing from the publisher, Printed in the United States of America 10987 ISBN 0-13-283794-x PRENTICE-HALL INTERNATIONAL, INC,, London PRENTICE-HALL OF AUSTRALIA PIY. LIMITED, Sydney EDITORA PRENTICE-HALL DO BRAZIL, LTDA, Rio de Jonero PRENTICEHALL CANADA INC, Toronto PRENTICE-HALL OF INDIA PRIVATE LIMITED, New Dethi PRENTICE-HALL OF JAPAN, INC. Tokyo SRENTICE-ALL OF SOUTHEAST ASIA PTE. LTD., Singepore WHITEHALL BOOKS LIMITED, Wellington, New ZeclondWith Love and Affection for Ivy, Julian, Patrick, and Michelle Lin and Lucretia, Kevin, Nick, Daniel, and Anthony CostelloContents CHAPTER 1 CHAPTER 2 PREFACE xiii CODING FOR RELIABLE DIGITAL TRANSMISSION AND STORAGE i 1.1 Introduction 1 1.2 Types of Codes 3 1,3 Modulation and Demodulation 5 1.4 Maximum Likelihood Decoding 8 1.5 Types of Errors ” 1.6 Error Control Strategies 12 References 14 INTRODUCTION TO ALGEBRA 15 241 Groups 15 22 Fields 19 2.3 Binary Field Arithmetic 24 2.4 Construction of Galois Field GF(2") 29 2.5 Basic Properties of Galois Field GF") 34 2.6 Computations Using Galois Field GF(2*) Arithmetic 39 2.7 Vector Spaces 40 28 Matrices 46 Problems 48 References 50CHAPTER 3 CHAPTER 4 CHAPTER 5 CHAPTER 6 LINEAR BLOCK CODES 51 3.1 Introduction to Linear Block Codes ‘1 3.2 Syndrome and Error Detection 58 3.3 Minimum Distance of a Block Code 63. 3.4 Error-Detecting and Error-Correcting Capabilities ofa Block Code 65 3.5 Standard Array and Syndrome Decoding 68 3.6 Probability of an Undetected Error for Linear Codes overaBSC 76 3.7 Hamming Codes 79 Problems 82 References 84 CYCLIC CODES 8s 4.1 Description of Cyclic Codes as 4.2 Generator and Parity-Check Matrices of Cyclic Codes 92 43 Encoding of Cyclic Codes 95 4.4 Syndrome Computation and Error Detection 98 4.5 Decoding of Cyelic Codes 103 46 Cyclic Hamming Codes =m 4.7 Shortened Cyclic Codes 116 Problems 121 References 128 ERROR-TRAPPING DECODING FOR CYCLIC CODES — 125 5.1 Error-Trapping Decoding 125 5.2 Improved Error-Trapping Decoding 131 53 The Golay Code 134 Problems 139 References 139 BCH CODES 14 6.1 Description of the Codes 142 6.2 Decoding of the BCH Codes 151 6.3 Implementation of Galois Field Arithmetic 161 64 Implementation of Error Correction 167 6.5 Nonbinary BCH Codes and Reed-Solomon Codes 70 6.6 Weight Distribution and Error Detection of Binary BCH Codes 177 Problems 180 References 182 ContentsCHAPTER 7 MAJORITY-LOGIC DECODING FOR CYCLIC CODES = 184 7.1 One-Step Majority-Logic Decoding 184 7.2 Class of One-Step Majority-Logic Decodable Codes 194 73 Other One-Step Majority-Logic Decodable Codes 201 74 Multiple-Step Majority-Logic Decoding 209 Problems 219 References 221 CHAPTER 8 FINITE GEOMETRY CODES = 223 8.1 Euclidean Geometry 223, 8.2. Majority-Logic Decodable Cyclic Codes Based on Euclidean Geometry 227 8.3 Projective Geometry and Projective Geometry Codes 240 8.4 Modifications of Majority-Logic Decoding 245 Problems 253. References 255 CHAPTER 9 BURST-ERROR-CORRECTING CODES =—257 9.1 Introduction 257 9.2 Decoding of Single-Burst-Error-Correcting Cyclic Codes 259 9,3 Single-Burst-Error-Correcting Codes 267 9.4 Interleaved Codes 277 9.5 Phased-Burst-Error-Correcting Codes 272 9.6 Burst-and-Random-Error-Correcting Codes 24 9.7 Modified Fire Codes for Simultaneous Correction of Burst and Random Errors 280 Problems 282 References 284 CHAPTER 10 CONVOLUTIONAL CODES =— 287 10.1 Encoding of Convolutional Codes 288 10.2 Structural Properties of Convolutional Codes 295 10.3 Distance Properties of Convolutional Codes 308 Problems 312 References 313 CHAPTER 11 MAXIMUM LIKELIHOOD DECODING OF CONVOLUTIONAL CODES — 315 ILI The Viterbi Algorithm 315 11.2 Performance Bounds for Convolutional Codes 322 Contents xCHAPTER 12 CHAPTER 13 CHAPTER 14 CHAPTER 15 11.3 Construction of Good Convolutional Codes 329 11.4 Implementation of the Viterbi Algorithm 337 11.5 Modifications of the Viterbi Algorithm 345 Problems 346 References 348 SEQUENTIAL DECODING OF CONVOLUTIONAL CODES = 350 12.1 The Stack Algorithm 351 12.2 The Fano Algorithm 360 12.3 Performance Characteristics of Sequential Decoding 364 12.4 Code Construction for Sequential Decoding 374 12.5 Other Approaches to Sequential Decoding 380. Problems 384 References 386 MAJORITY-LOGIC DECODING OF CONVOLUTIONAL CODES — 388 13.1 Feedback Decoding 389 13.2 Error Propagation and Definite Decoding 406 133 Distance Properties and Code Performance 408 13.4 Code Construction for Majority-Logic Decoding a4 13.5 Comparison with Probabilistic Decoding 424 Problems 426 References 428 BURST-ERROR-CORRECTING CONVOLUTIONAL CODES = 429 14.1 Bounds on Burst-Error-Correcting Capability 430 14.2 Burst-Error-Correcting Convolutional Codes 430 14.3 Interleaved Convolutional Codes 441 14.4 Burst-and-Random-Error-Correcting Convolutional Codes 442 Problems. 455 References 456 AUTOMATIC-REPEAT-REQUEST STRATEGIES = 458 15.1 Basic ARQ Schemes 459 15.2 Sclective-Repeat ARQ System with Finite Receiver Buffer 465 15.3 ARQ Schemes with Mixed Modes of Retransmission 474 15.4 Hybrid ARQ Schemes 477 15.5 Class of Half-Rate Invertible Codes 481 Contents15.6 Type II Hybrid Selective-Repeat ARQ with Finite Receiver Buffer 483 Problems 494 References 495 CHAPTER 16 APPLICATIONS OF BLOCK CODES FOR ERROR CONTROL IN DATA STORAGE SYSTEMS = 498 16.1 Error Control for Computer Main Processor and Control Storages 498 16.2 Error Control for Magnetic Tapes 503 16.3 Error Control in IBM 3850 Mass Storage System 516 164 Error Control for Magnetic Disks 525 16.5 Error Control in Other Data Storage Systems $37 Problems $92 References 532 CHAPTER 17 PRACTICAL APPLICATIONS OF CONVOLUTIONAL CODES = 533 17.1 Applications of Viterbi Decoding $33 17.2 Applications of Sequential Decoding 539 17.3 Applications of Majority-Logic Decoding $43 174 Applications to Burst-Etror Correction 347 175 Applications of Convolutional Codes in ARQ Systems 551 Problems 556 References 557 Appendix A Tables of Galois Fields 561 Appendix B Minimal Polynomials of Elements in GF(2") 579 Appendix C Generator Polynomials of Binary Primitive BCH Codes of Length up to 2'°—1 583 INDEX 599 Contents xi