Contents
Preface page xi
1 Introduction 1
1.1 The discrete communication channel 2
1.2 The history of data-transmission codes 4
1.3 Applications 6
1.4 Elementary concepts 7
1.5 Elementary codes 14
Problems 17
2 Introduction to Algebra 20
2.1 Fields of characteristic two 20
2.2 Groups 23
2.3 Rings 28
2.4 Fields 30
2.5 Vector spaces 32
2.6 Linear algebra 37
Problems 45
Notes 48
3 Linear BlockCodes 49
3.1 Structure of linear block codes 49
3.2 Matrix description of linear block codes 50
3.3 Hamming codes 54
3.4 The standard array 56
v
vi Contents
3.5 Hamming spheres and perfect codes 59
3.6 Simple modifications to a linear code 62
Problems 63
Notes 66
4 The Arithmetic of Galois Fields 67
4.1 The integer ring 67
4.2 Finite fields based on the integer ring 70
4.3 Polynomial rings 72
4.4 Finite fields based on polynomial rings 79
4.5 Primitive elements 83
4.6 The structure of finite fields 86
Problems 92
Notes 95
5 Cyclic Codes 96
5.1 Viewing a code from an extension field 96
5.2 Polynomial description of cyclic codes 99
5.3 Minimal polynomials and conjugates 104
5.4 Matrix description of cyclic codes 111
5.5 Hamming codes as cyclic codes 113
5.6 Cyclic codes for correcting double errors 116
5.7 Quasi-cyclic codes and shortened cyclic codes 118
5.8 The Golay code as a cyclic code 119
5.9 Cyclic codes for correcting burst errors 123
5.10 The Fire codes as cyclic codes 125
5.11 Cyclic codes for error detection 127
Problems 128
Notes 130
6 Codes Based on the Fourier Transform 131
6.1 The Fourier transform 131
6.2 Reed–Solomon codes 138
vii Contents
6.3 Conjugacy constraints and idempotents 143
6.4 Spectral description of cyclic codes 148
6.5 BCH codes 152
6.6 The Peterson–Gorenstein–Zierler decoder 159
6.7 The Reed–Muller codes as cyclic codes 166
6.8 Extended Reed–Solomon codes 169
6.9 Extended BCH codes 172
Problems 175
Notes 177
7 Algorithms Based on the Fourier Transform 179
7.1 Spectral estimation in a finite field 179
7.2 Synthesis of linear recursions 183
7.3 Decoding of binary BCH codes 191
7.4 Decoding of nonbinary BCH codes 193
7.5 Decoding with erasures and errors 201
7.6 Decoding in the time domain 206
7.7 Decoding within the BCH bound 210
7.8 Decoding beyond the BCH bound 213
7.9 Decoding of extended Reed–Solomon codes 216
7.10 Decoding with the euclidean algorithm 217
Problems 223
Notes 226
8 Implementation 228
8.1 Logic circuits for finite-field arithmetic 228
8.2 Shift-register encoders and decoders 235
8.3 The Meggitt decoder 237
8.4 Error trapping 244
8.5 Modified error trapping 250
8.6 Architecture of Reed–Solomon decoders 254
8.7 Multipliers and inverters 258
8.8 Bit-serial multipliers 262
Problems 267
Notes 269
viii Contents
9 Convolutional Codes 270
9.1 Codes without a block structure 270
9.2 Trellis description of convolutional codes 273
9.3 Polynomial description of convolutional codes 278
9.4 Check matrices and inverse matrices 282
9.5 Error correction and distance notions 287
9.6 Matrix description of convolutional codes 289
9.7 The Wyner–Ash codes as convolutional codes 291
9.8 Syndrome decoding algorithms 294
9.9 Convolutional codes for correcting error bursts 298
9.10 Algebraic structure of convolutional codes 303
Problems 309
Notes 311
10 Beyond BCH Codes 313
10.1 Product codes and interleaved codes 314
10.2 Bicyclic codes 318
10.3 Concatenated codes 321
10.4 Cross-interleaved codes 323
10.5 Turbo codes 326
10.6 Justesen codes 329
Problems 332
Notes 334
11 Codes and Algorithms Based on Graphs 335
11.1 Distance, probability, and likelihood 336
11.2 The Viterbi algorithm 340
11.3 Sequential algorithms to search a trellis 343
11.4 Trellis description of linear block codes 350
11.5 Gallager codes 354
11.6 Tanner graphs and factor graphs 355
11.7 Posterior probabilities 357
11.8 The two-way algorithm 359
11.9 Iterative decoding of turbo codes 362
ix Contents
11.10 Tail-biting representations of block codes 364
11.11 The Golay code as a tail-biting code 368
Problems 372
Notes 374
12 Performance of Error-Control Codes 375
12.1 Weight distributions of block codes 375
12.2 Performance of block codes 383
12.3 Bounds on minimum distance of block codes 386
12.4 Binary expansions of Reed–Solomon codes 394
12.5 Symbol error rates on a gaussian-noise channel 399
12.6 Sequence error rates on a gaussian-noise channel 403
12.7 Coding gain 406
12.8 Capacity of a gaussian-noise channel 411
Problems 414
Notes 416
13 Codes and Algorithms for Majority Decoding 418
13.1 Reed–Muller codes 418
13.2 Decoding by majority vote 426
13.3 Circuits for majority decoding 430
13.4 Affine permutations for cyclic codes 433
13.5 Cyclic codes based on permutations 437
13.6 Convolutional codes for majority decoding 441
13.7 Generalized Reed–Muller codes 442
13.8 Euclidean-geometry codes 447
13.9 Projective-geometry codes 456
Problems 460
Notes 461
Bibliography 463
Index 473
QQ截图未命名.jpg
