Wiley.The.Art.of.Error.Correcting.Coding.Second.Edition(信道编解码经典书籍)

crazylwj · 发表于 2009-4-16 14:03:34

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？注册

x

Contents:
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

Wiley.The.Art.of.Error.Correcting.Coding.Second.Edition.rar (1.73 MB, 下载次数: 710 )