Accueil
Connexion
DENIF –
Documents d’Enseignement Numériques en Informatique Fondamentale
Thèmes
Cursus
Enseignants
Essential Coding Theory
Thème :
Cryptographie
–
Cursus :
MIT
2001 - Algorithmic Introduction to Coding Theory
Course Notes
From course 16, only draft on notes.
Madhu Sudan
Notes of all finished lectures (1 to 15)
1. Introduction. Shannon's theorem. Information, Entropy.
2. Converse of Shannon's noisy coding theorem. Discussion on Shannon capacity. Hamming's theory. Error-correcting codes. Linear codes.
3. Hamming Codes. Hamming bound. Perfect codes. Finite fields. Polynomials over finite fields.
4. Singleton bound. Reed Solomon codes, MDS codes. Reed Muller codes, Hadamard codes.
4,5. BCH Codes.
5. Asymptotically good codes over small alphabets. Random codes, Random linear codes, Wozencraft ensemble.
6. Wozencraft ensemble (contd.). Operations on codes. Concatenated codes. Forney codes. Justesen codes.
7. Algebraic geometry codes: Codes better than random codes.
8. Impossibility results for codes: Plotkin bound, Johnson bound, Elias-Bassalygo bound.
9. Bounds (contd.): MacWilliams Identities. Linear Programming bound. The asymptotic perspective.
10. Algorithmic questions: Encoding. Decoding. Decoding from erasures. Decoding RS codes.
11. Abstract algorithm for decoding. Application: AG codes. Concatenated codes & GMD decoding.
12. List decoding: Recall combinatorics. List decoding of RS codes.
13. Improvements to list decoding.
14. Abstract decoding. Decoding CRT codes.
15. Implicit decoding. List decoding of Reed-Muller codes.
16. Linear time decoding: LDPC codes, Sipser-Spielman codes.
17. Linear time encoding and decoding: Spielman codes.
18. Linear time + near optimal error decoding!
19. Guest Lecturer: Piotr Indyk Expander based constructions of efficiently decodable codes
20. Some NP-hard coding theoretic problems.
21. Applications in Complexity theory - 1.
22. Applications in Complexity theory - 2.
23. Applications in Complexity theory - 3.
References