Harvard University homepage
HARVARD.EDU

Madhu Sudan: Essential Coding Theory

Course number: 6.896
Prereq: 6.046, 6.840 & Mathematical Maturity.
Time: MW 1:00-2:30pm
Location: 24-307
3-0-9 H-Level Grad Credit
Homepage: http://theory.lcs.mit.edu/~madhu/FT02/

Course announcement

Prereq: 6.046, 6.045, & Mathematical Maturity.
Time: MW 1:00-2:30pm
Location: 24-307
3-0-9 H-Level Grad Credit
Homepage: http://theory.lcs.mit.edu/~madhu/FT02/

Essential 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 and 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.

This course was offered as 6.897 in Fall 2001. See http://theory.lcs.mit.edu/~madhu/FT01 for notes from that offering. Other sources include:

Grading in this course will be based on four problem sets, scribe work, and possibly one term paper.

Instructor: Madhu Sudan

Problem Sets

  • Problem Set 1 (pdf). Solutions (pdf).
  • Problem Set 2 (pdf). Solutions (pdf).
  • Problem Set 3 (pdf). Solutions (pdf).
  • Problem Set 4 (pdf).

Topics covered:

  • Lecture 01 (09/04): Introduction. Hamming space, distance, code. Applications. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 02 (09/09): Shannon’s theory of information. The coding theorem. Its converse. Slides (pdf). Draft of scribe notes (REVISED 9/18/2002) (pdf).
  • Lecture 03 (09/11): Shannon theory vs. Hamming theory. Our goals. Linear codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 04 (09/16): Singleton bound. Polynomials over finite fields. Reed Solomon codes. Reed-Muller codes. Hadamard codes (again!). Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 05 (09/18): Asymptotically good codes. Random codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 06 (09/25): Concatenated codes. Forney codes. Justesen codes. Slides (pdf). Draft of scribe notes (REVISED 10/23/2002) (pdf).
  • Lecture 07 (09/30): Algebraic geometry codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 08 (10/02): Impossibility results for codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 09 (10/07): Elias-Bassalygo-Johnson bounds. MacWilliams Identities. Linear Programming bound. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 10 (10/09): Algorithmic questions: Encoding. Decoding. Decoding RS codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 11 (10/16): Decoding RS codes, AG codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 12 (10/21): Decoding AG codes (contd.), Decoding concatenated codes. Draft of scribe notes (pdf).
  • Lecture 13 (10/23): List decoding of Reed-Solomon Codes. Draft of scribe notes (pdf).
  • Lecture 14 (10/28): Locally decodable codes. Local unambiguous decoding of some Hadamard codes and Reed-Muller codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 15 (10/30): Local (list) decoding of Reed-Muller codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 16 (11/04): Linear time decoding: LDPC codes, Sipser-Spielman codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 17 (11/06): Linear time encoding and decoding: Spielman codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 18 (11/13): Linear time + near optimal error decoding! Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 19 (11/20): Expander based constructions of efficiently decodable codes. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 20 (11/25): Some NP-hard coding theoretic problems. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 21 (11/27): Applications in Complexity theory – 1 Draft of scribe notes (pdf).
  • Lecture 22 (12/02): Applications in Complexity theory – Randomness and derandomization; Randomness extractors; Trevisan’s extractors. Slides (pdf).
  • Lecture 23 (12/04): Applications in Complexity theory – 3.

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.

A related course offered at MIT is Principles of Digital Communication II (MIT 6.451) taught by Dave Forney. While 6.896 and 6.451 have a fair amount of overlap the courses do have significantly different emphasis to allow for students to benefit by taking both courses.Some non-standard references for coding theory include:

  • 6.897 Fall 2001 : Pointer to course notes from last time the course was taught.
  • A Crash Course on Coding Theory: Course notes of a fast-paced version of this course as taught at the IBM Thomas J. Watson Research Center and the IBM Almaden Research Center.

For scribes, here is a sample file and the preamble.tex file that it uses.