Information theory 2023

November 24, 2023

This is Year 2023 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.

Course Period: Aug. 28^th 2023 – Dec. 12^th 2023
There are 26 lectures.
There are 15 lectures before midterm and 12 lectures after midterm
Grading: Attendance 20%, Midterm 30%, Final 30%, Homework 20%

lnfo-Theory-Note_2023_09_20

HW-Collections-with-Cover-Tomas

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

SYLLABUS

week	Monday	Wednesday	Lecture note
1	8/28 First class-intro to the course Introduction to Information Theory	8/30 Probability and Random Variables	Preliminary Test
2	9/4 Monte Hall	9/6 Information/Horse Race	Chapter2 with HW1 HW#1 due 9/18 Grading due 9/25
3	9/11 Entropy	9/13 Mutual Information
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	HW#2 due 9/27 Grading due 10/4 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, One more example on Sufficient Statistics, Fano’s Inequality Problem 2.23 Cover on Thomas Part 1, Problem 2.23 Cover on Thomas Part 2, Statistics Sufficient part 1, Statistics Sufficient part 2	9/27 Video links: Fano’s Inequality Proof, Types of Convergences, Relationship between different types of Convergences, Law of Large Numbers & Surface Hardening Review of Types of convergences, Asymptotic Equipartition Property (AEP), The size of the Typical Set,	HW#3 due 10/11 Grading due 10/18 One more example on Sufficient Statistics Typical Set.exel Shannon’s paper
6	10/2 Chu-Suk hoilyday	10/4 Video links: High Probability Set vs. Typical Set, Entropy Rate & Shannon’ s English Description, Cesaro Mean	Quiz #1 Problem 2.23 note Textbook Example of Sufficient Statistic
7	10/9 한글날	10/11 Video links: Data Compression, Non Singular Code & Uniquely Decodable Code, Prefix Code, Kraft Inequality	HW#4 due 10/18 Sol man due 10/20 Data Compression Chapter4 – Chapter5 with HW4
8	10/16 Video links: Optimal Codes, Huffman Code, Huffman Codes Vs Shannon Codes, Lempel-Ziv Code	10/18 Review for Midterm
9	10/23 Midterm		Midterm week
10	10/30 No class. Please sutdy the node and videos Video links: Hamming Codes as a channel code, Hamming Codes Encoding and Decoding	11/1 Video links: Introduction to Channel Capacity,	HW#5 due 11/13 sol man due 11/15 Channel-capacity and HW5 Hamming Codes
11	11/6 Video links: Hamming codes, Erasure error correction, Channel Capacity Definition, Noisy Typewritter	11/8 Video links: Cap of BSC, Cap of BEC plus 1, Cap of BEC plus 2, Weakly Symmetric channels, Symmetric channels	HW#6 due 11/20 sol man due 11/22 Information Bit Error Rate for (7,4) Hamming code with HW6
12	11/13 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	11/15 Video links: Channel Coding Theorem Set up, Channel Coding Theorem Key Ideas, Channel Coding Theorem Forward Proof	Proof of Channel Capacity Theorem with HW7
13	11/20 Video links: Converse Proof Zero Error Capacity, Converse Proof using Fano’s Inequality	11/22 Video links: Gaussian Channel Capacity – Differential Entropy1, Gaussian Channel Capacity – Differential Entropy2, Gaussian Channel Motivation , The additive white Gaussian Channel	Quiz #2 on 11/22 HW#7 due 11/29 sol man due 12/1 Gaussian Channel Capacity and Gaussian Channel
14	11/27 Video links: Gaussian Channel Capacity, Gaussian Coding Theorem Sphere Packing, Gaussian Coding Theorem Forward Backward	11/29 Video links: Parallel Gaussian Channels, PGC with colored noise	HW#8 Do not submit Parallel Gaussian Channel Capacity-HW8
15	12/4 Multiple Access Chnannels, Slepian-Wolf Coding	12/6 Final Preparation
16	12/11 Final Exam		Final Week