15-859V: Introduction to Coding Theory, Spring 2010

Instructor: Venkatesan Guruswami.

Time: Wednesdays & Fridays, 1:30-2:50 PM, GHC 4102

Course Blog: http://errorcorrectingcodes.wordpress.com/

This webpage will be mostly static, except for postings of the problem sets and course notes. Please read the course blog regularly, or subscribe to it via email, or add it to your favorite feed reader (using links available on the blog). We will use the blog to post course related announcements; lecture summaries; problem set hints or corrections, etc.

Office hours: By appointment.

Problem sets

• Problem set 1 (due Feb 19)
• Problem set 2 (due Mar 19)
• Problem set 3 (due Apr 23)

Course notes

• Introduction, Linear codes
• Gilbert-Varshamov bound
• Stochastic channels and noisy coding theorem
• Elementary bounds on codes
• Fourier Transform, MacWillams identities, and LP bound
• Proof of the first MRRW bound
• Basics of finite fields
• Code constructions: Reed-Solomon, BCH, Reed-Muller, and concatenated
• Justesen codes, Reed-Solomon decoding, GMD decoding
• Expander codes and their decoding
• Notes on expander codes from a previous offering.
• Linear-time decodable codes of optimal rate; beginning of List Decoding (Draft version)
• List decoding Reed-Solomon codes and concatenated codes (Draft version)
• List decoding with optimal rate: Folded Reed-Solomon codes

Course Description: Error-correcting codes play an important role in many areas of science and engineering. This course is a graduate level introduction to error-correcting codes, with a focus on the theoretical and algorithmic aspects arising in the context of the "channel coding" problem: We want to transmit data over a noisy communication channel so that the receiver can recover the correct data despite the adverse effects of the channel.

Starting from the basics of coding theory and some of the classic theorems of the subject, the course will discuss more recent progress on code constructions and error-correction algorithms. List of potential topics include:

• Shannon coding theorem and noise models (worst-case, stochastic)
• Basics notions and combinatorial bounds of coding theory
• Classical code constructions (algebraic, LDPC, concatenated, etc.)
• Reed-Solomon decoding and applications
• Expander codes and linear time error-correction
• List decoding; error-correction with optimal redundancy.
• Iterative decoding methods and belief propagation
• Rateless codes; convolutional codes.
• Codes in computational complexity

Grading:

• Problem sets (about 3 of them, roughly 60% of the grade). Solutions must be typeset; LaTeX is strongly preferred. Collaboration encouraged (in two person groups); precise instructions are given on each problem set.
• Scribe notes (one week/two lectures per student, about 30%). The notes must be clear, detailed, and well synthesized, and typeset in LaTeX (preferably in a form convertable to wordpress for easy readability via course blog).
• Attendance and class participation (about 10%).

Reference materials: We won't follow any particular text for the course. There are many good introductory books on coding theory (see partial list below), but none of them have the same focus and goals as the course. The following lecture notes provide a good coverage of the topics covered in the course:

• Notes from a Fall 2006 course taught at U. Washington.
• The excellent notes from Madhu Sudan's Fall 2001 course at MIT.
• Notes from Atri Rudra's course at Univ. at Buffalo.
• Notes from Luca Trevisan's course on Coding theory and complexity

• Introduction to Coding Theory by J. H. van Lint. Springer-Verlag, Berlin, 1999.
• Introduction to Coding Theory by Ron M. Roth, Cambridge University Press, 2006.
• Algebraic codes for data transmission by Richard E. Blahut, Cambridge University Press, 2003.

• M. Sudan, Coding theory: Tutorial & Survey, Proc. of 42nd FOCS, pages 36-53, 2001.
• A. Rudra, Algorithmic Coding theory, Book Chapter, CRC Handbook on Algorithms and Theory of Computation.
• V. Guruswami and A. Rudra, Error Correction up to the Information-Theoretic Limit Communications of the ACM, 2009.
• V. Guruswami, Algorithmic results for list decoding, Foundations and Trends in Theoretical Computer Science, Volume 2, Issue 2, 2007.
• V. Guruswami, Iterative Decoding of Low-Density Parity Check Codes, Issue 90 of Bulletin of the EATCS.
• V. Guruswami, Error-correcting codes and Expander graphs, SIGACT News, 35(3), 2004.
• L. Trevisan, Some Applications of Coding Theory in Computational Complexity, Quaderni di Matematica 13:347-424, 2004.