CSE 533: Error-Correcting Codes: Constructions and Algorithms, Autumn 2006

University of Washington Computer Science & Engineering

CSE Home

About Us

Contact Info

Instructor:

Venkatesan Guruswami
Meeting times: Wednesday 3:00-4:20pm and Fridays 10:30-11:50am at CSE 403
Office hours: After class or by appointment.

Mailing List

It is important to subscribe to the class mailing list immediately. Everyone is expected to be reading cse533 e-mail to keep up-to-date on the course.
To subscribe to the CSE 533 mailing list, click here

Course announcement

Problem Sets

Problem Set 1, due October 30. Latex source.
Problem Set 2, due Friday, December 1st. Latex source.

Lecture notes

Here is the style file scribe.sty for preparing lecture notes.

Lecture 1 - A Hat puzzle; Basic definitions about codes; Rate and Distance; Linear codes; [7,4,3] Hamming code
Lecture 2 - Parity check matrix, Hamming code family, Volume bound, Dual codes, Hadamard code.
Lecture 3 - Introduction to Shannon theory; stochastic channels and examples; entropy function; Capacity theorem for BSC.
Lecture 4 - Proof of Shannon's theorem for BSC, Elias' constructive method using product of Hamming codes
Lecture 5 - Bounds on codes: Hamming upper bound, Singleton bound, Gilbert-Varshamov bound, Plotkin bound.
Lecture 6 - Johnson bound, Elias-Bassalygo bound.
Lecture 7 - Reed-Solomon (RS) codes, Bounds on number of roots of polynomials, Multivariate polynomial and Reed-Muller codes.
Lecture 8 - Majority logic decoding of Reed-Muller codes, Basics of extension fields, Binary codes from RS codes.
Lecture 9 - Concatenated codes, Explicit asymptotically good codes meeting Zyablov bound, GV, Zyablov & MRRW bounds, Justesen codes.
Lecture 10 - Justesen codes proof, Reed-Solomon decoding -- History and Welch-Berlekamp decoder (Gemmell-Sudan description).
Lecture 11 - Decoding concatenated codes: A naive decoder, and Forney's GMD decoding.
Lecture 12 - Achieving capacity of BSC with polytime encoding and decoding.
Lecture 13 - Expander based asymptotically good codes and linear time decoding.
Lecture 14 - Tanner codes; Linear time decodable codes using spectral expanders; Boosting error-correction using expander based symbol redistribution.

Related material appears in these notes from the Winter 2003 course at UW.

Lectures 15 and 16 - Wrap-up of linear time codes with optimal rate; Introduction to list decoding, List decoding capacity, Connection to Johnson bounds, Toy Reed-Solomon decoding problem
Lecture 17 - Interpolation based list decoding of RS codes, Soft decoding, Using multiplicities in decoding.
Lecture 18 - Decoding RS codes up to Johnson bound (wrap-up), Beyond RS codes: Folded RS codes, Multivariate interpolation based decoding.
Lecture 19 - Achieving list decoding capacity using folded RS codes. Topics we didn't cover: AG codes, LDPC decoding, Convolutional/turbo coding.

Reading links

Error-free coding, a paper by Peter Elias that achieves positive rate for BSC with small but positive crossover probability.

Reference material

We will not follow any one particular textbook. The closest resource is the excellent set of lecture notes for Madhu Sudan's coding theory course at MIT: Notes from 2001 and 2004.

The basic material on codes we discuss in initial lectures can be found in one of many textbooks (some of which are listed below), but the recent algorithmic developments are probably not adequately covered in any of these:

Introduction to Coding Theory, by J. H. van Lint, GTM 86. One of my favorites due to its compactness, and of course GTM yellow cover.
Introduction to Coding Theory, by Ron M. Roth, 2006 (very recent book!). Includes discussion of some recent algorithmic progress (such as list decoding, decoding expander codes).
Algebraic codes for data transmission. by Richard E. Blahut.

Though we won't cover much information theory in this course, if your curiosity is aroused on aspects such as entropy, mutual information, capacity theorems, source coding, etc., there is the classic information theory text

Elements of Information Theory, Thomas M. Cover and Joy A. Thomas, Wiley Series in Telecommunications, 1991.

Recommended preparation

The principal prerequisite for this class is some "mathematical maturity", or more specifically comfort with basics of linear algebra (vector spaces, basis, dual spaces); finite fields, field extensions and polynomials over finite fields; elementary probability; and analysis of algorithms.

If you are not comfortable with your algebra background, you can read the algebra material in any of the above 3 coding texts, your favorite algebra text, or these notes due to Madhu Sudan. You can also do this "as the need arises" in the lectures since we won't get to much algebraic stuff until a few lectures into the class.

Class Assignments and Grading

Coursework will include preparing Latex scribe notes for one or two lectures and doing a couple of problem sets. Posting scribe notes promptly is important to complement the lectures, and so students are urged to cooperate in this regard. The "grade" on scribe notes will be a function of both the quality of the notes and the timeliness with which it is handed in.

Final grades will be based on the scribe notes, class participation, and performance on the problem sets. There will be no exams.


	Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX