Algorithmic Introduction to Coding Theory

Lecture Notes

• Lecture 1 (9/5): Introduction. Shannon's theorem. Information, Entropy. References.
• Lecture 2 (9/10): Converse of Shannon's noisy coding theorem. Discussion on Shannon capacity. Hamming's theory. Error-correcting codes. Linear codes.
• Lecture 2.5: Notes on algebra.
• Lecture 3 (9/12): Hamming Codes. Hamming bound. Perfect codes. Finite fields. Polynomials over finite fields.
• Lecture 4 (9/19): Singleton bound. Reed Solomon codes, MDS codes. Reed Muller codes, Hadamard codes.
• Lecture 4.5: BCH Codes (REVISED 1/8/2002.)
• Lecture 5 (9/24): Asymptotically good codes over small alphabets. Random codes, Random linear codes, Wozencraft ensemble.
• Lecture 6 (9/26): Wozencraft ensemble (contd.). Operations on codes. Concatenated codes. Forney codes. Justesen codes.
• Lecture 7 (10/1): Algebraic geometry codes: Codes better than random codes.
• Lecture 8 (10/3): Impossibility results for codes: Plotkin bound, Johnson bound, Elias-Bassalygo bound.
• Lecture 9 (10/10): Bounds (contd.): MacWilliams Identities. Linear Programming bound. The asymptotic perspective.
• Lecture 10 (10/22): Algorithmic questions: Encoding. Decoding. Decoding from erasures. Decoding RS codes. Some additional material:
  1. My notes on rational function interpolation and
  2. Michael Rosenblum's notes on rational approximation.
• Lecture 11 (10/24): Abstract algorithm for decoding. Application: AG codes. Concatenated codes & GMD decoding.
• Lecture 12 (10/29): List decoding: Recall combinatorics. List decoding of RS codes.
• Lecture 13 (10/31): Improvements to list decoding.
• Lecture 14 (11/5): Abstract decoding. Decoding CRT codes.
• Lecture 15 (11/7): Implicit decoding. List decoding of Reed-Muller codes.
• Lecture 16 (11/14): Linear time decoding: LDPC codes, Sipser-Spielman codes. Draft of Notes.
• Lecture 17 (11/19): Linear time encoding and decoding: Spielman codes. Draft of Notes.
• Lecture 18 (11/21): Linear time + near optimal error decoding! Draft of Notes.
• Lecture 19 (11/28): Guest Lecturer: Piotr Indyk Expander based constructions of efficiently decodable codes. Draft of Notes.
• Lecture 20 (12/3): Some NP-hard coding theoretic problems. Draft of Notes.
• Lecture 21 (12/5): Applications in Complexity theory - 1 Draft of Notes.
• Lecture 22 (12/10): Applications in Complexity theory - 2 Draft of Notes.
• Lecture 23 (12/12): Applications in Complexity theory - 3. Draft of Notes.

Single file with notes of all finished lectures: (ps), (gzipped ps), (pdf).