DSC 291: Coding Theory

Coding Theory has been playing an important role in many areas of Engineering, Applied Math and Computer Science in topics such as communications, CS theory, networking, and security. This course will be a modern take on coding theory emphasizing probabilistic methods, power of randomization, and open research questions in discrete probability and extremal combinatorics. The topics covered will include (but will not be limited to) basic coding and information theory, soft-packing and Shannon capacity, threshold phenomenon in random graphs, polarization, algebraic codes, Reed-Solomon and Reed-Muller codes, list decoding, sparse-graphs and expander codes, algebraic combinatorics and codes, applications of codes.

This course is for graduate students and advanced undergraduate students (with permissions).

No Textbooks

Prerequisite: Linear algebra, probability

Lectures:

Lecture 1: Shannon and Hamming

Lecture 2: Hamming code and Sphere Packing

Lecture 3: Bounds on Codes

Lecture 4: Bounds on Codes - Random Channel

Lecture 5: Random Codes

Lecture 6: Codes on Graphs

Lecture 7: Expander Codes

Lecture 8: Spectral Expanders

Lecture 9: Belief Propagation

Lectures 10-11: Polar Codes

Lecture 12: Polar Codes (Cont'd)

Lecture 13: Reed-Muller Codes

Lecture 14: First-order Reed-Muller Codes and Covering Codes

Lecture 15: List Decoding

Lecture 16: Reed-Solomon Codes

Lecture 17: Decoding of Reed-Solomon Codes

Lecture 18: Concatenated Codes