MATH 474/874 - Information Theory
Fall 2011
Instructor
-
Fady Alajaji
Office: Jeffery Hall, Room 402
Telephone: 533-2423
E-mail: fady@mast.queensu.ca
-
Teaching Assistant
-
Ghady Azar
E-mail: ghady@mast.queensu.ca
-
Announcements
-
-
Lectures
-
Slot 21: Monday 2:30, Tuesday 4:30, Thursday 3:30 -- Jeffery Hall, Room 115.
-
Homeworks
- The homework assignments will
be posted on this web site (click here to access
them); no paper copies will be handed out.
There will be a total of five problem sets.
Solutions to the assignments will be available on reserve in the
Engineering and Science Library (Douglas Library).
-
Office Hours
-
Tuesday: 9:30 - 11:30, or by appointment.
-
Textbook
-
Class Notes.
Online Lecture Notes: PDF . (Updated Nov. 10, 2011.)
T.M. Cover and J.A. Thomas, Elements of Information Theory,
Second Edition, John Wiley, 2006.
-
References
-
R. Gallager, Information Theory and Reliable Communication,
John Wiley, 1968.
R. Blahut, Principles and Practice of Information Theory,
Addison Wesley, 1987.
R. Yeung, Information Theory and Network Coding,
Springer, 2008.
-
Grading
-
Homeworks: 10%
Midterm Exam: 30%
Final Exam: 60%
-
Note: Undergraduate students enrolled
in MATH-474 will receive
a reduced load in the homeworks and exams.
The Midterm Exam is tentatively
scheduled for Wednesday November 9, 2011.
-
All assignments and exams in this course will receive numerical marks. The final
grade students receive for the course will be derived by converting their numerical
course average to a letter grade according to the
Queens Official Grade Conversion Scale.
-
Policy for Missing Exams:
-
There will be no
makeup exams. If a student misses the midterm
due to severe illness or a personal tragedy, then
the final exam will count towards 90% of the
student's mark.
-
Students with Special Needs:
-
Students with diverse learning styles and needs are welcome at Queen's. In
particular, if you have a disability or health consideration that may require
accommodations, please feel free to approach me and/or the Disability Services Office
as soon as possible at (613) 533-6467. The Disability Services staff is available by
appointment to develop individualized accommodation plans, provide referrals and
assist with advocacy. The sooner you let us know about your needs, the better we can assist
you in achieving your learning goals at Queen's. For further information, visit
Health, Counselling and Disability Services website at
http://www.queensu.ca/hcds/ds.
-
Academic Integrity:
-
Academic integrity is constituted by the five core fundamental values of honesty,
trust, fairness, respect and responsibility.
These values are central to the building, nurturing and sustaining of an academic
community in which all members of the community will thrive. Adherence to the values
expressed through academic integrity forms a foundation for the "freedom of inquiry
and exchange of ideas" essential to the intellectual life of the University
(see the
Senate Report on Principles and Priorities.)
Students are responsible for familiarizing themselves with the regulations concerning
academic integrity and for ensuring that their assignments conform to the principles
of academic integrity. Information on academic integrity is available on these websites:
Arts and Science
and
Engineering and Applied Science.
Departures from academic integrity include plagiarism, use of unauthorized materials,
facilitation, forgery and falsification, and are antithetical to the development of an
academic community at Queen's. Given the seriousness of these matters, actions which
contravene the regulation on academic integrity carry sanctions that can range from
a warning or the loss of grades on an assignment to the failure of a course to
a requirement to withdraw from the university.
-
Outline
-
The reliable transmission of information bearing signals over a noisy
communication channel is at the heart of what we call communication.
Information theory -- founded by
Claude E. Shannon in 1948 --
provides a mathematical framework for the theory
of communication; it describes the fundamental
limits to how efficiently one can encode
information and still be able to recover it with negligible loss.
This course will examine the basic concepts of this theory.
What follows is a list of topics to be covered.
- Shannon's Measures of Information: entropy, divergence,
mutual information; properties of information measures;
the data processing theorem; Fano's inequality.
- Fundamentals of Fixed-Length Lossless Source Coding
(Data Compression):
discrete memoryless sources,
asymptotic equipartition property (AEP),
block or fixed-length coding,
fixed-length source coding theorem for discrete memoryless sources;
entropy rate of stationary sources with memory, Markov sources,
stationary ergodic sources, fixed-length source coding theorem for
stationary ergodic sources; source modeling and redundancy.
- Fundamentals of Variable-Length Lossless Source Coding:
variable-length encoding, unique decodability, Kraft inequality,
prefix codes, variable-length source coding theorem
for discrete memoryless sources and for stationary sources
with memory; Shannon-Fano code; construction of optimal variable-length
codes: Huffman codes.
- Fundamentals of Channel Coding:
discrete memoryless channels,
channel capacity and properties; noisy channel coding theorem
for discrete memoryless channels;
the lossless joint source-channel coding theorem.
- Information Theory for Continuous Alphabet Systems:
differential entropy, divergence and mutual information;
differential entropy of the
multivariate Gaussian distribution; AEP for continuous alphabet
memoryless sources, capacity
of discrete-time and band-limited continuous-time memoryless Gaussian channels;
parallel Gaussian channels and waterfilling.
- Rate-Distortion Theory:
(time permitting) lossy data compression;
discrete memoryless sources,
rate-distortion function and its properties; rate-distortion theorem;
the lossy joint source-channel coding theorem.
Interesting Links
IEEE Information Theory Society
Canadian Society of Information Theory (CSIT)
Data-Compression.Com
How We Know by Freeman Dyson,
published in The New York Review of Books, March 10, 2011
