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
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. Reed-Muller 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): Elias-Bassalygo-Johnson 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 Reed-Solomon Codes.
Draft of scribe notes
(tex,
ps,
pdf).
-
Lecture 14 (10/28):
Locally decodable codes. Local unambiguous decoding
of some Hadamard codes and Reed-Muller codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).
-
Lecture 15 (10/30):
Local (list) decoding of Reed-Muller codes.
Slides
(ps,
pdf).
Draft of scribe notes
(tex,
ps,
pdf).
-
Lecture 16 (11/04):
Linear time decoding: LDPC codes, Sipser-Spielman 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 NP-hard 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 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.