Coding Theory and Applications

Fall 2020

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

Class times:
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:

  1. Basic notions of linear codes, bounds on codes
  2. Algebraic codes, list decoding and its limits
  3. Asymptotically good codes: Random and efficiently constructible
  4. Codes on graphs and their decoding (expander and LDPC codes)
  5. Threshold phenomenon: Channel capacity, Polar codes, Reed-Muller codes
  6. Applications: Coding for storage (coding for the cloud), Index coding.

Home assignments: | HW1 Solutions | HW2 Solutions | HW3 Solutions |
Final exam: Problems  Solutions

Here is a List of Papers for the course project (the linked version is the most recent one).

Detailed contents of the course: (tentative outline)

   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
   My notes
    [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.

   Applications
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

References:
  • [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