Home > Teaching > CS 698Z: Fundamentals of Error Correcting Codes

#### CS 698Z: Fundamentals of Error Correcting Codes

Course Credits: 3-0-0-0 (9)

Prerequisites: CS201 or equivalent

Intended Audience: UG 3rd year onwards, all PG students

###### Course Objective

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.

###### Course Contents

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

###### Books and References
1. Fundamentals of Error Correcting Codes by Cary Huffman and Vera Pless.
2. Lecture notes by Madhu Sudan
3. Lecture notes by Venkatesan Guruswami
4. Other sources as and when required.