Harvard University homepage
HARVARD.EDU

Madhu Sudan: 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

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

Algorithmic Introduction to Coding Theory

This course introduces the theory of error-correcting codes to computer scientists. This theory, dating back to the works of Shannon and Hamming from the late 40’s, overflows with theorems, techniques, and notions of interest to theoretical computer scientists. The course will focus on results of asymptotic or algorithmic significance. Principal topics include:

  1. Construction and existence results for error-correcting codes.
  2. Limitations on the combinatorial performance of error-correcting codes.
  3. Decoding algorithms.
  4. Applications in computer science.

For some preliminary material on the course, see

Instructor: Madhu Sudan

Topics covered

References
  • Lecture 1: Shannon’s original paper is available from the Bell Labs website. A good source on information theory is the text by Cover and Thomas. In particular, this lecture refers to material from Chapters 2 and 8 of this book. See also pages 1 to 12 from Lecture 1 of my crash course.
    • Claude E. Shannon. A Mathematical Theory of Communication. Bell Systems Technical Journal, Vol 27, pp. 379-423, 623-656, July, October, 1948.
    • Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley Publishing, New York, 1991.
  • 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

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.

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