Information Theory and Coding

Instructor Emre Telatar
Office INR 117
Phone +41 21 69 37693
Email [email protected]
Office Hours By appointment
Teaching Assistant Yunus Inan
Office INR 033
Phone +41 21 69 36604
Email [email protected]
Office Hours By appointment
Teaching Assistant Reka Inovan
Office INR 033
Phone +41 21 69 36604
Email [email protected]
Office Hours By appointment
Lectures Monday 11:00 – 13:00 (Room: BC01)
Tuesday 13:00 – 15:00 (Room: ELA 2)
Exercises Tuesday 15:00 – 17:00 (Room: ELA 2)
Language: English
Credits : 7 ECTS

Course Information

See the course information.

Special Announcements

Midterm Exam (40%)

    • Midterm date: 29 October, Place: ELA2 and DIA 004.
    • Closed book, closed notes.
    • ONE two-sided A4 cheat sheet allowed.

Graded Homework (10%)

    • Due Tuesday, December 3, at the beginning of the exercise session. You can prepare handwritten or typewritten sheets for the solutions.

Final Exam (50%)

    • Final date: 18 January, 08.15-11.15, Place: CE4.
    • Closed book, closed notes.
    • TWO two-sided A4 cheat sheet allowed.

Detailed Schedule

Date Topics Covered Assignment Solutions Remarks
Sep 16 Public Holiday
Sep 17 – Introduction to Source Coding
– Non-singular codes
– Uniquely decodable codes
– Prefix-free codes
– Kraft’s inequality for prefix-free codes
– Kraft’s sum for products of codes
hw1.pdf sol1.pdf
Sep 23 – Kraft’s inequality for non-singular codes

– Kraft’s inequality for uniquely decodable codes

– Reverse Kraft’s inequality

– Expected codeword length

Sep 25

– Entropy as a lower-bound to the expected codeword length

– Existence of prefix-free codes with expected length at most entropy + 1

– Properties of optimal codes

– Huffman procedure

– Equivalence of prefix-free codes and strategies for guessing via binary questions

hw2.pdf sol2.pdf
Sep 30

– Entropy of multiple random variables

– Source coding by describing words of n letters

– Conditional entropy and mutual information

– Chain Rules for entropy and mutual information

– Short reminder for Markov Chains

– Minimal and maximal values of H(U)

– Data Processing inequality

Oct 01

– Entropy Rate

– Entropy rate of Stationary Processes

– Coding Theorem for Stationary Sources

– Fixed-to-Fixed Length Source Codes

– Typicality

– Properties of Typical Sets

– Asymptotic Equipartition Property

hw3.pdf sol3.pdf
Oct 07 – Source Coding via Typicality

– Finite state machine (FSM) compressors

Oct 08 -Invertible machines, information lossless (IL) machines

– Lower bound to the output length for IL FSMs

hw4.pdf sol4.pdf
Oct 14  (Lecture by Ruediger Urbanke)

– Communication channels

– memoryless/stationary channels, communication without feedback

– C(W) = max I(X;Y), examples with binary erasure channel and binary symmetric channels

-Multi-letter Fano’s Inequality

Oct 15 (Lecture by Ruediger Urbanke)-Weak converse of noisy channel coding theorem

-The necessity part of KKT condition for capacity achieving input distribution.

hw5.pdf sol5.pdf
Oct 21 -Review of the last lecture

-The sufficiency part of KKT condition for capacity achieving input distribution.

-Computation of capacity C(W).

Oct 22 -Information Lossless machines cont.

-Lempel Ziv Algorithm

hw6.pdf sol6.pdf Some old midterm exams



Oct 28 – Channel coding theorem

– Channels with input cost

– Proofs by random constructions

Oct 29 Midterm midterm.pdf midsol.pdf histogram
Nov 4 Exercise session
(No lecture)
hw7.pdf sol7.pdf
Nov 5 -Differential Entropy

-Properties of Differential Entropy

Nov 11 -Relationship between H(X) and h(X)

-Entropy of Gaussian R.Vs

-Capacity of Gaussian Channel

Nov 12 -Parallel Gaussian Channels, water-filling

-Bandlimited AWGN Channels

hw8.pdf sol8.pdf
Nov 18 – Hamming codes- Hamming weight

– Hamming distance

Notes on coding
Nov 19 – Sphere-packing bound- Gilbert bound

– Singleton bound

– Linear codes

– Generator and parity check matrices

hw9.pdf sol9.pdf gradedHW


Nov 25 – Polar Codes
Nov 26 – Polar Codes hw10.pdf sol10.pdf
Dec 2 – Polar Codes
Dec 3 -Rate-Distortion Theory hw11.pdf sol11.pdf
Dec 9 -Rate-Distortion Theory
Dec 10 -Slepian-Wolf Coding hw12.pdf sol12.pdf
Dec 16 -Multiple Access Channels (MAC) (Achievability)
Dec 17 -Multiple Access Channels (MAC) (Converse) hw13.pdf


ITC2019 Final

ITC2018 Final

ITC2016 Final



ITC2019 Final Sol

ITC2018 Final Sol

ITC2016 Final Sol

Jan 18 Final Exam Final Final Sol


Additional Reading Material

To Review Basic Probability Theory