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
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.cYou 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 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