15-859V: Introduction to Coding Theory, Spring 2010
- Instructor: Venkatesan Guruswami.
- Time: Wednesdays & Fridays, 1:30-2:50 PM, GHC
- 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.
The notes (up to Notes 6) are also posted on the course blog. PDF versions are linked below:
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
- 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:
The basic material on codes we discuss in initial lectures can be found in many books, including
Here are some surveys that have a more computer science slant and
could be useful for the course:
- M. Sudan, Coding
theory: Tutorial & Survey, Proc. of 42nd FOCS, pages 36-53,
- 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),
- L. Trevisan, Some
Applications of Coding Theory in Computational Complexity,
Quaderni di Matematica 13:347-424, 2004.
Last modified: Fri Apr 30 17:39:44 EDT 2010
Maintained by Venkatesan Guruswami