Target audience:
Advanced ECE/CSE/Math undergrads.
Postgraduate students from ECE/CSE (with theoretical inclination), and Math postgraduate students.
[This is a theoretical course, and the rigour will not be diluted under any circumstance. ]
Course description: Algorithms have always been designed to make communication systems, or for that matter any system, more reliable, less memory consuming, more efficient in using system resources, etc. This then begs the question, how does one know if an algorithm is optimal, i.e., whether it ensures the minimum possible usage of system resources in accomplishing its task? In other words, we want to ask, what are the fundamental limitations that a system and a given task imposes on all possible algorithms that can solve that given task?
One possible way to tackle such questions is through the discipline of information theory, and this course is meant as an intorduction to this field. The course will broadly cover three canonical systems: The lossless storage system requiring minimal storage space consumption with perfect recovery, the noisy communication channel requiring maximum communication rates for arbitrarily low probability of decoding error, and the lossy storage system requiring minimal storage space while allowing a pre-defined level of distortion in the recovered data. To tackle these three broad problems, we shall first introduce the fundamental information theoretic quantities such as entropy, relative entropy, mutual information, and study their properties. Next, we shall introduce various tools required for proofs such as asymptotic equipartition property, Fano's inequality, method of types, data processing inequality. Finally, the student will be introduced to the probabilistic method for obtaining proofs. We shall then leverage these proof techniques to see how the fundamental limits of the above-mentioned systems can be expressed in terms of the quantities such as entropy, relative entropy, and mutual information.
Individual or groups of students (depending on the number of attendees) will be asked to choose and explore one further topic from a curated list of topics from areas such as network information theory, applications of information theory, information theoretic security, common information. The students would be required to prepare a report summarising their understanding of their chosen topic, as part of their evaluation.
Course objectives/Learning outcomes:
Formulate and solve data compression problems and evaluate their fundamental limits.
Evaluate the fundamental limits of information transmission.
Analyze and evaluate fundamental information theoretic quantities.
Differentiate between and achievability and a converse parts of a proof.
Apply probabilistic methods.
Course notes: Find here.
Assignments and examinations: