University of Toronto
Department of Computer Science

CSC 2414H
Introduction to Coding Theory

Spring 2008


Lecture: Tuesday 13-15, AP120

Instructor: Avner Magen

Office hours: by appointment (SF 2301B, 946-8672).

Tutor: Ilya Sutskever

Approximated Syllabus

* Shannon coding theorem
* Noise models (worst-case or probabilisitic)
* Combinatorial bounds, Gilbert-Varshamov, Delsartte and MRRW bounds
* Classical code constructions (algebraic, LDPC, concatenated)
* Reed-Solomon decoding and applications
* Expander codes
* List decoding
* Turbo codes

  • Reading

    * Theory and Practice of Error-Control Codes. Richard E. Blahut. Addison-Wesley, Reading, Massachusetts, 1983.
    * The Theory of Error Correcting Codes. F.J. MacWilliams and N.J.A. Sloane. North-Holland, Amsterdam, 1981.
    * Introduction to Coding Theory. Jacobus H. van Lint. Springer-Verlag, Berlin, 1999.

    Other courses on the subject have useful websites, such as Sudan's course at MIT (2004) and Guruswami's course at the University of Washington.


    There will be a total of four assignments, each worth 25% of your mark.

  • assignment 1. Updated Wednesday 23/1 in the afternoon. Due 5/2.
  • assignment 2. Due 4/3.
  • assignment 3. Due 1/4. Updated 26/3 @11:00AM. Check also clarifications in response to FAQ.
  • assignment 4. (question 1,2a,3b updated. check the boldfaced parts of the assignment). Due 24/4.
  • Announcements

    Date Announcement(s)
    Here is a link to Navon and Samoridnitsky's paper that bounds the rate of a code using harmonic analysis (and that is related to Delsarte's metod)
    There will be a tutorial on Thursday 20/3, 11:00-12:00 in BA 2195. It will be dedicated to selected solutions from the assignments. Please prepare questions.
    There will be a tutorial on Thursday 14/2, 11:00-12:00 in BA 2195.
    There will be theory seminar on topics related to coding theory this Friday by Valentine Kabanets from SFU. Check here for more details.
    Deadline for A1 will change to next Tuesday's class, 5/2
    We will change the time of the lecture: Tuesday 13-15. Location: AP120. This will go into effect Jan 29 (next week!)
    I made some small modification to the assignment (15:48). Please take this version.
    Assignment 1 is uploaded.
    Tutorial on Tue 22/1, 12:00-13:00 in BA 2130.
    I am expecting to have assignment 1 ready by Monday or Tuesday. It will be due 31/1.
    There will be a tutoial, Tue 22/1 12:00-13:00. Location TBA. Ilya will cover necessary background material, mainly about finite fields.