CSE 533: Error-Correcting Codes: Constructions and Algorithms, Autumn 2006
Meeting times: Wednesday 3:00-4:20pm and Fridays 10:30-11:50am at CSE 403
Office hours: After class or by appointment.
- 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
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
- Lecture 13 - Expander based asymptotically good codes and linear time
- 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.
coding, a paper by Peter Elias that achieves positive rate for BSC
with small but positive crossover probability.
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:
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
- 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.
- Elements of Information Theory, Thomas M. Cover and Joy A. Thomas,
Wiley Series in Telecommunications, 1991.
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
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX