"Advances in Algebraic Geometry Codes" presents the most successful applications of algebraic geometry to the field of error-correcting codes, which are used in the industry when one sends information through a noisy channel. The noise in a channel is the corruption of a part of the information due to either interferences in the telecommunications or degradation of the information-storing support (for instance, compact disc). An error-correcting code thus adds extra information to the message to be transmitted with the aim of recovering the sent information. With contributions form renowned researchers, this pioneering book will be of value to mathematicians, computer scientists, and engineers in information theory.
Author(s): Edgar Martinez-moro, Diego Ruano
Series: Series on coding theory and cryptology 5
Publisher: World Scientific
Year: 2008
Language: English
Pages: 453
City: Singapore; Hackensack, N.J
Contents......Page 8
Preface......Page 6
Contents......Page 10
1.1 Linear codes and the a ne line......Page 11
1.1.1 Dimension and in nite families......Page 12
1.1.2 Duality and di erentials......Page 13
1.1.3 Minimum distance......Page 14
1.1.4 Error correction......Page 15
1.1.5 Linear secret sharing schemes......Page 17
1.1.6 Weight distributions and codes over extension elds......Page 20
1.2.1. Reed-Solomon and BCH codes......Page 22
1.2.2. Classical Goppa codes......Page 23
1.2.3. Dual BCH codes......Page 25
1.3. Reed-Muller codes......Page 28
1.4. Geometric Goppa codes......Page 30
1.4.1. Curves and linear codes......Page 31
1.4.2. Duality and differentials......Page 33
1.4.3. Families of curves......Page 35
1.4.4. One-point codes......Page 38
1.4.5. Two-point codes......Page 41
1.4.6. Error correction......Page 43
1.4.7. Secret reconstruction for algebraic-geometric LSSSs......Page 46
1.4.8. Weight distributions......Page 50
References......Page 53
2.1. Introduction......Page 58
2.2.1. Decoding......Page 59
2.2.2. The basic algorithm for decoding of algebraic geome- try codes......Page 60
2.3. Syndrome formulation of the basic algorithm......Page 61
2.4. The generalized order bound......Page 70
2.5. Majority voting......Page 78
2.6. List decoding of algebraic geometry codes......Page 86
2.7. Syndrome formulation of list decoding......Page 94
2.8. Literature......Page 105
References......Page 106
Contents......Page 108
3.1. Introduction......Page 109
3.2.1. Reed-Solomon codes......Page 111
3.2.2. Polynomials for decoding......Page 112
3.2.3. The key equation and the Berlekamp-Massey algorithm......Page 114
3.2.4. Error evaluation without the evaluator polynomial......Page 117
3.2.5. Connections to the Euclidean algorithm......Page 118
3.3. The key equation for Hermitian codes......Page 120
3.3.1. The Hermitian curve......Page 121
3.3.3. Polynomials for decoding......Page 122
3.3.4. Another basis for Fq2(x; y)......Page 126
3.3.5. The key equation......Page 128
3.3.6. Solving the key equation......Page 131
3.3.7. Error evaluation without the error evalua- tor polynomials......Page 135
3.3.8. An example......Page 137
3.4.1. Curves, function fields and differentials......Page 140
3.4.2. One-point codes and their duals......Page 142
3.4.3. The trace and a dual basis......Page 143
3.4.4. Polynomials for decoding......Page 147
3.4.5. The key equation and its solution......Page 150
3.4.6. Error evaluation without the error evaluator polynomials......Page 152
3.5. Bibliographical notes......Page 155
References......Page 156
4.1. Introduction......Page 162
4.2. Affine variety codes......Page 163
4.3. Some Grobner basis theoretical tools......Page 164
4.4. A bound on the minimum distance of C(I; L)......Page 166
4.5. The Feng-Rao bound for C(I; L)?......Page 169
4.6. Using weighted degree orderings......Page 172
4.7. The order domain conditions......Page 177
4.8. Weight functions and order domains......Page 181
4.9. Codes form order domains......Page 182
4.10. One-point geometric Goppa codes......Page 185
4.11. Bibliographical Notes......Page 187
References......Page 188
5.1. Introduction......Page 190
5.2. Preliminaries......Page 193
5.3. Two Constructions of Asymptotically Good Codes......Page 195
5.4. The Stichtenoth-Xing Construction......Page 209
5.5. Improved Bounds Using Distinguished Divisors......Page 214
Acknowledgments......Page 227
References......Page 228
Introduction......Page 230
6.1. The Function Nq(g)......Page 235
6.2. Asymptotic Problems......Page 239
6.3. Zeta-functions and Linear Series......Page 240
6.4. A Characterization of the Suzuki Curve......Page 243
6.5. Maximal Curves......Page 249
References......Page 260
Contents......Page 266
7.1. Introduction......Page 267
7.1.1. Notation......Page 269
7.2. The General Construction......Page 270
7.3.1. Elementary bounds......Page 272
7.3.2. Bounds from covering families of curves......Page 273
7.3.4. Bounds from S itself......Page 275
7.3.5. General Weil-type bounds......Page 277
7.4.1. Quadrics......Page 279
7.4.2. Hermitian hypersurfaces......Page 281
7.4.3. Grassmannians and flag varieties......Page 283
7.4.4. Blow-ups and Del Pezzo surfaces......Page 287
7.4.5. Ruled surfaces and generalizations......Page 289
7.4.6. Other work on codes from surfaces......Page 290
7.5. Codes from Deligne-Lusztig Varieties......Page 291
7.6. Connections with Other Code Constructions......Page 293
7.7. Code Comparisons......Page 294
7.8. Bibliographic Notes......Page 296
References......Page 299
Contents......Page 304
8.1.1. Cones, fans, polytopes and toric varieties......Page 305
8.1.2. Properties of toric varieties......Page 310
8.1.3. Orbits and divisors......Page 312
8.2. Definition of toric codes......Page 314
8.4. Structure of toric codes......Page 317
8.4.2. Dual of a toric code......Page 318
8.5.1. Bound with Minkowski sum......Page 320
8.5.2. Bound with Minkowski length......Page 321
8.5.3. Bound with intersection theory......Page 323
8.7. Bibliographical notes......Page 328
References......Page 329
9.1. Introduction......Page 332
9.1.1. Codes over Rings......Page 334
9.1.2. Curves over Rings......Page 336
9.2. Algebraic Geometric Codes over Rings......Page 340
9.3. Non-Hamming Weights and Exponential Sums......Page 345
9.4.1. The Basic Algorithm for the Hamming Metric......Page 349
9.4.2. List Decoding for the Hamming Metric......Page 354
9.4.3. The Koetter-Vardy Algorithm for Decoding with Other Metrics......Page 362
9.5. Conclusion......Page 367
References......Page 368
10.1. Introduction......Page 372
10.2. Generalized Hamming weights......Page 373
10.3.1. The gonality sequence......Page 374
10.3.2. Extending the Goppa bound......Page 377
10.3.3. One-point codes and the Weierstrass semigroup......Page 378
10.3.4. Extending the order bound......Page 380
10.4.1. Trellises and codes......Page 384
10.4.2. Minimal trellises......Page 385
10.5. Linking the problems......Page 387
10.6.1. A Goppa-like bound on s(C)......Page 388
10.6.2. Another bound on the trellis state complexity......Page 389
10.7. Bibliographical notes......Page 394
References......Page 396
11.1. Introduction......Page 400
11.2. Convolutional Codes......Page 402
11.2.1. Convolutional encoders. Linear systems and circuits......Page 404
11.2.2. Basic encoders. Degree of a convolutional code......Page 408
11.2.3. Minimal basic encoders. Canonical encoders......Page 412
11.2.4. Dual code. Parity-check (control) matrix......Page 414
11.3. Convolutional Goppa codes......Page 415
11.3.1. Dual convolutional Goppa codes......Page 417
11.4. Weights and (free)distance......Page 418
11.5. Convolutional Goppa Codes over the projective line......Page 421
11.6. Convolutional Goppa Codes over elliptic curves......Page 424
References......Page 425
Contents......Page 428
12.2.1. Background and terminology......Page 429
12.2.2. Bounds on quantum codes......Page 434
12.3. Relating quantum codes and classical codes......Page 435
12.3.2. CSS construction......Page 436
12.4. Quantum codes constructed from algebraic geometry codes......Page 439
12.4.1.1. Quantum Reed-Solomon codes......Page 441
12.4.1.2. Quantum Hermitian codes......Page 442
12.4.2. More general AG constructions......Page 443
12.4.3. Quantum codes from hyperelliptic curves......Page 446
12.4.4. Asymptotic results......Page 447
12.5. Bibliographical notes......Page 450
References......Page 451
