Advanced Topics in Coding Theory (ENEE739C). Course Information

2003 Edition

Meeting times: Tuesday and Thursday 2:00 - 3:15 CHE 2136 (Chemical Engineering, Building 90)
Office hours: Wednesday 11:00-12:30 AVW 2361 (A.V. Williams, Building 115)

Announcements
· Course matters : No class on Thursday 12/4/2003.

· Items of general interest
Student seminar on Coding and Information Theory will be held every Wednesday in AVW 2224, 5:00 p.m. (first meeting 9/17). You are encouraged to participate.

Grading policy

Several homeworks (the number to be determined) (50%) and student presentations (50%).

Presentations.
You are encouraged to suggest a paper/subject you would like to present in class. A list of papers is found here. Your choice is not confined to this list: please feel free to suggest your own topic. However you must receive my approval of the subject. Please come during the office hours or schedule a discussion on your presentation topic. In the discussion I will likely suggest some new elements of the subject that you should address in your presentation.
The deadline for choosing a paper is Thursday 10/23. Please schedule a discussion with me before that date.
A new publishable result will automatically earn you an "A" grade.

Homework assignments. Papers are due at the beginning of the class on the due date. Papers turned in one week late will be given 50% credit, no credit after that.
Collaboration on homework problems is encouraged; however, proper credits should be stated on the papers (who did what).
Homework1 Solution1
Homework2 Solution2

Lecture notes
It is likely that the actual breakdown into lectures will be different from the breakdown of the notes. These notes change as errors are found (and hopefully removed), so check back often.

Lecture 1. Review: Notions of coding theory, asymptotic notation. Goals of coding theory. (Class of 9/2) ps pdf
Lecture 2. Average properties of codes. (Class of 9/4, 9/9) ps pdf
Lecture 3. Decoding of codes. (Class of 9/9, 9/11, 9/16) ps pdf
Lecture 4. Typical-sets decoding and the Shannon theorem. (Class of 9/23) ps pdf
Lecture 5. Max-likelihood decoding and error exponents: the Binary Symmetric Channel. (Class of 9/25) ps pdf
Lecture 6. Error exponents for Discrete Memoryless Channels. (Class of 9/30) ps pdf
Lecture 6a. Linear codes. Weights, ranks and all that. (Class of 10/7,10/9,10/14) ps pdf
Lecture 7. Random matrices over F_q. Erasure channel and its error exponent. Complexity issues in coding theory. (Class of 10/16, 10/21, 10/23) [corrected] ps pdf
Lecture 8. Asymptotically good families of codes. (Serially) concatenated codes and their decdoding. Generalized minimum distance decoding. (Class of 10/28, 10/30, 11/4) ps pdf
Lecture 9. Codes defined on graphs. The problem of attaining capacity. Iterative decoding. (Class of 11/11,11/13,11/18) ps pdf
Lecture 10. Attaining capacity with linear complexity: Expander codes. ps pdf (In addition to the notes we will use papers [5] and [2])
Lecture 11. Transmission of information over quantum channels. The nature of noise. Elements of quantum error correction. ps pdf
Fall 2003: We will stop here

Lecture 12. The problem of list decoding. Algebraic list decoding of Reed-Solomon codes. (d'après V. Guruswami and M. Sudan).
Lecture 13. Gaussian channel and spherical codes.
Lecture 14. The Johnson space and constant weight codes.
Lecture 15. Wire-tap channel and generalized Hamming weights.
Lecture 16. Impossibility results for codes. The Johnson and Bassalygo-Elias bounds. Linear programming (Delsarte) bound.