Essential Coding Theory
Course number: 6.896
Prereq: 6.046, 6.840 & Mathematical Maturity.
Time: MW 1:002:30pm
Location:
24307
309 HLevel Grad Credit
Homepage:
http://theory.lcs.mit.edu/~madhu/FT02/
Course announcement
Problem Sets
 Problem Set 1
(tex,
ps,
pdf).
Solutions
(tex,
ps,
pdf).
 Problem Set 2
(tex,
ps,
pdf).
Solutions
(tex,
ps,
pdf).
 Problem Set 3
(tex,
ps,
pdf).
Solutions
(tex,
ps,
pdf).
 Problem Set 4
(tex,
ps,
pdf).
Topics covered:

Lecture 01 (09/04):
Introduction. Hamming space, distance, code. Applications.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 02 (09/09):
Shannon's theory of information. The coding theorem.
Its converse.
Slides
(ps,
pdf).
Draft of scribe notes (REVISED 9/18/2002)
(tex,
ps,
pdf).

Lecture 03 (09/11):
Shannon theory vs. Hamming theory. Our goals. Linear codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 04 (09/16):
Singleton bound.
Polynomials over finite fields. Reed Solomon
codes. ReedMuller codes. Hadamard codes (again!).
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 05 (09/18):
Asymptotically good codes. Random codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 06 (09/25):
Concatenated codes. Forney codes. Justesen codes.
Slides
(ps,
pdf).
Draft of scribe notes (REVISED 10/23/2002)
(tex,
ps,
pdf).

Lecture 07 (09/30): Algebraic geometry codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 08 (10/02):
Impossibility results for codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 09 (10/07): EliasBassalygoJohnson bounds.
MacWilliams Identities.
Linear Programming bound.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 10 (10/09):
Algorithmic questions: Encoding. Decoding.
Decoding RS codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 11 (10/16):
Decoding RS codes, AG codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 12 (10/21):
Decoding AG codes (contd.), Decoding concatenated codes.
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 13 (10/23):
List decoding of ReedSolomon Codes.
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 14 (10/28):
Locally decodable codes. Local unambiguous decoding
of some Hadamard codes and ReedMuller codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 15 (10/30):
Local (list) decoding of ReedMuller codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 16 (11/04):
Linear time decoding: LDPC codes, SipserSpielman codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 17 (11/06):
Linear time encoding and decoding: Spielman codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 18 (11/13):
Linear time + near optimal error decoding!
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 19 (11/20):
Expander based constructions of efficiently decodable
codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 20 (11/25):
Some NPhard coding theoretic problems.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 21 (11/27):
Applications in Complexity theory  1
Draft of scribe notes
(tex,
ps,
pdf).

Lecture 22 (12/02):
Applications in Complexity theory  Randomness and
derandomization; Randomness extractors; Trevisan's extractors.
Slides
(ps,
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 ErrorControl Codes.
Richard E. Blahut.
AddisonWesley, Reading, Massachusetts, 1983.

The Theory of Error Correcting Codes.
F.J. MacWilliams and N.J.A. Sloane.
NorthHolland, Amsterdam, 1981.

Introduction to Coding Theory.
Jacobus H. van Lint.
SpringerVerlag, 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 nonstandard 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 fastpaced
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.