Codes and Curves (Student Mathematical Library, Vol. 7)
Judy L. Walker
Format: PDF / Kindle (mobi) / ePub
When information is transmitted, errors are likely to occur. This problem has become increasingly important as tremendous amounts of information are transferred electronically every day. Coding theory examines efficient ways of packaging data so that these errors can be detected, or even corrected. The traditional tools of coding theory have come from combinatorics and group theory. Since the work of Goppa in the late 1970s, however, coding theorists have added techniques from algebraic geometry to their toolboxes. In particular, by re-interpreting the Reed-Solomon codes as coming from evaluating functions associated to divisors on the projective line, one can see how to define new codes based on other divisors or on other algebraic curves. For instance, using modular curves over finite fields, Tsfasman, Vladut, and Zink showed that one can define a sequence of codes with asymptotically better parameters than any previously known codes. This monograph is based on a series of lectures the author gave as part of the IAS/PCMI program on arithmetic algebraic geometry. Here, the reader is introduced to the exciting field of algebraic geometric coding theory. Presenting the material in the same conversational tone of the lectures, the author covers linear codes, including cyclic codes, and both bounds and asymptotic bounds on the parameters of codes. Algebraic geometry is introduced, with particular attention given to projective curves, rational functions and divisors. The construction of algebraic geometric codes is given, and the Tsfasman-Vladut-Zink result mentioned above is discussed. No previous experience in coding theory or algebraic geometry is required. Some familiarity with abstract algebra, in particular finite fields, is assumed. However, this material is reviewed in two appendices. There is also an appendix containing projects that explore other codes not covered in the main text.
of k[x]/ f (x) as polynomials of degree at most d − 1. Now, however, these polynomials will form a field by Exercises B.4 and B.5 above. To avoid confusion, we’ll write α for the element of the field k[x]/ f (x) which corresponds to x. Exercise B.6. Let g(x) = x3 + x + 1 ∈ F2 [x]. a) Show that g(x) is irreducible in F2 [x]. Conclude that F := F2 [x]/ g(x) is a field. b) How many elements does F have? List them. Make an addition table and a multiplication table. B.2. Classification of Finite
B.10, f − g has degree at least q − 1. But f − g ∈ Lk , which implies f = g. Thus C has dimension exactly k. To find the minimum distance, we’ll use Exercise 1.6 and find the minimum weight instead. So, suppose f ∈ Lk−1 and wt( (f )) = d = dmin . Then f has at least n − d zeros, so it has degree at least n − d (again using Exercise B.10). Since f ∈ Lk−1 , this means that n − d ≤ k − 1, or, equivalently, d ≥ n − k + 1. In Chapter 2.1, we will show that, in fact, we have d = n − k + 1. 6 1.
Suppose first that f (x) ∈ I is monic of degree . If f (x) = g(x), then f (x) − g(x) is a polynomial of degree strictly less than in I. Multiplying by an appropriate scalar yields a monic polynomial, which contradicts the minimality of , proving (a). To prove (b), let c(x) be any element of I. Lifting to Fq [x], we can use the division algorithm to write c(x) = f (x)g(x) + r(x) for polynomials f (x) and r(x) with r(x) either 0 or of degree strictly less than . Since c(x), g(x) and r(x) all have
encouraged to work through them. Of the sources listed in the bibliography, it should be pointed out that [CLO2], [Ga], [H], [L], [MS], [NZM] and [S] were used most intensively in preparing these notes. In particular: • Theorem 1.11, which gives some important properties of cyclic codes, can be found in [MS]. xi xii Preface • The proof given for the Singleton Bound (Theorem 2.1) is from [S]. • The proofs given for the Plotkin Bound (Theorem 2.3), the Gilbert-Varshamov Bound (Theorem 2.4),
Heitsch, who did a great job coordinating problem sessions for my lectures; Graham Leuschke and Mark Walker, who proofread the various drafts of these notes; and, most importantly, the thirteen amazingly bright undergraduate women who participated in the program — Heidi Basler, Lauren Baynes, Juliana Belding, Mariana Campbell, Janae Caspar, Sarah Gruhn, Catherine Holl, Theresa Kim, Sarah Moss, Katarzyna Potocka, Camilla Smith, Michelle Wang, and Lauren Williams. Judy L. Walker Chapter 1