The Art of Error Correcting Coding

Building on the success of the first edition, which offered a practical introductory approach to the techniques of error concealment, this book, now fully revised and updated, provides a comprehensive treatment of the subject and includes a wealth of additional features. The Art of Error Correcting Coding, Second Edition explores intermediate and advanced level concepts as well as those which will appeal to the novice. All key topics are discussed, including Reed-Solomon codes, Viterbi decoding, soft-output decoding algorithms, MAP, log-MAP and MAX-log-MAP.  Reliability-based algorithms GMD and Chase are examined, as are turbo codes, both serially and parallel concatenated, as well as low-density parity-check (LDPC) codes and their iterative decoders. Features additional problems at the end of each chapter and an instructor’s solutions manual Updated companion website offers new C/C ++programs and MATLAB scripts, to help with the understanding and implementation of basic ECC techniques Easy to follow examples illustrate the fundamental concepts of error correcting codes Basic analysis tools are provided throughout to help in the assessment of the error performance block and convolutional codes of a particular error correcting coding (ECC) scheme for a selection of the basic channel models This edition provides an essential resource to engineers, computer scientists and graduate students alike for understanding and applying ECC techniques in the transmission and storage of digital information.

Table of Contents:
Preface ix Foreword xi The ECC web site xiii 1 Introduction 1 1.1 Error correcting coding: Basic concepts 4 1.1.1 Block codes and convolutional codes 4 1.1.2 Hamming distance, Hamming spheres and error correcting capability 5 1.2 Linear block codes 7 1.2.1 Generator and parity-check matrices 7 1.2.2 The weight is the distance 8 1.3 Encoding and decoding of linear block codes 8 1.3.1 Encoding with G and H 8 1.3.2 Standard array decoding 10 1.3.3 Hamming spheres, decoding regions and the standard array 12 1.4 Weight distribution and error performance 13 1.4.1 Weight distribution and undetected error probability over a BSC 14 1.4.2 Performance bounds over BSC, AWGN and fading channels 15 1.5 General structure of a hard-decision decoder of linear codes 23 Problems 23 2 Hamming, Golay and Reed–Muller codes 27 2.1 Hamming codes 27 2.1.1 Encoding and decoding procedures 28 2.2 The binary Golay code 29 2.2.1 Encoding 29 2.2.2 Decoding 30 2.2.3 Arithmetic decoding of the extended (24, 12, 8) Golay code 30 2.3 Binary Reed–Muller codes 31 2.3.1 Boolean polynomials and RM codes 31 2.3.2 Finite geometries and majority-logic decoding 33 Problems 37 3 Binary cyclic codes and BCH codes 39 3.1 Binary cyclic codes 39 3.1.1 Generator and parity-check polynomials 39 3.1.2 The generator polynomial 40 3.1.3 Encoding and decoding of binary cyclic codes 41 3.1.4 The parity-check polynomial 42 3.1.5 Shortened cyclic codes and CRC codes 44 3.1.6 Fire codes 45 3.2 General decoding of cyclic codes 46 3.2.1 GF(2m) arithmetic 48 3.3 Binary BCH codes 52 3.3.1 BCH bound 53 3.4 Polynomial codes 53 3.5 Decoding of binary BCH codes 54 3.5.1 General decoding algorithm for BCH codes 56 3.5.2 The Berlekamp–Massey algorithm (BMA) 57 3.5.3 PGZ decoder 60 3.5.4 Euclidean algorithm 61 3.5.5 Chien search and error correction 63 3.5.6 Errors-and-erasures decoding 63 3.6 Weight distribution and performance bounds 65 3.6.1 Error performance evaluation 66 Problems 69 4 Nonbinary BCH codes: Reed–Solomon codes 73 4.1 RS codes as polynomial codes 73 4.2 From binary BCH to RS codes 73 4.3 Decoding RS codes 74 4.3.1 Remarks on decoding algorithms 79 4.3.2 Errors-and-erasures decoding 79 4.4 Weight distribution 84 Problems 84 5 Binary convolutional codes 87 5.1 Basic structure 87 5.1.1 Recursive systematic convolutional codes 92 5.1.2 Free distance 94 5.2 Connections with block codes 94 5.2.1 Zero-tail construction 94 5.2.2 Direct-truncation construction 95 5.2.3 Tail-biting construction 95 5.2.4 Weight distributions 95 5.3 Weight enumeration 97 5.4 Performance bounds 99 5.5 Decoding: Viterbi algorithm with Hamming metrics 101 5.5.1 Maximum-likelihood decoding and metrics 101 5.5.2 The Viterbi algorithm 102 5.5.3 Implementation issues 104 5.6 Punctured convolutional codes 112 5.6.1 Implementation issues related to punctured convolutional codes 115 5.6.2 RCPC codes 116 Problems 116 6 Modifying and combining codes 119 6.1 Modifying codes 119 6.1.1 Shortening 119 6.1.2 Extending 121 6.1.3 Puncturing 122 6.1.4 Augmenting, expurgating and lengthening 122 6.2 Combining codes 124 6.2.1 Time sharing of codes 124 6.2.2 Direct sums of codes 125 6.2.3 The |u|u + v|-construction and related techniques 126 6.2.4 Products of codes 128 6.2.5 Concatenated codes 134 6.2.6 Generalized concatenated codes 136 Problems 140 7 Soft-decision decoding 143 7.1 Binary transmission over AWGN channels 144 7.2 Viterbi algorithm with Euclidean metric 145 7.3 Decoding binary linear block codes with a trellis 146 7.4 The Chase algorithm 150 7.5 Ordered statistics decoding 153 7.6 Generalized minimum distance decoding 156 7.6.1 Sufficient conditions for optimality 157 7.7 List decoding 158 7.8 Soft-output algorithms 158 7.8.1 Soft-output Viterbi algorithm 158 7.8.2 Maximum-a posteriori (MAP) algorithm 161 7.8.3 Log-MAP algorithm 163 7.8.4 Max-Log-MAP algorithm 164 7.8.5 Soft-output OSD algorithm 164 Problems 165 8 Iteratively decodable codes 169 8.1 Iterative decoding 172 8.2 Product codes 174 8.2.1 Parallel concatenation: Turbo codes 174 8.2.2 Serial concatenation 183 8.2.3 Block product codes 185 8.3 Low-density parity-check codes 190 8.3.1 Tanner graphs 190 8.3.2 Iterative hard-decision decoding: The bit-flip algorithm 192 8.3.3 Iterative probabilistic decoding: Belief propagation 196 Problems 201 9 Combining codes and digital modulation 203 9.1 Motivation 203 9.1.1 Examples of signal sets 204 9.1.2 Coded modulation 206 9.1.3 Distance considerations 207 9.2 Trellis-coded modulation (TCM) 208 9.2.1 Set partitioning and trellis mapping 209 9.2.2 Maximum-likelihood decoding 211 9.2.3 Distance considerations and error performance 212 9.2.4 Pragmatic TCM and two-stage decoding 213 9.3 Multilevel coded modulation 217 9.3.1 Constructions and multistage decoding 217 9.3.2 Unequal error protection with MCM 221 9.4 Bit-interleaved coded modulation 225 9.4.1 Gray mapping 226 9.4.2 Metric generation: De-mapping 227 9.4.3 Interleaving 227 9.5 Turbo trellis-coded modulation 227 9.5.1 Pragmatic turbo TCM 228 9.5.2 Turbo TCM with symbol interleaving 228 9.5.3 Turbo TCM with bit interleaving 229 Problems 230 Appendix A Weight distributions of extended BCH codes 233 A.1 Length 8 233 A.2 Length 16 233 A.3 Length 32 234 A.4 Length 64 235 A.5 Length 128 238 Bibliography 247 Index 257