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.


    Assignments

    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)
    20/3
    		 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)
    17/3
    		 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.
    12/2
    		 There will be a tutorial on Thursday 14/2, 11:00-12:00 in BA 2195.
    28/1
    		 There will be theory seminar on topics related to coding theory this Friday by Valentine Kabanets from SFU. Check here for more details.
    28/1
    		 Deadline for A1 will change to next Tuesday's class, 5/2
    24/1
    		 We will change the time of the lecture: Tuesday 13-15. Location: AP120. This will go into effect Jan 29 (next week!)
    23/1
    		 I made some small modification to the assignment (15:48). Please take this version.
    23/1
    		 Assignment 1 is uploaded.
    21/1
    		 Tutorial on Tue 22/1, 12:00-13:00 in BA 2130.
    19/1
    		 I am expecting to have assignment 1 ready by Monday or Tuesday. It will be due 31/1.
    18/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.