Course Credits: 3-0-0-0 (9)
Prerequisites: CS201 or equivalent
Intended Audience: UG 3rd year onwards, all PG students
Error-correcting codes play a crucial role across various fields of science and engineering, serving as protective measures to maintain data integrity when faced with the disruptive influences of noise in both communication and storage systems. This course primarily adopts a theoretical perspective. It is designed to engage mathematically adept undergraduate and postgraduate students. In this course we discuss the fundamentals of coding theory and the exploration of some foundational theorems in this domain. We look at constructions of some basic codes, followed by codes based on polynomials and expander graphs. Thereafter we move to the topic of decoding, and learn about the various decoding algorithms for the codes that we constructed. We also study the connection between coding theory and areas like pseudorandomness and derandomization in this course.
Through these topics, students will gain a comprehensive understanding of error-correcting codes and their significance in contemporary scientific and engineering contexts.
| Module | List of Topics | No. of hrs |
|---|---|---|
| Linear codes | Linear codes, generator and parity check matrices, constructing new codes from old ones, Hamming codes, Reed-Muller codes, Shannon's Theorem | 6 |
| Bounds on code cizes | Plotkin Bound, Johnson Bounds, Gilbert Lower Bound, Varshamov Lower Bound | 6 |
| Cyclic codes | Finite fields, cyclic codes and their minimum distance | 5 |
| BCH and Reed Solomon codes | BCH codes, Reed Solomon codes, Generalized Reed Solomon codes | 3 |
| Concatenated codes | Code concatenation, Zyablov Bound, Advanced Concatena- tion and Strongly Explicit Constructions | 3 |
| Efficient Decoding of codes | Unique Decoding Reed Solomon codes, List Decoding of Reed Solomon codes, Decoding Reed-Muller codes, Decoding of concatenated codes (optional) | 8 |
| Graph based codes | Expander graphs, basic expander codes, distance amplification | 5 |
| Application to Computational Complexity | Derandomization and pseudorandomness, applications in communication complexity | 4 |