Information Theory and Coding ‒ IPG ‐ EPFL

Instructor	Emre Telatar
Office	INR 117
Phone	+41 21 69 37693
Email	[email protected]
Office Hours	By appointment


Teaching Assistant	Elie Najm
Phone	+41 21 69 37535
Office	INR141
Email	[email protected]
Office Hours	By appointment


Teaching Assistant	Aleksei Triastcyn
Phone	+41 21 69 36674
Office	INR 238
Email	[email protected]
Office Hours	By appointment


Teaching Assistant	Pierre Quinton
Email	[email protected]

Lectures	Monday	13:00 – 15:00 (Room: ELA 1)
	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

Your midterm exam will take place on Tuesday October 31^st, at 13:15 in BCH 2201.
You are allowed to bring a two-sided A4 handwritten cheat sheet.
The material covered is up to and including Homework 6.

Graded Homework

The graded homework is out on Tuesday, November 21^st and is due on Monday, December 4^th at 13:15.
You are allowed to collaborate among yourselves but you have to write your own solution and indicate who you collaborated with.

Final Exam

Your final exam will take place on Tuesday January 23^rd, at 08:15 in CM 1105 and CM 1106.
You are allowed to bring 2 two-sided A4 handwritten cheat sheets (2 sheets, 4 pages).
The exam covers all the material seen in class during the semester.

Detailed Schedule

Date	Topics Covered	Assignment	Solutions	Remarks
Sep 18				Public Holiday
Sep 19	– 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 – Kraft’s inequality for non-singular codes	hw1.pdf	sol1.pdf
Sep 25	– Kraft’s inequality for uniquely decodable codes – Reverse Kraft’s inequality – Expected codeword length – Entropy as a lower-bound to the expected codeword length
Sep 26	– 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
Oct 02	– 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
Oct 03	– Short reminder for Markov Chains – Minimal and maximal values of H(U) – Data Processing inequality – Entropy Rate – Entropy rate of Stationary Processes	hw3.pdf	sol3.pdf
Oct 09	– Coding Theorem for Stationary Sources – Fixed-to-Fixed Length Source Codes – Typicality
Oct 10	– Properties of Typical Sets – Asymptotic Equipartition Property – Source Coding via Typicality – Universal coding example for iid binary sources	hw4.pdf	sol4.pdf
Oct 16	– Finite state machine (FSM) compressors – invertible machines, information lossless (IL) machines – lower bound to the output length for IL FSMs
Oct 17	– Lempel-Ziv data compression algorithm – analysis and competitive optimality of Lempel-Ziv with respect to FSMs. – asymptotic optimality of Lempel-Ziv	hw5.pdf	sol5.pdf	Notes on Lempel-Ziv
Oct 23	– Communication channels – memoryless/stationary channels, communication without feedback – C(W) = max I(X;Y), examples with binary erasure channel and binary symmetric channels
Oct 24	– Fano’s inequality – Converse to the coding theorem	hw6.pdf	sol6.pdf
Oct 30	– computation of C(W), KKT conditions	midterm_2015.pdf midterm_2014.pdf midterm_2013.pdf	midsol_2015.pdf midsol_2014.pdf midsol_2013.pdf
Oct 31	Midterm	midterm.pdf	midsol.pdf
Nov 06	– channel coding theorem – proofs by random constructions
Nov 07	– proof of the channel coding theorem via random codes and typicality decoder	hw7.pdf	sol7.pdf
Nov 13	– revisit the random coding method for the BEC – differential entropy and its properties
Nov 14	– Properties of differential entropy – Entropy-typical seqeuences – Quantization – Entropy of Gaussian distribution	hw8.pdf	sol8.pdf
Nov 20	– Capacity under cost constraint – Capacity of AWGN – Converse to the channel coding theorem with cost constraint
Nov 21	– Parallel Gaussian channels (water-filling) – Proof of Channel Coding Theorem for general channels via Threshold Decoding – Hamming code – Hamming weight – Hamming distance	hw9.pdf Graded Homework	sol9.pdf Graded homework sol
Nov 27	– Sphere-packing bound – Gilbert bound – Singleton bound – Linear codes – Generator and parity check matrices
Nov 28	– Reed-solomon codes – Polar codes	hw10.pdf	sol10.pdf
Dec 04	– Polar codes			Coding Notes
Dec 05	– Polar codes	hw11.pdf	sol11.pdf
Dec 11	– Rate distortion
Dec 12	– Rate distortion	hw12.pdf	sol12.pdf
Dec 18	– Multi-access channel
Dec 19	– Multi-access channel	hw13.pdf	sol13.pdf
Jan 23		final.pdf	finalsol.pdf

Textbook

T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley 2006.

Additional Reading Material

C. E. Shannon, A Mathematical Theory of Communications, Bell System Technical Journal, 1948.
Notes on Tunstall Coding.
Notes on Lempel-Ziv Algorithm

To Review Basic Probability Theory

K. L. Chung, A Course in Probability Theory, Academic Press.
W. Feller, An Introduction to Probability Theory and Its Applications, Wiley.
G. Grimmett and D. Stirzaker, Probability and Random Processes, Oxford University Press.
A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-Hill.
S. M. Ross, A First Course in Probability, Pearson Education.