Algebraic codes for data transmission

Richard E. Blahut0521553741, 9780521553742, 9780511077401

Error-correcting codes play a fundamental role in modern communications and data-storage systems. This volume provides an accessible introduction to the basic elements of algebraic codes and discusses their use in a variety of applications. The author describes a range of important coding techniques, including Reed-Solomon codes, BCH codes, trellis codes, and turbocodes. Throughout the book, mathematical theory is illustrated by reference to many practical examples. The book is written for graduate students of electrical and computer engineering and practicing engineers whose work involves communications or signal processing.

---

Table of contents :
Cover……Page 1
Half-title……Page 2
Title……Page 4
Copyright……Page 5
Contents……Page 6
Preface……Page 12
1 Introduction……Page 16
1.1 The discrete communication channel……Page 17
1.2 The history of data-transmission codes……Page 19
1.3 Applications……Page 21
1.4 Elementary concepts……Page 22
Repetition codes……Page 29
Hamming codes……Page 30
Problems……Page 32
2.1 Fields of characteristic two……Page 35
2.2 Groups……Page 38
2.3 Rings……Page 43
2.4 Fields……Page 45
2.5 Vector spaces……Page 47
2.6 Linear algebra……Page 52
Problems……Page 60
Notes……Page 63
3.1 Structure of linear block codes……Page 64
3.2 Matrix description of linear block codes……Page 65
3.3 Hamming codes……Page 69
3.4 The standard array……Page 71
3.5 Hamming spheres and perfect codes……Page 74
3.6 Simple modifications to a linear code……Page 77
Problems……Page 78
Notes……Page 81
4.1 The integer ring……Page 82
4.2 Finite fields based on the integer ring……Page 85
4.3 Polynomial rings……Page 87
4.4 Finite fields based on polynomial rings……Page 94
4.5 Primitive elements……Page 98
4.6 The structure of finite fields……Page 101
Problems……Page 107
Notes……Page 110
5.1 Viewing a code from an extension field……Page 111
5.2 Polynomial description of cyclic codes……Page 114
5.3 Minimal polynomials and conjugates……Page 119
5.4 Matrix description of cyclic codes……Page 126
5.5 Hamming codes as cyclic codes……Page 128
5.6 Cyclic codes for correcting double errors……Page 131
5.7 Quasi-cyclic codes and shortened cyclic codes……Page 133
5.8 The Golay code as a cyclic code……Page 134
5.9 Cyclic codes for correcting burst errors……Page 138
5.10 The Fire codes as cyclic codes……Page 140
5.11 Cyclic codes for error detection……Page 142
Problems……Page 143
Notes……Page 145
6.1 The Fourier transform……Page 146
6.2 Reed–Solomon codes……Page 153
6.3 Conjugacy constraints and idempotents……Page 158
6.4 Spectral description of cyclic codes……Page 163
6.5 BCH codes……Page 167
6.6 The Peterson–Gorenstein–Zierler decoder……Page 174
6.7 The Reed–Muller codes as cyclic codes……Page 181
6.8 Extended Reed–Solomon codes……Page 184
6.9 Extended BCH codes……Page 187
Problems……Page 190
Notes……Page 192
7.1 Spectral estimation in a finite field……Page 194
7.2 Synthesis of linear recursions……Page 198
7.3 Decoding of binary BCH codes……Page 206
7.4 Decoding of nonbinary BCH codes……Page 208
7.5 Decoding with erasures and errors……Page 216
7.6 Decoding in the time domain……Page 221
7.7 Decoding within the BCH bound……Page 225
7.8 Decoding beyond the BCH bound……Page 228
7.9 Decoding of extended Reed–Solomon codes……Page 231
7.10 Decoding with the euclidean algorithm……Page 232
Problems……Page 238
Notes……Page 241
8.1 Logic circuits for finite-field arithmetic……Page 243
8.2 Shift-register encoders and decoders……Page 250
8.3 The Meggitt decoder……Page 252
8.4 Error trapping……Page 259
8.5 Modified error trapping……Page 265
8.6 Architecture of Reed–Solomon decoders……Page 269
8.7 Multipliers and inverters……Page 273
8.8 Bit-serial multipliers……Page 277
Problems……Page 282
Notes……Page 284
9.1 Codes without a block structure……Page 285
9.2 Trellis description of convolutional codes……Page 288
9.3 Polynomial description of convolutional codes……Page 293
9.4 Check matrices and inverse matrices……Page 297
9.5 Error correction and distance notions……Page 302
9.6 Matrix description of convolutional codes……Page 304
9.7 The Wyner–Ash codes as convolutional codes……Page 306
9.8 Syndrome decoding algorithms……Page 309
9.9 Convolutional codes for correcting error bursts……Page 313
9.10 Algebraic structure of convolutional codes……Page 318
Problems……Page 324
Notes……Page 326
10 Beyond BCH Codes……Page 328
10.1 Product codes and interleaved codes……Page 329
10.2 Bicyclic codes……Page 333
10.3 Concatenated codes……Page 336
10.4 Cross-interleaved codes……Page 338
10.5 Turbo codes……Page 341
10.6 Justesen codes……Page 345
Problems……Page 348
Notes……Page 349
11 Codes and Algorithms Based on Graphs……Page 350
11.1 Distance, probability, and likelihood……Page 351
11.2 The Viterbi algorithm……Page 355
11.3 Sequential algorithms to search a trellis……Page 358
11.4 Trellis description of linear block codes……Page 365
11.5 Gallager codes……Page 369
11.6 Tanner graphs and factor graphs……Page 370
11.7 Posterior probabilities……Page 372
11.8 The two-way algorithm……Page 374
11.9 Iterative decoding of turbo codes……Page 377
11.10 Tail-biting representations of block codes……Page 379
11.11 The Golay code as a tail-biting code……Page 383
Problems……Page 387
Notes……Page 389
12.1 Weight distributions of block codes……Page 390
12.2 Performance of block codes……Page 398
12.3 Bounds on minimum distance of block codes……Page 401
12.4 Binary expansions of Reed–Solomon codes……Page 409
12.5 Symbol error rates on a gaussian-noise channel……Page 414
12.6 Sequence error rates on a gaussian-noise channel……Page 418
12.7 Coding gain……Page 421
12.8 Capacity of a gaussian-noise channel……Page 426
Problems……Page 429
Notes……Page 431
13.1 Reed–Muller codes……Page 433
13.2 Decoding by majority vote……Page 441
13.3 Circuits for majority decoding……Page 445
13.4 Affine permutations for cyclic codes……Page 448
13.5 Cyclic codes based on permutations……Page 452
13.6 Convolutional codes for majority decoding……Page 456
13.7 Generalized Reed–Muller codes……Page 457
13.8 Euclidean-geometry codes……Page 462
13.9 Projective-geometry codes……Page 471
Problems……Page 475
Notes……Page 476
Bibliography……Page 478
Index……Page 488