Algebraic geometry is often employed to encode and decode signals transmitted in communication systems. This book describes the fundamental principles of algebraic coding theory from the perspective of an engineer, discussing a number of applications in communications and signal processing. The principal concept is that of using algebraic curves over finite fields to construct error-correcting codes. The most recent developments are presented including the theory of codes on curves, without the use of detailed mathematics, substituting the intense theory of algebraic geometry with Fourier transform where possible. The author describes the codes and corresponding decoding algorithms in a manner that allows the reader to evaluate these codes against practical applications, or to help with the design of encoders and decoders. This book is relevant to practicing communication engineers and those involved in the design of new communication systems, as well as graduate students and researchers in electrical engineering.
Author(s): Richard Blahut
Year: 2008
Language: English
Pages: 576
Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 9
List of figures......Page 14
List of tables......Page 17
Preface......Page 19
1 Sequences and the One-Dimensional Fourier Transform......Page 25
1.1 Fields......Page 26
1.2 The Fourier transform......Page 32
1.3 Properties of the Fourier transform......Page 36
1.4 Univariate and homogeneous bivariate polynomials......Page 40
1.5 Linear complexity of sequences......Page 44
1.6 Massey's theorem for sequences......Page 47
1.7 Cyclic complexity and locator polynomials......Page 49
1.8 Bounds on the weights of vectors......Page 54
1.9 Subfields, conjugates, and idempotents......Page 58
1.10 Semifast algorithms based on conjugacy......Page 63
1.11 The Gleason--Prange theorem......Page 66
1.12 The Rader algorithm......Page 73
Problems......Page 77
Notes......Page 78
2.1 Linear codes, weight, and distance......Page 80
2.2 Cyclic codes......Page 84
2.3 Codes on the affine line and the projective line......Page 88
2.4 The wisdom of Solomon and the wizardry of Reed......Page 90
2.5 Encoders for Reed–Solomon codes......Page 94
2.6 BCH codes......Page 96
2.7 Melas codes and Zetterberg codes......Page 99
2.8 Roos codes......Page 100
2.9 Quadratic residue codes......Page 101
2.10 The binary Golay code......Page 110
2.11 A nonlinear code with the cyclic property......Page 113
2.12 Alternant codes......Page 116
2.13 Goppa codes......Page 123
2.14 Codes for the Lee metric......Page 132
2.15 Galois rings......Page 137
2.16 The Preparata, Kerdock, and Goethals codes......Page 146
Problems......Page 156
Notes......Page 159
3 The Many Decoding Algorithms for Reed–Solomon Codes......Page 161
3.1 Syndromes and error patterns......Page 162
3.2 Computation of the error values......Page 168
3.3 Correction of errors of weight 2......Page 172
3.4 The Sugiyama algorithm......Page 175
3.5 The Berlekamp–Massey algorithm......Page 179
3.6 Decoding of binary BCH codes......Page 187
3.7 Putting it all together......Page 188
3.8 Decoding in the code domain......Page 191
3.9 The Berlekamp algorithm......Page 194
3.10 Systolic and pipelined algorithms......Page 197
3.11 The Welch–Berlekamp decoder......Page 200
3.12 The Welch–Berlekamp algorithm......Page 205
Problems......Page 210
Notes......Page 212
4 Within or Beyond the Packing Radius......Page 214
4.1 Weight distributions......Page 215
4.2 Distance structure of Reed–Solomon codes......Page 220
4.3 Bounded-distance decoding......Page 222
4.4 Detection beyond the packing radius......Page 224
4.5 Detection within the packing radius......Page 226
4.6 Decoding with both erasures and errors......Page 227
4.7 Decoding beyond the packing radius......Page 229
4.8 List decoding of some low-rate codes......Page 231
4.9 Bounds on the decoding radius and list size......Page 236
4.10 The MacWilliams equation......Page 241
Problems......Page 245
Notes......Page 247
5.1 The two-dimensional Fourier transform......Page 248
5.2 Properties of the two-dimensional Fourier transform......Page 250
5.3 Bivariate and homogeneous trivariate polynomials......Page 253
5.4 Polynomial evaluation and the Fourier transform......Page 256
5.5 Intermediate arrays......Page 258
5.6 Fast algorithms based on decimation......Page 259
5.7 Bounds on the weights of arrays......Page 261
Problems......Page 269
Notes......Page 270
6.1 Bicyclic codes......Page 271
6.2 Codes on the affine plane and the projective plane......Page 275
6.3 Minimum distance of bicyclic codes......Page 277
6.4 Bicyclic codes based on the multilevel bound......Page 279
6.5 Bicyclic codes based on the BCH bound......Page 282
6.6 The (21, 12, 5) bicyclic BCH code......Page 284
6.7 The Turyn representation of the (21, 12, 5) BCH code......Page 287
6.8 The (24, 12, 8) bivariate Golay code......Page 290
6.9 The (24, 14, 6) Wagner code......Page 294
6.10 Self-dual codes......Page 297
Problems......Page 298
Notes......Page 299
7.1 Polynomial representations of arrays......Page 301
7.2 Ordering the elements of an array......Page 303
7.3 The bivariate division algorithm......Page 308
7.4 The footprint and minimal bases of an ideal......Page 315
7.5 Reduced bases and quotient rings......Page 320
7.6 The Buchberger theorem......Page 325
7.7 The locator ideal......Page 336
7.8 The Bézout theorem......Page 342
7.9 Nullstellensätze......Page 350
7.10 Cyclic complexity of arrays......Page 355
7.11 Enlarging an ideal......Page 357
Problems......Page 368
Notes......Page 369
8.1 The Buchberger algorithm......Page 371
8.2 Connection polynomials......Page 375
8.3 The Sakata–Massey theorem......Page 382
8.4 The Sakata algorithm......Page 385
8.5 An example......Page 391
8.6 The Koetter algorithm......Page 408
Problems......Page 411
Notes......Page 413
9.1 Curves in the plane......Page 414
9.2 The Hasse–Weil bound......Page 417
9.3 The Klein quartic polynomial......Page 418
9.4 The hermitian polynomials......Page 420
9.5 Plane curves and the two-dimensional Fourier transform......Page 426
9.6 Monomial bases on the plane and on curves......Page 428
9.7 Semigroups and the Feng–Rao distance......Page 434
9.8 Bounds on the weights of vectors on curves......Page 441
Problems......Page 448
Notes......Page 450
10 Codes on Curves and Surfaces......Page 452
10.1 Beyond Reed–Solomon codes......Page 453
10.2 Epicyclic codes......Page 455
10.3 Codes on affine curves and projective curves......Page 460
10.4 Projective hermitian codes......Page 464
10.5 Affine hermitian codes......Page 466
10.6 Epicyclic hermitian codes......Page 469
10.7 Codes shorter than hermitian codes......Page 471
Problems......Page 474
Notes......Page 475
11 Other Representations of Codes on Curves......Page 477
11.1 Shortened codes from punctured codes......Page 478
11.2 Shortened codes on hermitian curves......Page 483
11.3 Quasi-cyclic hermitian codes......Page 487
11.4 The Klein codes......Page 489
11.5 Klein codes constructed from Reed–Solomon codes......Page 491
11.6 Hermitian codes constructed from Reed–Solomon codes......Page 497
Problems......Page 504
Notes......Page 506
12 The Many Decoding Algorithms for Codes on Curves......Page 508
12.1 Two-dimensional syndromes and locator ideals......Page 509
12.2 The illusion of missing syndromes......Page 511
12.3 Decoding of hyperbolic codes......Page 513
12.4 Decoding of hermitian codes......Page 521
12.5 Computation of the error values......Page 531
12.6 Supercodes of hermitian codes......Page 533
12.7 The Feng–Rao decoder......Page 536
12.8 The theory of syndrome filling......Page 540
Problems......Page 546
Notes......Page 547
Bibliography......Page 549
Index......Page 558
