Chapter 5: Lossless Source Coding

Learning Objectives

• Understand prefix codes, Kraft's inequality, and the binary tree interpretation
• Prove that entropy is the fundamental limit for lossless compression
• Construct optimal codes via Huffman's algorithm and prove their optimality
• Explain arithmetic coding and why it supersedes Huffman in practice
• Analyze Lempel-Ziv compression and prove its universality for stationary ergodic sources
• Compute entropy rates for Markov sources and design codes exploiting memory