===== Information Theory & Coding ===== \\ |Instructor|**Emre Telatar**| |Office|[[http://plan.epfl.ch/?room=INR117|INR 117]]| |Phone|**+41 21 69 37693**| |Email|**emre.telatar@epfl.ch**| |Office Hours|**By appointment**| | | | | | | |Teaching Assistant |**Mani Bastani Parizi**| |Phone|**+41 21 69 31359**| |Office|[[http://plan.epfl.ch/?room=INR032|INR032]]| |Email|**mani.bastaniparizi@epfl.ch**| |Office Hours|**By appointment**| | | | | | | |Teaching Assistant |**Rafah El-Khatib**| |Phone|**+41 21 69 31361**| |Office|[[http://plan.epfl.ch/?room=INR032|INR 032]]| |Email|**rafah.el-khatib@epfl.ch**| |Office Hours|**By appointment**| | | | | | | \\ |Lectures|**Monday** |**13:00 - 15:00** (Room: [[http://plan.epfl.ch/?reset_session&alias=ela1|ELA 1]])| | |**Tuesday** |**13:00 - 15:00** (Room: [[http://plan.epfl.ch/?reset_session&alias=ela2|ELA 2]])| |Exercises|**Tuesday** |**15:00 - 17:00** (Room: [[http://plan.epfl.ch/?reset_session&room=ela2|ELA 2]])| \\ |**Language**:| |English| |**Credits **:| |7 ECTS| \\ See the course {{:en:courses:2015-2016:itc:info2015.pdf|information}}. /* [[http://isa.epfl.ch/imoniteur_ISAP/!itffichecours.htm?ww_i_matiere=1774097&ww_x_anneeAcad=2011-2012&ww_i_section=2139068&ww_i_niveau=&ww_c_langue=en|Link]] to official course description. */ ==== Special Announcements ==== === Midterm Exam === Your midterm exam will take place on **Tuesday October 27, at 13:15** in rooms [[http://plan.epfl.ch/?room=ela2|ELA2]], [[http://plan.epfl.ch/?room=dia003|DIA003]], and [[http://plan.epfl.ch/?room=co120|CO120]]. * Please find your room and seat before the exam according to the following seating plan: * If your last name starts with **A to KAR** please go to room [[http://plan.epfl.ch/?room=ELA2|ELA2]]. * If your last name starts with **KAS to P** please go to room [[http://plan.epfl.ch/?room=DIA003|DIA003]] * If your last name starts with **R to Z** please go to room [[http://plan.epfl.ch/?room=CO120|CO120]] * This is a closed book exam but you are allowed to have __one A4 page of notes (double-sided)__ with you. Here is some statistics about midterm grades: | ^ Average ^ Standard Deviation ^ ^ P1| 6.39 | 3.72 | ^ P2| 9.51 | 4.45 | ^ P3| 5.09 | 4.09 | ^ Total| 21 | 9.18 | You can also find a histogram of the grades {{:en:courses:2015-2016:itc:midterm-histogram.txt|here}}. === Final Exam === Your final exam will take place on **Monday, January 11, 2016, at 8:15** in rooms [[http://plan.epfl.ch/?lang=en&room=INM200|INM200]] and [[http://plan.epfl.ch/?lang=en&room=INM202|INM202]]. * Please be there well in advance to find your room and seat. * This is a closed book exam, but you are allowed to bring __two A4 pages of notes (double-sided)__ with you. ==== Detailed Schedule ==== ^ Date ^ Topics Covered ^ Assignment ^ Solutions ^ Remarks ^ | Sep 14 | - Introduction to Source Coding \\ - Non-singular codes \\ - Uniquely decodable codes \\ - Prefix-free codes \\ - Kraft's inequality for prefix-free codes \\ - Kraft's inequality for extensions of codes | | | | | | Sep 15 | - Kraft's inequality for uniquely decodable codes \\ - Reverse Kraft's inequality \\ - Expected codeword length \\ - Entropy as a lower-bound to the expected codeword length | {{:en:courses:2015-2016:itc:hw1.pdf|}} | {{:en:courses:2015-2016:itc:sol1.pdf|}} | | | Sep 21 | | | | Public Holiday :-) | | Sep 22 | - Existence of prefix-free codes with average length at most entropy + 1 \\ - Entropy of multiple random variables \\ - Properties of optimal codes \\ - Huffman procedure | {{:en:courses:2015-2016:itc:hw2.pdf|}} | {{:en:courses:2015-2016:itc:sol2.pdf|}} | | | Sep 28 | - Equivalence of prefix-free codes and strategy for guessing via binary questions \\ - Interpretation of entropy as expected number of questions for guessing the random variable \\ - Conditional Entropy and Mutual Information \\ - Chain Rules for entropy and mutual information | | | | | Sep 29 | - Review of Markov Chains \\ - Data Processing inequality \\ - Entropy Rate \\ - Entropy rate of Stationary Processes | {{:en:courses:2015-2016:itc:hw3.pdf|}} | {{:en:courses:2015-2016:itc:sol3.pdf|}} | | | Oct 5 | - Coding Theorem for Stationary Sources \\ - Fixed-to-Fixed Length Source Codes \\ - Typicality | | | | | Oct 6 | - Properties of Typical Sets \\ - Asymptotic Equipartition Property \\ - Source Coding by AEP \\ - Variable-to-Fixed Length Source Codes \\ - Valid and Prefix-Free Dictionaries | {{:en:courses:2015-2016:itc:hw4.pdf|}} | {{:en:courses:2015-2016:itc:sol4.pdf|}} | | | Oct 12 | - Relationship between word- and letter-entropies for valid, prefix-free dictionaries \\ - Tunstall procedure \\ - Analysis of Tunstall procedure | | | {{:en:courses:2015-2016:itc:tunstall.pdf|Notes}} on Tunstall Coding | | Oct 13 | - Universal Source Coding \\ - Lempel--Ziv method \\ - Analysis of Lempel--Ziv (finite state machine compressions, FSM compressibility of a sequence, LZ compressibility of a sequence) | {{:en:courses:2015-2016:itc:hw5.pdf|}} | {{:en:courses:2015-2016:itc:sol5.pdf|}} | | Oct 19 | - Information-Lossless FSM Compressors \\ - Lower bound on the output length of an IL FSM Compressor | | | {{:en:courses:2015-2016:itc:lz.pdf|Notes}} on Lempel--Ziv Compression | | Oct 20 | - LZ Compressibility of sequences \\ - Optimality of Lempel--Ziv \\ - Communication Channels \\ - Discrete Memoryless Channels | {{:en:courses:2015-2016:itc:hw6.pdf|}} | {{:en:courses:2015-2016:itc:sol6.pdf|}} | | \\ | Oct 26 | - Examples of Discrete Memoryless Channels (BSC and BEC) \\ - Transmission with or without feedback \\ - Channel Capacity \\ - Fano's Inequality | | | | \\ | Oct 27 | Midterm Exam | {{:en:courses:2015-2016:itc:midterm.pdf|}} | {{:en:courses:2015-2016:itc:midsol.pdf|}} | | \\ | Nov 2 | - Converse to the Channel Coding Theorem | | | | \\ | Nov 3 | - Proof of the Channel Coding Theorem | {{:en:courses:2015-2016:itc:hw7.pdf|}} | {{:en:courses:2015-2016:itc:sol7.pdf|}} | |\\ | Nov 9 | - Capacity of BSC and BEC \\ - Jensen's Inequality \\ - Concavity of Mutual Information in Input Distribution \\ - KKT Conditions | | | | \\ | Nov 10 | - KKT Conditions (cont'd) \\ - Application of KKT: Capacity of Z Channel \\ - Continuous Alphabet: Differential Entropy | {{:en:courses:2015-2016:itc:hw8.pdf|}} | {{:en:courses:2015-2016:itc:sol8.pdf|}} | |\\ | Nov 16 | - Properties of differential entropy \\ - Entropy-typical seqeuences \\ - Quantization \\ - Entropy of Gaussian distribution | | | |\\ | Nov 17 |- Capacity under cost constraint \\ - Capacity of AWGN \\ - Converse to the channel coding theorem with cost constraint \\ - Parallel Gaussian channels (water-filling) | {{:en:courses:2015-2016:itc:hw9.pdf|}} | {{:en:courses:2015-2016:itc:sol9.pdf|}}| | | Nov 23 | - Proof of Channel Coding Theorem for general channels via Threshold Decoding | | | | |\\ | Nov 24 | - Channel Codes \\ - Minimum Distance \\ - Singleton Bound \\ - Sphere-packing Bound \\ - Gilbert--Varshamov Bound | {{:en:courses:2015-2016:itc:hw10.pdf|}} | {{:en:courses:2015-2016:itc:sol10.pdf|}} | |\\ | Nov 30 | - Linear Codes \\ - Generator Matrix \\ - Parity-check Matrix \\ - Hamming Codes | | | |\\ | Dec 1 | - Reed--Solomon Codes | {{:en:courses:2015-2016:itc:hw11.pdf|}} | {{:en:courses:2015-2016:itc:sol11.pdf|}} | | \\ | Dec 7 | - Polar Codes | | | | \\ | Dec 8 | - Polar Codes | {{:en:courses:2015-2016:itc:hw12.pdf|}} | {{:en:courses:2015-2016:itc:sol12.pdf|}} | |\\ | Dec 14 | - Polar Codes | | | |\\ | Dec 16 | - Rate--Distortion Theory | | | |\\ | Jan 11 | Final Exam | {{:en:courses:2015-2016:itc:final.pdf|}} | {{:en:courses:2015-2016:itc:finalsol.pdf|}} | | ==== Textbook ==== * T. M. Cover and J. A. Thomas, //[[http://opac.nebis.ch/F?local_base=nebis&func=find-b&find_code=020&request=0-471-24195-4&con_lng=ENG|Elements of Information Theory]]//, Wiley 2006. ==== Additional Reading Material ==== * C. E. Shannon, {{:en:courses:2015-2016:itc:shannon1948.pdf|A Mathematical Theory of Communications}}, //Bell System Technical Journal,// 1948. * Notes on {{:en:courses:2015-2016:itc:tunstall.pdf|Tunstall Coding}}. * Notes on {{:en:courses:2015-2016:itc:lz.pdf|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, //[[http://opac.nebis.ch/F/6N67R6YCDN9DRKT9J93AGHH2KQQEG1PGCFQLRAYT6KP7F7V579-04801?func=direct&=&=&local_base=EBI01&doc_number=006162185&pds_handle=GUEST&CON_LNG=ENG|Probability and Random Processes]]//, Oxford University Press. * A. Papoulis, //[[http://opac.nebis.ch/F?func=direct&local_base=EBI01&doc_number=000606172|Probability, Random Variables, and Stochastic Processes]]//, McGraw-Hill. * S. M. Ross, //[[http://opac.nebis.ch/F?func=direct&local_base=EBI01&doc_number=005264889|A First Course in Probability]]//, Pearson Education.