Date

Class Topic

Notes

Notes

1.

Mar 4

Codes as Combinatorial Objects (2 meetings)

·   Definition.

·         Upper and lower bounds on the dependence of distance on rate:

o   The Gilbert-Varshamov and Hamming bounds.

o   The Singleton bound

o   The Plotkin bound

o   List decoding, the Johnson bound and the Elias-Bassalygo bound, and,

[vL, Chapter 5]

[GRS,part II, Chapters 4-8]

2.

Mar 11

o   Lecturer: Bharat Ram Rangarajan

MacWilliams identity, Delsarte’s program, the LP bound. [Notes]

o   Lecturer: Bharat Ram Rangarajan

The LP bound via essential covering radius [Notes]

 Notes: The MRRW bound

Notes: The LP bound via essential covering radius

3-4.

Mar 18

April 8

Polynomial codes

·         Reed Solomon codes.

o   RS codes are cyclic

o   The dual

o   The Berlekamp-Welsh decoding algorithm.

·         Hasse Deriviatives. Multiplicities.

o   The Sudan and Guruswami-Sudan list decoding algorithms. 

5-6.

April 22

April 29

Bezout theorem and some algebraic evaluation codes

·         A [19,6,13]_13 code (Taken from Madu Sudan's class "Essential coding theory", 2001, Lecture 7).

Mar 18,

·         Resultants

·         Bezout's theorem.

·         Elliptic curves.

·         Hermitian codes.

Not done: The Mordell-Weil group of rational points.

4.

Apr 8

Alegebraic-Geometric codes (AG) codes (a.k.a Goppa codes). (2-3 meetings).

·         The setting: Algebraic function fields. Places. Divisors. Riemann spaces. The genus.

·         Examples: The rational function field, Hermetian function field, Elliptic curves.

·         Expressing the rate and designated distance in terms of dimension and degree of the algebraic objects. The Riemann-Roch theorem (simplified to the case where the degree is above 2g).

·         Decoding AG codes. Generalizing the Guruswami-Sudan list decoding algorithm.

·         The Riemann-roch function (unabridged). The dual code. Examples.

5.

Apr 22

The Garcia-Stichtenoth construction. (2-3 meetings). Following [GS, Chapter 1].

·         Finite extensions of algebraic function fields. Ramification. Kummer's lemma. Abhyankar's lemma.

·         Tower constructions. Tame towers. Ramification locus and splitting rate.

·         Explicit tame towers. A subset of T1, T2 and T3 of [GS, Chapter 1.4].

·         Beating the GV bound for F_49.

·         Optional: How far can we go? The hasse-Weil theorem and the Drinfeld-Vladut bound.

6.

Apr 29

7. May 6

8.

May 13

9.

May 20

10.

May 27

11.

Jun 3

12.

Jun 10

13.

Jun 17