Courses:

Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses.

Prof. Madhu Sudan

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.

6.046J and mathematical maturity.

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

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.

Blahut, R. E. Theory and Practice of Error-Control Codes. Reading, MA: Addison-Wesley, 1983. ISBN: 0201101025.

MacWilliams, F. J., and N. J. A. Sloane. The Theory of Error Correcting Codes. Amsterdam, Netherlands: North-Holland, 1978. ISBN: 0444851933.

Van Lint, J. H. Introduction to Coding Theory. 3rd ed. Berlin, Germany: Springer-Verlag, 1999. ISBN: 3540641335.

A related course offered at MIT is 6.451: Principles of Digital Communication II, taught by Dave Forney. While 6.895 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.