Information Theory 1

InfoTheo_1
Abstract

Since 1948, the year of publication of Shannon’s landmark paper “A mathematical theory of communications”, Information theory has paved the ground for the most important developments of today’s information/communication world making it perhaps the most important theoretical tool to understand the fundamentals of information technologies. The main objective of this course is to provide an introductory-level coverage of Information Theory. Information theory studies the ultimate theoretical limits of source coding and data compression, channel coding, and reliable communications via channels, and provides the guidelines for the development of practical signal-processing and coding algorithms. The course is meant to provide an intuitive point of view and foundation for both research and practice.

Teaching & Learning Methods: Lectures and homework.

Course policies: 

Attendance Policy: Attendance is expected and required in every class period, unless previously discussed with the instructor. We will cover a lot of ground in this course to build a strong foundation for Information Theory, so attendance is important. To encourage learning, preparation, and participation, the lectures will be complemented by additional reading or review materials, e.g., slides, papers, MATLAB codes, and online course materials to cover some of the basic concepts prior to the lectures.

Other Course Policies: All mobile devices (e.g., smartphones, tablets, computers) should be stored securely away during lecture and are not be used unless specifically directed otherwise by the instructor. Use of a mobile device during an exam without the explicit permission of the instructor will be interpreted as the illicit transfer of exam data, will be considered an act of cheating and will be treated as such.

You are expected to approach the instructor with any issue that may affect your performance in class ahead of time. This includes absence from important class meetings, late assignments, inability to perform an assigned task, the need for extra time on assignments, etc. You should be prepared to provide sufficient proof of any circumstances based on which you are making a special request.

Academic Integrity: Student-teacher relationships are built on trust. For example, students must trust that teachers have made appropriate decisions about the structure and content of the courses they teach, and teachers must trust that the assignments that students turn in are their own. Acts that violate this trust undermine the educational process. In this class, all assignments that are turned in for a grade must represent the student’s own work. Submission of any assignment that is in violation of this policy may result in a penalty of an F in the class and may be subject to further disciplinary action.

If you have any questions concerning this policy before submitting an assignment, please ask for clarification.

Bibliography

Text (Required and available at the library):

  • Book: COVER T., THOMAS J. Elements of Information Theory. Edition 2, John Wiley & Sons, 2012, 784p.

Supplementary Resources (Not Required):

  • Book: GALLAGER, ROBERT G., Information Theory and Reliable Communication. New York: Wiley, 1968.
  • Book: Gray, Robert M., Entropy and Information Theory. Springer Science & Business Media, 2011.
  • Book: AHLSWEDE A., ALTH¨OFER I., DEPPE C., TAMM, U. Probabilistic Methods and Distributed Information. Springer International Publishing, 2019.
  • Publication: WEISSMAN, TSACHY. “EE 376A: Information Theory” (2016).
  • Publication: POLYANSKIY Y., Wu Y. Lecture notes on information theory. Lecture Notes for ECE563 (UIUC) (2014) and, 6(2012-2016), 7.
  • Book: EL GAMAL, ABBAS, YOUNG-HAN KIM. Lecture notes on network information theory. (2010).
  • Book: MACKAY, DAVID JC. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003.
  • Book: CSISZ´AR, IMRE, J´ANOS K¨ORNER. Information theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011.
  • Book: LEINSTER, TOM. Entropy and Diversity: The Axiomatic Approach. Cambridge University Press, 2021.
  • Book: SHAMAI, SHLOMO, ZAIDI, ABDELLATIF. Information Theory for Data Communications and Processing. Entropy 22.11 (2020).

Requirements

Basic knowledge in statistics and probabilities. Basic MATLAB knowledge for the lab session - No C programming needed.

Description

We will cover the following topics from Cover and Thomas:

  • An introduction to information theory
  • Discrete entropy, joint entropy, mutual information, divergence
  • The Asymptotic Equipartition Property
  • Data compression, source coding: Huffman codes, universal data compression.
  • Channel capacity and coding
  • The channel coding theorem: communicating with zero probability of error
  • Differential entropy and its properties
  • Gaussian channel: Capacity of discrete-time Gaussian channels, correlated noise.
  • Parallel Gaussian channels, multicarrier modulation via waterfalling
  • Rate-distortion theory: Compression of Gaussian sources, vector quantization.
  • Topics in network information theory: The multiple-access, the broadcast channel, and encoding of correlated sources.

Online Tools: Moodle will be used to support this course. If you do not have access to this tool, please inform the instructor as soon as possible.

  • Primary use is for class announcements, class discussion, and posting questions.
  • Contains all course information and links.
  • Contains lecture notes, homework assignments, solutions and back exams; you are responsible for knowing any information that appears there.

Course Calendar (Tentative)

 

DATE

TOPIC

READINGS

(C. & T.)

ASSIGNMENTS

T 2/28

An introduction to information theory

1

/

T 3/07

Discrete entropy, joint entropy, mutual information, divergence

2

/

T 3/14

The Asymptotic Equipartition Property; Data compression, source coding: Huffman codes, universal data compression.

3, 5

/

T 3/21

Channel capacity and coding

7

/

T 3/28

The channel coding theorem: communicating with zero probability of error

7

HW 1 due

T 4/04

Lab Session with Selected Topic

/

Report/Code

T 4/11

Midterm exam

/

/

T 4/18

Differential entropy and its properties, Entropy rates of a stochastic process

8, 4

/

T 5/09

Gaussian channel: Capacity of discret-time Gaussian channels, correlated noise.

9

/

T 5/16

Parallel Gaussian channels, multicarrier modulation via waterfilling

9

/

T 5/23

Rate-distortion theory: Compression of Gaussian sources, vector quantization.

10

/

T 5/30

Topics in network information theory: The multiple-access, the broadcast channel, encoding of correlated sources (the Slepian-Wolf theorem)

15

/

T 6/06

Lab Session with Selected Topic

/

Report/Code

T 6/13

TBD

/

HW 2 due

T 6/?

Final exam

1, 2, 3, 5, 7-10, 15

/

Learning Outcomes: 

  • Understand the basic concepts: What is information, and how is it measured? How is it communicated and compressed and what are the limits? 
  • Understand how to communicate and compress it in a network?

Nb hours: 42.00

Evaluation: 

Homework: 2 homeworks will be assigned and posted on Moodle. These homeworks will be paper-andpencil problems to hand in and may include MATLAB problems. You may discuss problems with other students, but you must prepare your solution with your group (each group involves 4 or 5 students). Homework is due at the start of class (defined as the first 10 minutes) on the date indicated. Late homework will not be accepted. Any questions about grading should be directed to Dr. Malak.

Exams:Exams will be closed book. Dr Malak will assist in grading and handle any questions or appeals.

The grade will be based on the average homework grade (worth 15%), Matlab (worth 15%), a midterm exam (worth 25%), and a final exam (worth 45%).

Regrading Policy: Grade appeals, on homework or exam, must be submitted in writing within 72 hours of their return to the class. No verbal complaints will be considered. Grade appeals on homework and exams should be made to the professor within 72 hours of its return to the class. I will not consider appeals immediately after an exam is handed back unless they relate to an error in adding up points. Please take the time to carefully compare your solution to the posted exam/homework solutions before appealing.