MATH - MTHE 474/874 - Information Theory
Fall 2023
Instructor
-
Fady Alajaji
Office: Jeffery Hall, Room 402
Telephone: 533-2423
E-mail: fa@queensu.ca
-
Course Website: OnQ
-
-
Textbook
-
F. Alajaji and P.-N. Chen,
An Introduction to Single-User Information Theory,
Springer, 2018.
[errata]
-
References
-
T. M. Cover and J. A. Thomas, Elements of Information Theory, Second Edition, John Wiley, 2006.
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.
-
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
Queen's Student Accessibility Services.
-
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.
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 compression, processing and 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,
cross-entropy, mutual information; properties of information measures;
generalized information measures (Rényi entropy and divergence,
Jensen-Shannon divergence);
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; design and 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 and Shannon's separation principle.
- 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 and the Shannon limit of communication systems.
Interesting Links
Claude E. Shannon
IEEE Information Theory Society
Canadian Society of Information Theory (CSIT)
How We Know by Freeman Dyson,
published in The New York Review of Books, March 10, 2011
