CSC 310 - Information Theory (Jan-Apr 2002)

Here are the term and final exam marks. You can collect assignments and tests from my office. Phone ahead to see if I'm in before coming by.

Information theory arises from two important problems: How to represent information compactly, and how to transmit information reliably in the presence of noise. The concept of `entropy' as a measure of information content is central to both of these problems, and is the basis for an elegant theory centred on two famous theorems proved by Claude Shannon over 50 years ago. Only in recent years has the promise of these theorems been fully realized, however. In this course, the elements of information theory will be presented, along with some of the practical techniques needed to construct the data compression and error-correction methods that play a large role in modern communications and storage systems.

Instructor: Radford Neal, Phone: (416) 978-4970, Email: radford@cs.utoronto.ca
Office Hours: Mondays 1:10-2:00 and Thursdays 2:30-3:30, in SS 6016A

Lectures:

Mondays and Wednesdays, from 3:10pm to 4:00pm, in SS 1073
From January 7 to April 10, except for Reading Week (February 18-22)

Tutorials:

Fridays, from 3:10pm to 4:00pm, in SS 1073
From January 18 to April 12, except for Reading Week and Good Friday (March 29)

A webpage with supplementary information on tutorials is maintained by the TA, Cosmin Truta.

Course Texts:

G. A. Jones and J. M. Jones, Information and Coding Theory
K. Sayood, Introduction to Data Compression

Computing:

Computing will be done on the CDF computer system, on which you will receive an account soon. If you are not familiar with this system, you should get A Student's Guide to CDF, available from the bookstore.

Marking Scheme:

Final exam, worth 40%.
Four assignments, worth 5%, 10%, 5%, and 10%.
Two one-hour in-class tests, each worth 15%.
The tests are tentatively scheduled for February 15 and March 22, during the tutorial time.

Please read the important course policies

Tests

Here are the questions on test 1 in Postscript, and the answers to test 1.

Assignments

Assignment 1 handout: Postscript, PDF.
Assignment 1 solutions: Postscript, PDF.

Assignment 2 handout: Postscript, PDF.

Here's a little shell file that illustrates one way that you might handle the task of running the tests for this assignment.

The program modules for use with assigment 2 are available on CDF in the directory /u/radford/310. Here are all the files needed, in case you want to work with them at home:

  Documentation  Makefile  code.c  decode.c  encode.c  freq.c
  HiMom          bit-io.c  code.h  decpic.c  encpic.c  freq.h

And here are the additional files that make up my solution to the assignment:

  Discussion  tst-results   html-encode.c  html.h
  chk         tst-plot.ps   html-decode.c  html-contexts.c
  tst         tst-plot.pdf  html-freq.c
You can also now get to these files in /u/radford/310 on CDF.

Assignment 3 handout: Postscript, PDF.
Assignment 3 solutions: Postscript, PDF.

Assignment 4 handout: Postscript, PDF.
Clarification: The table of results produced should have one line with statistics for all 10000 messages sent, plus lines for the subsets of messages in which the total number of transmission errors for all 49 bits of the codeword is 0, 1, 2, etc. Contrary to what you might have heard in tutorial, you should not hand in the a printout with 10000 lines containing the results of decoding each and every one of the 10000 simulated messages.
Note: If you find that simulating 10000 messages is taking an unreasonable amount of time, you can simulate just 1000 messages (thought this is less desirable).

Assignment 4 solution: program, results and discussion.

Slides, readings, and exercises for each week

Here are the overhead slides for each lecture, four per page, in PDF and Postscript formats, organized by week (1, 2, 3, ...) and by lecture within week (A and B). To read these, you'll need one or the other of the free acroread program (for PDF) or the free ghostview program (for both PDF and Postscript). Note that there are links for all lectures, but not all of the slides are there yet. Also, the correspondence with actual lectures may be only approximate. I've also listed the appropriate sections of the textbooks to read (JJ is the Jones and Jones text, S is the Sayood text), and suggested exercises (non-credit), which may be discussed in tutorials.
           SLIDES IN   SLIDES IN   REQUIRED     OPTIONAL        NON-CREDIT
   WEEK    PDF FORMAT  POSTSCRIPT  READINGS     READINGS        EXERCISES

 1 Jan  7     A  B        A  B                  S Ch. 1
 2 Jan 14     A  B        A  B     JJ Ch. 1     JJ Appendix A   JJ 1.15-1.17
 3 Jan 21     A  B        A  B     JJ Ch. 2     S Sec. 3.1-3.3  JJ 2.14,2.11
 4 Jan 28     A  B        A  B     JJ Ch. 3     S Sec. 2.2      S Ch.2 #4, JJ 3.13
 5 Feb  4     A  B        A  B     S Ch. 4
 6 Feb 11     A  B        A  B     S Sec. 3.8,  S Sec. 3.4
                                      6.1-6.3
 7 Feb 25     A  B        A  B     S Ch. 5
 8 Mar  4     A  B        A  B     JJ Ch. 4                     JJ 4.6,4.7
 9 Mar 11     A  B        A  B     JJ 5.1-5.3                   JJ 5.9
10 Mar 18     A  B        A  B     JJ 6.1-6.2,                  JJ 6.1,6.4,
                                      7.1-7.2                      7.1,7.2
11 Mar 25     A  B        A  B     JJ 6.3-6.5,                  JJ 6.7
                                      7.3,7.4,
                                      7.6,7.7
12 Apr  1     A  B        A  B     JJ 5.4-5.6   JJ Appendix C
13 Apr  8     A  B        A  B                  S 7.1-7.5