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.
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
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:
