Information Theory and Coding

 Source coding / Data compression:
– injective, uniquely decodable, prefix-free (binary) codes
– Kraft sum, Kraft inequalities

– (Partial) converse to Kraft inequality
– Properties of log (and ln)
– Expected codeword length: lower and upper bounds, asymptotic per-letter tightness

– “Optimal” prefix-free code design: Huffman algorithm
– Entropy and friends (joint, conditional)

– KL divergence, (conditional) mutual information
– Inequalities and properties of information measures
– Data processing inequality

HW 3

– “Distributions, source codes, regret, divergence”
– Entropy rate

– Data compression theorem for stationary sources
– ε-typicality
– Properties of typical sequences and sets

HW 4

– Source coding via typicality
– Joint typicality
– Motivating (toy) example for universal data compression

– Lempel-Ziv algorithm
– Finite-state, information-lossless machines (competitors to LZ)
– Lower bound to lengths of k-distinct words

HW 5

– Proof that LZ beats FSILMs
– Are FSILMs powerful?
– Modifying LZ to deal with finite sequences
– Connections to Learning Theory

– “Memoryful”, memoryless, stationary channels
– Communication with feedback
– Capacity of a stationary, memoryless channel
– Examples: BSC, BEC

HW 6

– Fano’s inequality: relating conditional entropy to probability of error
– Fano’s inequality (bis): multi-letter
– Channel coding converse theorem (bad news)
– Definitions: encoder/decoder pair, rate, error probabilities
– Channel coding achievability theorem (good news; proof upcoming)
– Source-channel separation

– How to maximize mutual information (as in the definition of capacity)
– KKT for general smooth functions (necessary conditions)
– KKT for smooth, concave functions (necessary and sufficient conditions)
– Examples using KKT
– KKT for mutual information maximization
– Connection to min-max regret as seen in source coding

Midterm exam

Midterm

Solutions

– (Goal) proof of “Good News” Thm (maximum error probability)
– Expurgation to get sufficient Thm’ (average error probability)
– Non-constructive, probabilistic method to show existence
– Proof of Thm’ by the probabilistic method
– Alternate decoder: Typicality decoder (vs. maximum likelihood score)

HW 7

– Definitions associated with the “coding theorem”
– Channels with cost
– Aside on random coding and sphere packing exponents
– Coding theorem for channels with cost
– Another example of “proof by random construction” — Multiple-Access Channel

– Differential entropy for real, vector-valued random variables
– Properties of differential entropy
– Relationship between H(.) and h(.)
– (Differential) mutual information
– Differential entropy of Gaussian vectors
– Mutual information of Gaussian channel with Gaussian input

HW 8

– Extremality of h(.) under different conditions
– Additive Gaussian noise channel with power constraint
– Capacity of additive Gaussian channel with power constraint
– Saddlepoint theorem

– Parallel Gaussian channels
– Water-filling solution
– Hamming distance, minimum distance of a code

HW 9

Coding notes

– Sphere-packing bound
– Hamming code (example of a perfect code)
– Singleton bound​​​
– Gilbert bound

– Proof of Gilbert-Varshamov bound
– Linear codes
– Reminder: fields, vector spaces over fields
– Generator and parity-check matrices
– Linear codes achieve BSC capacity

HW 10

– Reed-Solomon codes

– Polar codes
– Construction of synthetic channels
– BEC example

HW 11

Graded HW

– Complexity of encoding and decoding
– ε-good and ε-bad channels
– First attempt at error probability

– ε-noble and ε-lucky channels
– Refined (successful) attempt at error probability
– Rate-distortion setup
– Bad news (converse) theorem

HW 12

– Good news theorem and proof
– Rate-distortion function
– Example: Binary, Hamming distance

– Back to Multiple-Access Channel (first introduced on 7/11/2023)
– Convex hull for good news theorem
– Bad news theorem and proof

HW 13

Graded HW Soln

– Completing proof of converse (convex hull)
– Maximal vs. average error probability criterion
– Unsolved problems: Broadcast channel, Interference channel
– Secrecy (solved)

Final Exam

Final

Solutions