Bookmark and Share


  • 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).
 

Our Followers

Speak to us !

Creative Commons License [Valid RSS] [Valid Atom 1.0] DMCA.com ScanVerify.com Trust Seal