Information theory 2022

September 26, 2020

This is Year 2022 Information Theory class at GIST.

Course Outline: Introduction to information theory; topics covered include entropy, mutual information, asymptotic equipartition theory, entropy rate, data compression, capacity of noisy channels, channel coding theorem. Application of the fundamental information theoretic ideas to blockchains, machine learning and classification, channel codes and cryptography.

Textbook : “Elements of Information Theory, by Cover and Thomas, Wiley, New York, 2006.”

Grading: Attendance 20%, Midterm 30%, Final 30%, Homework 20%

SYLLABUS

week	Monday	Wednesday	Lecture note
1	8/28 First class-intro to the course	8/30 Probability and Random Variables	Introduction to Information Theory Preliminary Test
2	9/4 Probability and Random Variables	9/6 Monte Hall	Probability and Random Variables
3	9/11 Information/Horse Race	9/13 Entropy	Chapter2 with HW1
4	9/18 Video links: Jensen’s Inequality, Relative Entropy part 1, Relative Entropy part 2 and Mutual Information, Mutual Information, Conditioning reduces entropy	9/20 Video links: Concavity of log, Concavity of Entropy : other approach, Zero MI and Independence, Markov chain and Data Processing Inequality, State Markov Chain 2nd Thermodynamics	Chapter2 – 3 with HW2 and HW3 Jensen Inequality Hash Algorithm과 PoW 성공 확률 Independance – Sufficient Statistics
5	9/25 Video links: Sufficient Statistics: Example and Proof 1, Sufficient Statistic Proof 2,	9/27 Video links: One more example on Sufficient Statistics, Fano’s Inequality	One more example on Sufficient Statistics
6	10/2 Video links: Fano’s Inequality Proof, Types of Convergences, Relationship between different types of Convergences, Law of Large Numbers & Surface Hardening	10/4 Video links: Problem 2.23 Cover on Thomas Part 1, Problem 2.23 Cover on Thomas Part 2, Statistics Sufficient note part 1, Statistics Sufficient note part 2	Problem 2.23 note Textbook Example of Sufficient Statistic
7	10/9 Video links: Review of Types of convergences, Asymptotic Equipartition Property (AEP), The size of the Typical Set, AEP Examples 1,2,3, AEP Examples 4,5,	10/11 Video links: High Probability Set vs. Typical Set, Markov Inequality & Chebyshev inequality, Entropy Rate & Shannon’ s English Description, Cesaro Mean	Chapter4 – Chapter5 with HW4 Typical Set.exel Shannon’s paper
8	10/16 Video links: Data Compression, Non Singular Code & Uniquely Decodable Code, Prefix Code, Kraft Inequality	10/18 Video links: Optimal Codes, Huffman Code, Huffman Codes Vs Shannon Codes, Lempel-Ziv Code	Data Compression
9	10/23 Midterm
10	10/30	11/1
11	11/6 Video links: Introduction to Channel Capacity, Hamming Codes as a channel code, Hamming Codes Encoding and Decoding	11/8 Video links: Hamming codes, Erasure error correction, Channel Capacity Definition, Noisy Typewritter	Channel-capacity Hamming Codes
12	11/13 Video links: Cap of BSC, Cap of BEC plus 1, Cap of BEC plus 2, Weakly Symmetric channels, Symmetric channels	11/15 Video links: Channel Coding Theorem Proof, Properties of Channel Capacity, Information bit error rate 1, Information bit error rate 2, Information bit error rate 3	Channel-capacity and HW5 Information Bit Error Rate for (7,4) Hamming code with HW6
13	11/20 Video links: Channel Coding Theorem Set up, Channel Coding Theorem Key Ideas, Channel Coding Theorem Forward Proof	11/22 Video links: Converse Proof Zero Error Capacity, Converse Proof using Fano’s Inequality	Proof of Channel Capacity Theorem with HW7
14	11/27 Video links: Gaussian Channel Capacity – Differential Entropy1, Gaussian Channel Capacity – Differential Entropy2, Gaussian Channel Motivation , The additive white Gaussian Channel	11/29 Video links: Gaussian Channel Capacity, Gaussian Coding Theorem Sphere Packing, Gaussian Coding Theorem Forward Backward	Gaussian Channel Capacity and Gaussian Channel
15	12/4 Video links: Parallel Gaussian Channels,	12/6 Video links: PGC with colored noise	Parallel Gaussian Channel Capacity
16	12/11 Final Exam		Final Week