Harvard University homepage
HARVARD.EDU

Madhu Sudan: Essential Coding Theory

Course number: 6.895
Prereq: 6.046 & Mathematical Maturity.
Time: MW 1:00-2:30pm
Location: 36-156
3-0-9 H-Level Grad Credit
Instructor: Madhu Sudan
Office Hours: Tuesday 2:30pm-4pm (tentative)
Homepage: http://theory.csail.mit.edu/~madhu/FT04/

Bulletin Board
1. Sign up for scribing. See scribes.txt for availability.
2. Get added to class mailing list. Send mail to me (firstname at mit dot edu).
3. PS 2 Out Now (, pdf). Due: Wednesday, October 13, 2004 by 1pm.

Old Problem Sets: PS1

And their solutions: Will appear here

Course announcement

Prereq: 6.046 & Mathematical Maturity.
Time: MW 1:00-2:30pm
Location: 36-156
3-0-9 H-Level Grad Credit
Homepage: http://theory.csail.mit.edu/~madhu/FT04/

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, and 6.896 in Fall 2002. See http://theory.lcs.mit.edu/~madhu/FT01 and http://theory.csail.mit.edu/~madhu/FT02 for notes from previous offerings. Other sources include:

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

Instructor: Madhu Sudan

Tentative schedule of topics

  • Lecture 01 (09/08): Introduction. Hamming space, distance, code. Applications. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 02 (09/13): Shannon’s theory of information. The coding theorem. Its converse. Slides (pdf). Draft of scribe notes (pdf).
  • Lecture 03 (09/15): Shannon theory vs. Hamming theory. Our goals. Tools. Linear codes. (Slides pdf). Draft of scribe notes (pdf).
  • Lecture 04 (09/20): Asymptotically good codes. Projection and Volume Bound. Random Codes. (Slides pdf). Draft of scribe notes (pdf).
  • Lecture 05 (09/22): Algebraic Codes: Reed-Solomon, Reed-Muller, Hadamard. Plotkin Bound. (Slides pdf). Draft of scribe notes (pdf). 
  • Lecture 06 (09/27):  Decoding Reed-Solomon codes – The Welch-Berlekamp algorithm. (Slides pdf). Draft of scribe notes (pdf)
  • Lecture 07 (09/29): Abstracting the RS decoding algorithm. Beyond unique decoding. Draft of scribe notes (pdf).
  • Lecture 08 (10/04):  List decoding of Reed-Solomon Codes. Draft of scribe notes (pdf).
  • Lecture 09 (10/06): CANCELLED.
  • Monday (10/11): Columbus Day Holiday.
  • Lecture 10 (10/13): Concatenated codes and decoding. Justesen codes. Draft of scribe notes (pdf).
  • Lecture 11 (10/18): Achieving Shannon capacity in polytime with concatenated codes. Draft of scribe notes ( pdf).
  • Lecture 12 (10/20): List decoding versus Rate versus Distance. Draft of scribe notes (pdf).
  • Lecture 13 (10/25): The gap between constructive and existential results in coding theory. Notes (pdf)..
  • Lecture 14 (10/27): Algebraic Geometry codes. Notes (pdf).
  • Lecture 15 (11/01): Linear-time decodable codes. Notes (pdf).
  • Lecture 16 (11/03): Linear-time encodable and decodable codes. Notes (not yet available). (pdf).
  • Lecture 17 (11/08): ?. Notes (not yet available). (pdf).
  • Lecture 18 (11/10): Expander Codes – the ABNNR construction. Notes ( pdf).
  • Lecture 19 (11/15): Computation and Randomness: Pseudo-randomness, limited independence, small-bias spaces. Notes (pdf).
  • Lecture 20 (11/17): Extraction of randomness, min-entropy, statistical difference, Extractors and codes. Notes (pdf).
  • Lecture 21 (11/22): Trevisan’s Extractor.
  • Lecture 22 (11/24): Ta-Shma-Zuckerman-Safra Extractor, Guruswami-codes. Notes (pdf).
  • Lecture 23 (11/29): Ta-Shma-Zuckerman-Safra Extractor (contd.). Notes (pdf).
  • Lecture 24 (12/01): Expanders, Eigenvalues and the Zig-Zag Product. Notes (pdf).
  • Lecture 25 (12/06): TBA.
  • Lecture 26 (12/08): TBA

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.