The Art of Error Correcting Coding

Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
The ECC web site . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XI.I.I.
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Error correcting coding: Basic concepts . . . . . . . . . . . . . . . . . . . . 3
1.1 . 1 Block codes and convolutional codes . . . . . . . . . . . . . . . . . 3
1.1.2 Hamming distance, Hamming spheres and error correcting capability 4
1.2 Linear block codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Generator and parity-check matrices . . . . . . . . . . . . . . . . . . 6
1.2.2 The weight is the distance . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Encoding and decoding of linear block codes . . . . . . . . . . . . . . . . . 7
1.3.1 EncodingwithGandH . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Standard array decoding . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.3 Hamming spheres, decoding regions and the standard array . . . . . . 11
1.4 Weight distribution and error performance . . . . . . . . . . . . . . . . . . . 12
1.4.1 Weight distribution and undetected error probability over a BSC . . . 12
Performance bounds over BSC, AWGN and fading channels . . . . . 13
1.5 General structureof a hard-decisiondecoderof linear codes . . . . . . . . . . 19
1.4.2
2 Hamming. Golay and Reed-Muller codes . . . . . . . . . . . . . . . . . . . . . 23
2.1 Hamming codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.1 Encoding and decoding procedures . . . . . . . . . . . . . . . . . . 24
2.2 The binary Golay code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.3 26
2.3 Binary Reed-Muller codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Boolean polynomials and RM codes . . . . . . . . . . . . . . . . . . 27
2.3.2 Finite geometries and majority-logic decoding . . . . . . . . . . . . 28
Arithmetic decoding of the extended (24. 12. 8) Golay code . . . . . .
3 Binary cyclic codes and BCH codes . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1 Binary cyclic codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.1 Generator and parity-check polynomials . . . . . . . . . . . . . . . . 33
3.1.2 The generator polynomial . . . . . . . . . . . . . . . . . . . . . . .
Encoding and decoding of binary cyclic codes . . . . . . . . . . . . .
3.1.4 The parity-check polynomial . . . . . . . . . . . . . . . . . . . . . .
3.1.5 Shortened cyclic codes and CRC codes . . . . . . . . . . . . . . . .
General decoding of cyclic codes . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 GF(2m) arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Binary BCH codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Polynomial codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Decoding of binary BCH codes . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.1 General decoding algorithm for BCH codes . . . . . . . . . . . . . .
3.5.2 The Berlekamp-Massey algorithm (BMA) . . . . . . . . . . . . . . .
3.5.3 PGZ decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.4 Euclidean Algorithm (EA) . . . . . . . . . . . . . . . . . . . . . . .
3.5.5 Chien search and error correction . . . . . . . . . . . . . . . . . . .
3.5.6 Errors-and-erasures decoding . . . . . . . . . . . . . . . . . . . . .
Weight distribution and performance bounds . . . . . . . . . . . . . . . . . .
3.6.1 Error performance evaluation . . . . . . . . . . . . . . . . . . . . .
Non-binary BCH codes: Reed-Solomon codes . . . . . . . . . . . . . . . . . . .
4.1 RS codes as polynomial codes . . . . . . . . . . . . . . . . . . . . . . . . .
From binary BCH to RS codes . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Decoding RS codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Remarks on decoding algorithms . . . . . . . . . . . . . . . . . . . .
4.3.2 Errors-and-erasures decoding . . . . . . . . . . . . . . . . . . . . .
4.4 Weight distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3
3.2
3.5
3.6
4
4.2
5 Binary convotutional codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1 Basic structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Recursive systematic convolutional codes . . . . . . . . . . . . . . .
5.1.2 Free distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Connections with block codes . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Zero-tail construction . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 Direct-truncation construction . . . . . . . . . . . . . . . . . . . . .
5.2.3 Tail-biting construction . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.4 Weight distributions . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Weight enumeration and performance bounds . . . . . . . . . . . . . . . . .
5.4.1 Maximum likelihood decoding and metrics . . . . . . . . . . . . . .
5.4.2 The Viterbi algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.3 Implementation issues . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Punctured convolutional codes . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Implementation issues related to punctured convolutional codes . . .
5.5.2 RCPC codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Decoding: Viterbi algorithm with Hamming metrics . . . . . . . . . . . . . .
6 Modifying and combining codes . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1 Modifying codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Shortening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.2 Extending . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.3 Puncturing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.4 Augmenting and expurgating . . . . . . . . . . . . . . . . . . . . . .
6.2 Combining codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Time-sharing of codes . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.2 Direct-sums of codes . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.3 Products of codes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.4 Concatenated codes . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.5 Generalized concatenated codes . . . . . . . . . . . . . . . . . . . .
105
105
106
108
108
109
111
117
119
7 Soft-decision decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.2 Viterbi algorithm with Euclidean metric . . . . . . . . . . . . . . . . . . . . 124
7.4 The Chase algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.5 Ordered statistics decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.6 Generalized minimum distance decoding . . . . . . . . . . . . . . . . . . . . 134
7.6.1 Sufficient conditions for optimality . . . . . . . . . . . . . . . . . . 135
7.7 Listdecoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.8 Soft-output algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.8.1 Soft-output Viterbi algorithm . . . . . . . . . . . . . . . . . . . . . . 136
7.8.3 Log-MAP algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.8.4 Max-Log-MAP algorithm . . . . . . . . . . . . . . . . . . . . . . . 142
7.8.5 Soft-output OSD algorithm . . . . . . . . . . . . . . . . . . . . . . . 142
7.1 Binary transmission over AWGN channels . . . . . . . . . . . . . . . . . . . 124
7.3 Decoding binary linear block codes with a trellis . . . . . . . . . . . . . . . 130
7.8.2 Maximum-a-posteriori (MAP) algorithm . . . . . . . . . . . . . . . 139
8 Iteratively decodable codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.1 Iterative decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.2 Productcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.2.1 Parallel concatenation: turbo codes . . . . . . . . . . . . . . . . . . 149
8.2.2 Serial concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.2.3 Block product codes . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.3 Low-density parity-check codes . . . . . . . . . . . . . . . . . . . . . . . . 161
8.3.1 Tanner graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.3.2 Iterative hard-decision decoding: The bit-flip algorithm . . . . . . . . 163
8.3.3 Iterative probabilisticdecoding: belief propagation . . . . . . . . . . 164
9 Combining codes and digital modulation . . . . . . . . . . . . . . . . . . . . . 171
9.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
9.1.1 Examples of signal sets . . . . . . . . . . . . . . . . . . . . . . . . . 172
9.1.2 Coded modulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
9.1.3 Distance considerations . . . . . . . . . . . . . . . . . . . . . . . . 175
9.2 Trellis-coded modulation (TCM) . . . . . . . . . . . . . . . . . . . . . . . . 176
9.2.1 Set partitioning and trellis mapping . . . . . . . . . . . . . . . . . . 176
9.2.2 Maximum-likelihood decoding . . . . . . . . . . . . . . . . . . . . . 177
9.2.3 Distance considerations and error performance . . . . . . . . . . . . 177
9.2.4 Pragmatic TCM and two-stage decoding . . . . . . . . . . . . . . . . 178
9.3 Multilevel coded modulation (MCM) . . . . . . . . . . . . . . . . . . . . . . 182
9.3.1 Constructions and multi-stage decoding . . . . . . . . . . . . . . . . 183
9.3.2 Unequal-error-protection with MCM . . . . . . . . . . . . . . . . . 185
9.4 Bit-interleaved coded modulation (BICM) . . . . . . . . . . . . . . . . . . . 191
9.4.1 Gray mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.4.2 Metric generation: De-mapping . . . . . . . . . . . . . . . . . . . . 192
9.4.3 Interleaving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
9.5 Turbo trellis-coded modulation (TTCM) . . . . . . . . . . . . . . . . . . . . 194
9.5.1 Pragmatic turbo TCM . . . . . . . . . . . . . . . . . . . . . . . . . 194
9.5.2 Turbo TCM with symbol interleaving . . . . . . . . . . . . . . . . . 194
9.5.3 Turbo TCM with bit interleaving . . . . . . . . . . . . . . . . . . . . 194
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Appendix A Weight distributions of extended BCH codes . . . . . . . . . . . . . . 207
A.l Length8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
A.2 Length 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
A.3 Length 32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
A.4 Length 64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
AS Length 128 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

Another Security Books
Another Network Books
Download