Coding Theory and Applications
Instructor : Alexander Barg
(*)Department of ECE, (*)Inst. for Systems Research, (*)Department of CS, (*)Department of Mathematics
Office: 2361 A.V. Williams Building. E-mail: abarg at umd dot edu
Lectures: Streaming online TuTh 2:00 - 3:15
Instructor availability outside class hours: Please send me an email, including an online meeting request
Course Homepage: http://www.ece.umd.edu/~abarg/ECC
Course description: This is a graduate-level introduction to Coding Theory with an emphasis on essential constructions and algorithms. We will cover several foundational methods that are widely used in modern research in coding theory and adjacent areas of CS and discrete mathematics. The first part covers basic concepts of coding theory including linear codes and bounds on codes. We continue with algebraic constructions such as Reed-Solomon codes and their extensions, and their list decoding algorithms. The second part is devoted to topics being developed in current research, including polar codes (as an explicit way to achieve the Shannon capacity), codes on graphs, codes for the cloud (locally recoverable codes, regenerating codes), codes for storage and index coding, other applications (inference and security). The course will take students to the forefront of research in some of the mentioned topics, enabling them to follow current research literature in coding theory and applications.
Prerequisites The course focuses on mathematical reasoning, so general mathematical maturity and previous experience of similar kind is essential. Most of the results are established from the first principles, so no specific background is required (except for good knowledge of basic linear algebra).
Textbook: No required textbook. The lectures draw on multiple sources, some of which are listed below.
Grading: Homeworks (1/3), Course project/End of course presentation (1/3), Take home final exam (1/3)
Project topics and materials will be distributed halfway into the course (please wait for the announcement). Please take a look at the 2019 class (on a different subject) to get an idea of the project style.
Course contents: We plan to cover the following topics:
- Basic notions of linear codes, bounds on codes
- Algebraic codes, list decoding and its limits
- Asymptotically good codes: Random and efficiently constructible
- Codes on graphs and their decoding (expander and LDPC codes)
- Threshold phenomenon: Channel capacity, Polar codes, Reed-Muller codes
- Applications: Coding for storage (coding for the cloud), Index coding.
Home assignments: | HW1 Solutions | HW2 Solutions | HW3 Solutions |
Detailed contents of the course: (tentative outline)
Final exam: Problems Solutions
Here is a List of Papers for the course project (the linked version is the most recent one).
Basic coding theory
Lecture 1. Introduction to Coding Theory, Linear codes and their duals.
Lecture 2. Generator and parity-check matrices, syndromes, decoding.
Lecture 3. Codes over general alphabets, Gilbert-Varshamov (GV) bound. [GRS], Sec. 4.1-4.4;
Lecture 4. Impossibility results: Plotkin and Hamming bounds. The MacWilliams theorem, a view through combinatorics and Fourier analysis.
[GRS], Sec. 4.1-4.4; [MS], Sec. 5.1; [R], Sec.4.4.
The 1963 paper by J. MacWilliams;
Delsarte, Goethals and Seidel's 1977 paper
Recent applications to
spherical codes and lattices.
Lecture 5. The asymptotic Plotkin bound. The Hamming code and its relatives. Random codes and the GV bound<.
[GRS], Sec.4.4, Sec. 4.2, and Ch.2. my
paper with G.D. Forney;
Lecture 6. Shannon's perspective of packing: Capacity of the BSC and BEC.
Madhu Sudan's Lectures 2,3; [GRS] Ch.6; my
paper with G.D. Forney; UMass Lect.7 by Arya Mazumdar.
RS Codes: constructions, extensions, and algorithms
Lecture 7 (9/22). Fundamentals of finite fields
[R], Ch.3; [MS], Sec.4.1-4.3; Old class notes (Lec.11,12,17)
Lecture 8 (9/24). RS codes as evaluation codes. MDS codes and the Singleton bound. Concatenated codes and the Zyablov bound.
[GRS], Ch.10, Sec.5.2-5.3; [MS], Sec.10.11; [R] Ch.12
Lecture 9. (9/29) Decoding algorithms of RS codes. The Peterson and Welch algorithms.
[GRS], Ch.15; Sudan's materials for Lec.9 (Harvard); my notes Pt.II, pp.34-35
Lecture 10. (10/1) List decoding of RS codes
[GRS], Ch.15; [R] Sec.9.3-9.5; [JH] Ch. 12
Lecture 11. (10/6) Improved list decoding of RS codes. Limits to list decoding.
[GRS], Ch.15; Ch.7
Lecture 12. (10/8) Distributed storage and RS codes with locality. Locality of random codes (a GV-type bound).
References: Talk at IT School, pp.12-30;
Paper with I. Tamo.
Lecture 13. (10/13) (1) A bound on the communication complexity of node repair. (2) From lines to curves: Hermitian codes
Reading for (2): [B] Ch.9 (first 4 sections); Sec. 10.3, 10.4
Combining codes; graphs and their eigenvalues; a path to capacity
Lecture 14. (10/15) Product codes and their decoding up to d/2 errors -- a segue to iterative decoding. Introduction to codes on graphs.
(not in textbooks); Tanner's paper
Lectures 15-16. (10/20, 10/22) Graphs and their eigenvalues. Expander codes. Linear-time decoding of a constant proportion of errors.
Sudan's lectures 13,14; Zemor's algorithm: wikipedia and paper
Lecture 17. (10/27) (1) Decoding of concatenated codes. (2) Concatenated (and expander) codes attain capacity in poly-time -- or do they?
Reading for (1) [GRS] Ch.12; my 2003 notes
Lecture 18. (10/29) Introduction to polar codes
Eren Sasoglu's thesis here or here
Arikan's 2009 paper
Youtube lectures of Telatar and Urbanke
[GRS] Ch.11 (more detailed than we did in class)
Lecture 19. (11/3) Convergence proofs of polarization
consult references for Lec.18
Lecture 20. (11/5) (1) Decoding of polar codes. Polarization and data compression. (2) Threshold phenomena in graphs and codes
Lecture 21. (11/10) Threshold probability of a code. Reed-Muller codes and polar codes
Threshold probability paper
RM codes: [MS] Ch.13, [GRS] Ch.9,14
Recent survey of RM codes (Abbe-Shpilka-Ye)
Links between polar codes and RM codes
Lecture 22. (11/12) (1) RM codes and polar codes. (2) Reed-Muller codes achieve BEC capacity
For (2) I will follow Abbe-Shpilka-Ye; here's the original paper by Kudekar e.a.
Lecture 23. (11/17) Reed-Muller codes achieve BEC capacity (finishing). (2) RM codes and local decoding.
For (2) see Yekhanin's survey below.
Lecture 24. (11/19) RM codes and locally correctable codes.
Lecture 25. (11/24) (1) More on LCCs. (2) Secret sharing, linear codes, and minimal vectors
For (2) see: McEliece-Sarwate | Massey |
Ashikhmin-Barg | Ding-Yuan |
Lecture 26. (12/1) Wiretap channel and higher weights
Ozarov-Weiner The wiretap channel | Wei's paper on GHWs |
Tsfasman-Vladuts: Geometric view of higher weights
Lecture 27. (12/3) Part I 2:00-3:15pm Digital fingerprinting and identifiable parents (IPP codes)
Part II 4:00 - 5:30pm You are invited to attend the talk by Mary Wootters (Stanford U.)
Sharp Thresholds for Random Subspaces, and Applications to LDPC Codes
(Details here; Link to the talk here )
References for IPP codes: Hollmann e.a. IPP codes for 2 parents | paper on the case of many parents
12/8, 12/10 End of course presentations
[GRS] V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory, book draft (2019)
[R] Ron M. Roth, Introduction to Coding Theory, Cambridge University Press, 2006, ISBN 978-0521845045
[MS] F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, North-Holland (many editions).
[JH] J. Justesen and T Hoeholdt, A Course in Error Correcting Codes, EMS Textbooks in Mathematics, 2017, ISBN 978-3037191798
J.I. Hall, Notes on Coding Theory, web draft
S. Yekhanin, Locally Decodable Codes, Foundations and Trends in Theoretical Computer Science, NOW publishers, 2010.
[B] R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves, Cambridge University Press, 2008, ISBN 978-0521771948.
Similar courses in other universities: (with course materials)
Harvard (Madhu Sudan)
SUNY Buffalo (Atri Rudra)
CMU (Venkat Guruswami)
U Mass (Arya Mazumdar)
old nodes for my UMD ECE course
Topics for student projects (in progress)
Decoding of Reed-Muller codes
Quantum (CSS) codes; hypergraph product codes
Scaling behavior of polar codes
Discrete energy of codes; quadratic discrepancy
Codes in Complexity: Hardness amplification, extractors
Locally decodable codes