CSC 310 - Information Theory (Jan-Apr 2004)

All work has now been marked. Assignments and can be picked up from my office (phone to see if I'm in). The term and final exam marks are available here. Please let me know of any errors.

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, Office: SS 6016A, Phone: (416) 978-4970, Email:

Office hours: Tuesdays from 2:30pm to 3:30pm and Fridays from 10:10am to 11:00am.


Mondays and Wednesdays, 3:10pm to 4:00pm, from January 5 to April 8, except for Reading Week (February 16-20), in BA 1200.


Fridays, 3:10pm to 4:00pm, from January 16 to April 2, except for Reading Week (February 16-20), in SS 1084 or 1086. We've decided that two tutorial sections are enough. Students in the first half of the alphabet should go to SS 1084, those in the last half to SS 1086. (Or arrange yourselves as needed if one room or the other is crowded.)

Course text:

David J. C. MacKay, Information Theory, Inference, and Learning Algorithms. See also the author's web site, which includes errata for the book. The copies in the bookstore appear to be from the first printing.


Computing will be done on the CDF computer system. Talk to me if you don't know your account name. 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, scheduled by the Faculty, worth 48%.
Four assignments, worth 6%, 10%, 6%, and 10%.
A 50-minute in-class test, worth 20%, scheduled for February 27 (in tutorial).

Please read the important course policies

Tutorial notes

The point of tutorials is to work through examples and supplementary material in an interactive manner. The process of figuring out these examples is as important as the result. You should not expect the tutorial instructor to just `give' you the answers, since this destroys the usefulness of the tutorial for you and the other students.

Nevertheless, although it's not really necessary, some students have asked for my notes on the tutorials. Here are some of these. These will definitely not be posted before the tutorials, since that would undermine the whole purpose!

    tut2  tut3  tut4  tut5  tut6  tut7  tut8


Here are the questions and answers for the test: Postscript, PDF.

Final Exam

You can look at past final exams for this course at the Arts and Science web page for this, which is here. However, note that Question 7(a) on the 2002 exam should have read "Find a generator matrix for this code, or for an equivalent code, in systematic form".

No books or notes will be allowed for the final exam. Calculators will be allowed.


Assignment 1: Postscript, PDF. Here is the solution, in Postscript, and PDF.

Assignment 2: Postscript, PDF.

To do assignment 2, you will need the package of C procedures for arithmetic coding. The package has changed slightly (in Makefile and code.h) from the version put here earlier. Note that this package does arithmetic coding using finite precision integers in a somewhat different (and more efficient) way from the algorithm presented in lecture.

You can get these procedures, plus documentation and example programs using them, as a single Unix tar file, or you can get the files individually by clicking below:

  Documentation  Makefile  code.c  decode.c   decpic.c  encmono.c  freq.c  testpages
  HiMom          bit-io.c  code.h  decmono.c  encode.c  encpic.c   freq.h
These files are also on CDF in the directory /u/radford/310.

You will also need the test images, which you can obtain from the same directory on CDF, or you can download them by clicking below:

page1 page2 page3 page4 page5
You can view these images in your browser by clicking on the .bmp files below. However, these are not the files you should try to compress, since they have extra header information in them.
page1.bmp page2.bmp page3.bmp page4.bmp page5.bmp

As a check on whether things are working properly for you, here is the output produced by testpages.

Note: A solution to the binary IO problem for Windows due to Cosmin Truta is available here.

Solution: Here is an encode program and a decode program for solving both parts. Here are the commands run for part1, and the output for part 1, and the commands run for part 2, and the output for part 2. Both use the testpages2 script. Finally, here is the discussion.

Assignment 3: Postscript, PDF. Here is the solution, in Postscript, and PDF.

Assignment 4: Postscript, PDF. Here are the parity check matrix and the received data to use for the assignment. Here is the solution: program, output and discussion.

Lecture slides for each week, and associated readings

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 sections of the textbook by MacKay that relate to each lecture.

 1 Jan  5     A  B        A  B      Chapter 1
 2 Jan 12     A  B        A  B      Sections 2.1, 4.1, 4.2, 5.1, 5.2
 3 Jan 19     A  B        A  B      Sections 5.3, 5.4, 5.5, 5.6
 4 Jan 26     A  B        A  B      Sections 4.3, 4.4, 6.1, 6.2
 5 Feb  2     A  B        A  B      Sections 2.2, 2.3, 2.6, 3.1, 3.2
 6 Feb  9     A  B        A  B
 7 Feb 23     A  B        A  B      Sections 6.4, 6.5
 8 Mar  1     -  B        -  B      Chapter 8, Sections 9.1 - 9.4
 9 Mar  8     A  B        A  B      Sections 9.5 - 9.7
10 Mar 15     A  B        A  B      Sections 1.2, 11.4-11.8, 13.1
11 Mar 22     A  B        A  B      Chapter 50
12 Mar 29     -  B        -  B      Chapter 10
13 Apr  5     A  B        A  B      Chapter 47

Previous versions of this course

Here are the web pages for versions of this course taught previously:
Spring 2003, by Ken Sevcik
Spring 2002, by Radford Neal