Algorithmic Introduction to Coding Theory

Course number: 6.897
Prereq: 6.046, 6.840 & Mathematical Maturity.
Time: MW 1:00-2:30pm
Location: 66-144
3-0-9 H-Level Grad Credit
Homepage: http://theory.lcs.mit.edu/~madhu/FT01/course.html

Course announcement

Topics covered:

Lecture 1 (9/5): Introduction. Shannon's theorem. Information, Entropy. References.
Lecture 2 (9/10): Converse of Shannon's noisy coding theorem. Discussion on Shannon capacity. Hamming's theory. Error-correcting codes. Linear codes.
Lecture 2.5: Notes on algebra.
Lecture 3 (9/12): Hamming Codes. Hamming bound. Perfect codes. Finite fields. Polynomials over finite fields.
Lecture 4 (9/19): Singleton bound. Reed Solomon codes, MDS codes. Reed Muller codes, Hadamard codes.
Lecture 4.5: BCH Codes (REVISED 1/8/2002.)
Lecture 5 (9/24): Asymptotically good codes over small alphabets. Random codes, Random linear codes, Wozencraft ensemble.
Lecture 6 (9/26): Wozencraft ensemble (contd.). Operations on codes. Concatenated codes. Forney codes. Justesen codes.
Lecture 7 (10/1): Algebraic geometry codes: Codes better than random codes.
Lecture 8 (10/3): Impossibility results for codes: Plotkin bound, Johnson bound, Elias-Bassalygo bound.
Lecture 9 (10/10): Bounds (contd.): MacWilliams Identities. Linear Programming bound. The asymptotic perspective.
Lecture 10 (10/22): Algorithmic questions: Encoding. Decoding. Decoding from erasures. Decoding RS codes. Some additional material:
1. My notes on rational function interpolation and
2. Michael Rosenblum's notes on rational approximation.
Lecture 11 (10/24): Abstract algorithm for decoding. Application: AG codes. Concatenated codes & GMD decoding.
Lecture 12 (10/29): List decoding: Recall combinatorics. List decoding of RS codes.
Lecture 13 (10/31): Improvements to list decoding.
Lecture 14 (11/5): Abstract decoding. Decoding CRT codes.
Lecture 15 (11/7): Implicit decoding. List decoding of Reed-Muller codes.
Lecture 16 (11/14): Linear time decoding: LDPC codes, Sipser-Spielman codes. Draft of Notes.
Lecture 17 (11/19): Linear time encoding and decoding: Spielman codes. Draft of Notes.
Lecture 18 (11/21): Linear time + near optimal error decoding! Draft of Notes.
Lecture 19 (11/28): Guest Lecturer: Piotr Indyk Expander based constructions of efficiently decodable codes. Draft of Notes.
Lecture 20 (12/3): Some NP-hard coding theoretic problems. Draft of Notes.
Lecture 21 (12/5): Applications in Complexity theory - 1 Draft of Notes.
Lecture 22 (12/10): Applications in Complexity theory - 2 Draft of Notes.
Lecture 23 (12/12): Applications in Complexity theory - 3. Draft of Notes.

Single file with notes of all finished lectures: (ps), (gzipped ps), (pdf).

References

Some standard references for coding theory are listed below. We won't follow any particular one of these. But the material covered can probably be found (in some disguise or other) in any of these.

Theory and Practice of Error-Control Codes. Richard E. Blahut. Addison-Wesley, Reading, Massachusetts, 1983.
The Theory of Error Correcting Codes. F.J. MacWilliams and N.J.A. Sloane. North-Holland, Amsterdam, 1981.
Introduction to Coding Theory. Jacobus H. van Lint. Springer-Verlag, Berlin, 1999.

Here is a pointer lecture notes from a previous (accelerated) version of this course.

A Crash Course on Coding Theory. Lecture notes from a course taught at the IBM Thomas J. Watson Research Center and the IBM Almaden Research Center.

Papers (to be added)
For scribes, here is a sample file and the preamble.tex file that it uses.