Coding Theory

Currently, this course is taught in the Master’s program at the Department of Discrete Mathematics, School of Applied Mathematics and Computer Science, MIPT. Different versions of the course have been taught at MIPT since 2012 as both a special course and a core course.

Assignments

• PDF file with problems

Lectures

Slides from some of last year’s lectures can be found at this link.

Lecture Plan

• Alphabetic coding. Sufficient conditions for unique decoding: uniformity, prefix property, suffix property. Recognizing uniqueness: Markov’s criterion. Bound on length of ambiguously decodable word.
• Kraft-McMillan inequality; existence of prefix code with given word lengths; corollary about universality of prefix codes.
• Minimum redundancy codes: problem statement, Huffman’s reduction theorem.
• Error correction and detection problem. Geometric interpretation. Error types. Hamming and Levenshtein metrics. Code distance. Basic problems in error-correcting codes theory.
• Varshamov-Tenengolts codes, algorithms for correcting single deletion and insertion errors.
• Basic bounds for parameters of substitution error-correcting codes: sphere packing bound, Singleton bound, Plotkin bound.
• Embedding of metric spaces. Lemma on number of vectors in Euclidean space. Elias-Bassalygo bound.
• Linear codes. Definitions. Generator and parity-check matrices. Relationship between code distance and parity-check matrix. Varshamov-Gilbert bound. Systematic encoding. Syndrome decoding. Hamming codes.
• Residual code. Griesmer-Solomon-Stiffler bound.
• Complexity of linear code decoding: NCP (Nearest Codeword Problem).
• Expander graphs. Probabilistic proof of expander existence. Codes based on bipartite graphs. Code distance of expander-based codes. Sipser-Spielman decoding algorithm.
• Hadamard matrices. Sylvester and Paley constructions. Codes based on Hadamard matrices.
• Reed-Solomon codes. Berlekamp-Welch decoding algorithm.
• Reed-Muller codes: code distance, majority decoding algorithm.
• Variants of Reed-Muller construction generalizations. Lipton-DeMillo-Schwartz-Zippel lemma. Introduction to algebraic-geometric codes.
• Concatenated codes. Forney codes: construction and simple decoding algorithm.
• Cyclic codes. Check and generator polynomials, existence criterion for code with given generator polynomial. Form of generator and check matrices. Systematic encoding.
• Bose-Chaudhuri-Hocquenghem bound. BCH codes.
• Synchronization recovery problem. Synchronization recovery for cosets of cyclic codes.
• Perfect codes. Golay codes. Vasilev’s theorem.
• Graph model of channel. Shannon product of graphs, Shannon capacity. Theorem on upper bound of Shannon capacity.
• Shannon’s theorems on rate limit in probabilistic channel model.
• Applications of error-correcting codes. Randomized protocol in communication complexity. McEliece cryptosystem. Homogeneous (pseudorandom) sets based on codes, their applications to derandomization in MAX-SAT problem and secret sharing problem.

Course Materials

• Lecture notes for the course.
• Map of key concepts and theorems covered in the course. It will help connect these concepts and make them easier to remember. A video commentary on a similar map can be viewed on YouTube.
• Lecture slides.

References

For a deeper understanding of the material, please refer to the literature list below. Pay special attention to book [5].

1. M. N. Arshinov, L. E. Sadovsky. Codes and Mathematics. Moscow: Nauka, 1983.
2. S. B. Gashkov. Expander Graphs and Their Applications in Coding Theory // Mathematical Enlightenment, ser. 3, issue 13, 2009. pp. 104-126.
3. F. J. MacWilliams, N. J. A. Sloane. The Theory of Error-Correcting Codes. Moscow: Svyaz, 1979.
4. W. W. Peterson, E. J. Weldon. Error-Correcting Codes. Moscow: Mir, 1976.
5. A. Romashchenko, A. Rumyantsev, A. Shen. Notes on Coding Theory. Moscow: MCCME, 2011.
6. Yu. L. Sagalovich. Introduction to Algebraic Codes. Moscow: MIPT Publishing House, 2007.
7. F. I. Solovyeva. Introduction to Coding Theory. Novosibirsk: NSU Publishing House, 2006.
8. Ye. Lindell. Introduction to Coding Theory. Lecture notes. Bar-Ilan University.
9. J. H. van Lint. Introduction to Coding Theory. Third edition. Springer-Verlag, 1999.
10. M. Sudan. Algorithmic Introduction to Coding Theory. Lecture notes. MIT, 2001.