Computer Science

Algebraic Error Correcting Codes
0368.4357.01

Spring 2013

Lectures

Monday 10:0013:00,
Orenstein 110 
Instructor

Amnon TaShma  Schreiber 127  6405364 
· Final grades for HomeWorks are
Textbooks

Main references:
Other textbooks:

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
GilbertVarshamov and Hamming bounds. o The
Singleton bound o The Plotkin bound o List
decoding, the Johnson bound and the EliasBassalygo
bound, and, 
[vL,
Chapter 5] [GRS,part
II, Chapters 48] 

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] 


34. Mar 18 April 8 
Polynomial
codes 
·
Reed Solomon codes. o RS
codes are cyclic o The
dual o The BerlekampWelsh decoding algorithm. ·
Hasse Deriviatives. Multiplicities. o The
Sudan and GuruswamiSudan list decoding
algorithms. 

56. 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 MordellWeil group of rational points. 

4. Apr 8 
AlegebraicGeometric
codes (AG) codes (a.k.a Goppa
codes). (23 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 RiemannRoch
theorem (simplified to the case where the degree is above 2g). ·
Decoding AG codes. Generalizing the GuruswamiSudan
list decoding algorithm. ·
The Riemannroch function (unabridged).
The dual code. Examples. 

5. Apr 22 
The
GarciaStichtenoth construction. (23 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 hasseWeil
theorem and the DrinfeldVladut 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 




