Algebraic codes on lines, planes, and curves : an engineering approach

Title:

Personal Author:

Blahut, Richard E.

Publication Information:

New York : Cambridge Univ Pr, 2008

Physical Description:

xix, 543 p. : ill. ; 26 cm.

ISBN:

9780521771948

Subject Term:

Signal processing -- Mathematics

Coding theory

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010170238	TK5102.9 B524 2008	Open Access Book	Book	Searching... Unknown

The past few years have witnessed significant developments in algebraic coding theory. This book provides an advanced treatment of the subject from an engineering perspective, covering the basic principles and their application in communications and signal processing. Emphasis is on codes defined on the line, on the plane, and on curves, with the core ideas presented using commutative algebra and computational algebraic geometry made accessible using the Fourier transform. Starting with codes defined on a line, a background framework is established upon which the later chapters concerning codes on planes, and on curves, are developed. The decoding algorithms are developed using the standard engineering approach applied to those of Reed-Solomon codes, enabling them to be evaluated against practical applications. Integrating recent developments in the field into the classical treatment of algebraic coding, this is an invaluable resource for graduate students and researchers in telecommunications and applied mathematics.

Reviews 1

Choice Review

Coding here refers to the formal transcription of abstract information with the aim of achieving some combination of efficiency, reliability, and perhaps security. As a subject new in the 20th century, with both deep mathematical content and dramatic practical implications, information theory has few rivals. Codes provides the student an initiation and shows the author's great talent for mathematical exposition clearly propelled by big ideas. In this sleek, pared-down approach, each section brings a major conceptual advance with much of the possible variation and elaboration simply left for further reading. Biggs (mathematics, London School of Economics, UK) pushes hard enough to leave the reader apt and ready to pursue mastery. He devotes half the book to classical information theory, data compression, and error correction, half to cryptography, including schemes based on number theory (RSA and elliptic curve cryptosystems).Blahut's Algebraic Codes on Lines, Planes, and Curves represents the sort of elaboration that Biggs's book suppresses, in this case concerning error-correcting codes. When transmitting information over a noisy channel, as when a satellite beams pictures to Earth, one must build in redundancy to counter random corruptions of the signal. Redundancy necessarily slows transmission, but the right coding, one accounting for the engineering assumptions particular to the situation, can achieve a valuable trade-off. The abstract nature of this problem has lent itself to assaults via quite abstruse mathematics, particularly as of late the algebraic geometry of curves over finite fields. Blahut (electrical and computer engineering, Univ. of Illinois, Urbana-Champaign) performs a great service by rendering these newer results accessible to those who might wish to apply them. Thus he gives readers a rich, detailed, but fundamentally elementary take on material previously available only to specialists. Both works will be valuable for academic libraries. Summing Up: Highly recommended. Advanced academic audiences, upper-division undergraduates through researchers/faculty. D. V. Feldman University of New Hampshire

List of figures	p. xii
List of tables	p. xv
Preface	p. xvii
1 Sequences and the One-Dimensional Fourier Transform	p. 1
1.1 Fields	p. 2
1.2 The Fourier transform	p. 8
1.3 Properties of the Fourier transform	p. 12
1.4 Univariate and homogeneous bivariate polynomials	p. 16
1.5 Linear complexity of sequences	p. 20
1.6 Massey's theorem for sequences	p. 23
1.7 Cyclic complexity and locator polynomials	p. 25
1.8 Bounds on the weights of vectors	p. 30
1.9 Subfields, conjugates, and idempotents	p. 34
1.10 Semifast algorithms based on conjugacy	p. 39
1.11 The Gleason-Prange theorem	p. 42
1.12 The Rader algorithm	p. 49
Problems	p. 53
Notes	p. 54
2 The Fourier Transform and Cyclic Codes	p. 56
2.1 Linear codes, weight, and distance	p. 56
2.2 Cyclic codes	p. 60
2.3 Codes on the affine line and the projective line	p. 64
2.4 The wisdom of Solomon and the wizardry of Reed	p. 66
2.5 Encoders for Reed-Solomon codes	p. 70
2.6 BCH codes	p. 72
2.7 Melas codes and Zetterberg codes	p. 75
2.8 Roos codes	p. 76
2.9 Quadratic residue codes	p. 77
2.10 The binary Golay code	p. 86
2.11 A nonlinear code with the cyclic property	p. 89
2.12 Alternant codes	p. 92
2.13 Goppa codes	p. 99
2.14 Codes for the Lee metric	p. 108
2.15 Galois rings	p. 113
2.16 The Preparata, Kerdock, and Goethals codes	p. 122
Problems	p. 132
Notes	p. 135
3 The Many Decoding Algorithms for Reed-Solomon Codes	p. 137
3.1 Syndromes and error patterns	p. 138
3.2 Computation of the error values	p. 144
3.3 Correction of errors of weight 2	p. 148
3.4 The Sugiyama algorithm	p. 151
3.5 The Berlekamp-Massey algorithm	p. 155
3.6 Decoding of binary BCH codes	p. 163
3.7 Putting it all together	p. 164
3.8 Decoding in the code domain	p. 167
3.9 The Berlekamp algorithm	p. 170
3.10 Systolic and pipelined algorithms	p. 173
3.11 The Welch-Berlekamp decoder	p. 176
3.12 The Welch-Berlekamp algorithm	p. 181
Problems	p. 186
Notes	p. 188
4 Within or Beyond the Packing Radius	p. 190
4.1 Weight distributions	p. 191
4.2 Distance structure of Reed-Solomon codes	p. 196
4.3 Bounded-distance decoding	p. 198
4.4 Detection beyond the packing radius	p. 200
4.5 Detection within the packing radius	p. 202
4.6 Decoding with both erasures and errors	p. 203
4.7 Decoding beyond the packing radius	p. 205
4.8 List decoding of some low-rate codes	p. 207
4.9 Bounds on the decoding radius and list size	p. 212
4.10 The MacWilliams equation	p. 217
Problems	p. 221
Notes	p. 223
5 Arrays and the Two-Dimensional Fourier Transform	p. 224
5.1 The two-dimensional Fourier transform	p. 224
5.2 Properties of the two-dimensional Fourier transform	p. 226
5.3 Bivariate and homogeneous trivariate polynomials	p. 229
5.4 Polynomial evaluation and the Fourier transform	p. 232
5.5 Intermediate arrays	p. 234
5.6 Fast algorithms based on decimation	p. 235
5.7 Bounds on the weights of arrays	p. 237
Problems	p. 245
Notes	p. 246
6 The Fourier Transform and Bicyclic Codes	p. 247
6.1 Bicyclic codes	p. 247
6.2 Codes on the affine plane and the projective plane	p. 251
6.3 Minimum distance of bicyclic codes	p. 253
6.4 Bicyclic codes based on the multilevel bound	p. 255
6.5 Bicyclic codes based on the BCH bound	p. 258
6.6 The (21, 12, 5) bicyclic BCH code	p. 260
6.7 The Turyn representation of the (21, 12, 5) BCH code	p. 263
6.8 The (24, 12, 8) bivariate Golay code	p. 266
6.9 The (24, 14, 6) Wagner code	p. 270
6.10 Self-dual codes	p. 273
Problems	p. 274
Notes	p. 275
7 Arrays and the Algebra of Bivariate Polynomials	p. 277
7.1 Polynomial representations of arrays	p. 277
7.2 Ordering the elements of an array	p. 279
7.3 The bivariate division algorithm	p. 284
7.4 The footprint and minimal bases of an ideal	p. 291
7.5 Reduced bases and quotient rings	p. 296
7.6 The Buchberger theorem	p. 301
7.7 The locator ideal	p. 312
7.8 The Bezout theorem	p. 318
7.9 Nullstellensatze	p. 326
7.10 Cyclic complexity of arrays	p. 331
7.11 Enlarging an ideal	p. 333
Problems	p. 344
Notes	p. 345
8 Computation of Minimal Bases	p. 347
8.1 The Buchberger algorithm	p. 347
8.2 Connection polynomials	p. 351
8.3 The Sakata-Massey theorem	p. 358
8.4 The Sakata algorithm	p. 361
8.5 An example	p. 367
8.6 The Koetter algorithm	p. 384
Problems	p. 387
Notes	p. 389
9 Curves, Surfaces, and Vector Spaces	p. 390
9.1 Curves in the plane	p. 390
9.2 The Hasse-Weil bound	p. 393
9.3 The Klein quartic polynomial	p. 394
9.4 The hermitian polynomials	p. 396
9.5 Plane curves and the two-dimensional Fourier transform	p. 402
9.6 Monomial bases on the plane and on curves	p. 404
9.7 Semigroups and the Feng-Rao distance	p. 410
9.8 Bounds on the weights of vectors on curves	p. 417
Problems	p. 424
Notes	p. 426
10 Codes on Curves and Surfaces	p. 428
10.1 Beyond Reed-Solomon codes	p. 429
10.2 Epicyclic codes	p. 431
10.3 Codes on affine curves and projective curves	p. 436
10.4 Projective hermitian codes	p. 440
10.5 Affine hermitian codes	p. 442
10.6 Epicyclic hermitian codes	p. 445
10.7 Codes shorter than hermitian codes	p. 447
Problems	p. 450
Notes	p. 451
11 Other Representations of Codes on Curves	p. 453
11.1 Shortened codes from punctured codes	p. 454
11.2 Shortened codes on hermitian curves	p. 459
11.3 Quasi-cyclic hermitian codes	p. 463
11.4 The Klein codes	p. 465
11.5 Klein codes constructed from Reed-Solomon codes	p. 467
11.6 Hermitian codes constructed from Reed-Solomon codes	p. 473
Problems	p. 480
Notes	p. 482
12 The Many Decoding Algorithms for Codes on Curves	p. 484
12.1 Two-dimensional syndromes and locator ideals	p. 485
12.2 The illusion of missing syndromes	p. 487
12.3 Decoding of hyperbolic codes	p. 489
12.4 Decoding of hermitian codes	p. 497
12.5 Computation of the error values	p. 507
12.6 Supercodes of hermitian codes	p. 509
12.7 The Feng-Rao decoder	p. 512
12.8 The theory of syndrome filling	p. 516
Problems	p. 522
Notes	p. 523
Bibliography	p. 525
Index	p. 534

Available:*

On Order

Summary

Summary

Reviews 1

Choice Review

Table of Contents