Error correcting codes are combinatorial objects that allow sending and recovering messages transmitted through noisy channels. Error correcting codes have many applications in both theory and practice in computer science. This class gives an introduction to coding theory with an algorithmic focus.
Requirements:
In the end of the semester there will be a home assignment. Following the home assignment, I may decide to conduct an oral exam (to make sure that students indeed prepared the solutions).
Course material:
The course will be mostly based on a course given by Madhu Sudan at MIT. A link to the page of the course is here. A very similar course was given by Venkat Guruswami. The link is here.
Both pages contain online lecture notes that cover the material to be presented in class.
I recommend the following text by Madhu Sudan that refreshes the basic algebra needed for this course.
Home assignment:
The most updated version is here. (modified 22/1).
The current deadline is 31/1/2007. Please submit in my mailbox:
List of corrections to the assignment:
1. (22/1) The definition of Dual code was corrected.
2. (22/1) Q3a the distance was changed from (1-\epsilon)k to (1-\epsilon)n.
3. (22/1) Q4 the distance was changed from (1-\epsilon) to (1-\epsilon)n.
Lectures
1. Introduction: (I'm not giving any particular reference here. The definitions can be found in the end of Sudan's lecture 2).
Motivation for error correcting codes. Course outline. Hamming Distance. Definition of error correcting codes. Codes with distance 2t+1 correct t errors. A sketch of Reed Solomon codes. Application to low communication protocol for comparing two files.
2. Linear codes: (This lecture is covered in Lecture 3 in Sudan's course).
The notion of linear codes. Algebra reminder: Fields, Vector spaces, Extension fields constructed using polynomialsGenerating Matrix and parity check matrix. Distance and Hamming weight. Hamming Code. Algorithm for decoding Hamming code.
3. Polynomial based codes: (The lecture is covered in Lectures 3,4 in Sudan's course).
Hamming bound. Building an (n+1,k,2t+2)_2 code from an (n,k,2t+1)_2 code. (In Sudan's lecture 3).
Singleton bound, Reed-Solomon code, Codes based on bivariate polynomials. (In Sudan's lecture 4).
Next week we continue with polynomial based codes.
4. More on polynomial based codes: (The lecture is covered in Lectures 3,4 in Sudan's course).
The Schwartz-Zippel Lemma and applications in theoretical computer science.
Reed-Muller codes. Various settings of parameters:
degree l=k^{\epsilon}, number of variables m=constant, alphabet q=O(l).
degree l~log^{O(1)} k, number of variables m=log k/loglog k, alphabet q=O(l).
degree l=1, number of variables m=k, alphabet q=2. (Hadamard code).
5. Random codes: (The lecture serves as an introduction to the Gilbert-Varshamov bound which will be covered next week and appears in Sudan's notes, more details next week).
The Chernoff inequality. The probabilistic method. The union bound proof technique.
Existence of asymptotically good codes.
The corrections method.
The entropy function and information theoretic interpretation of the Hamming bound. (R < 1-H(\delta/2) ).
6. The Gilbert-Varshamov bound: Lectures 5-6 in Sudan's course.
The bounds and proofs. Wozencraft's construction.
Concatenation of codes.
7. Explicit construction of codes. (Sudan's lecture 6)
The notion of explicit construction.
Concatenation of RS and Hadamard (and repeated Concatenation).
Forney codes and Justesen codes.
Introduction to BCH codes (code definition without analysis of the distance).
8. Efficient Decoding of RS: (Sudan's lecture 10)
The Welch-Berlekamp algorithm.
9. Efficient decoding of concatenated codes: (Sudan's lecture 11 section 2).
Decoding up to 1/4 of the distance.
Decoding up to 1/2 of the distance.
10. LDPC codes: (Link to relevant lecture in Sudan's 2002 course).