Source Coding

Source vs Channel

• Source Coding: REMOVE redundancy (Compress)
• Channel Coding: ADD controlled redundancy (Protect)
• Fundamental dichotomy of information theory
• Compression saves bandwidth and storage

Self-Information

• I(x) = -log₂ P(x)
• Information = "Unexpectedness" or Surprise
• Rare event (low P) → High information
• Common event (high P) → Low information

Shannon Entropy

• H(X) = -Σ p(x) log₂ p(x)
• Average information content per source symbol
• Measured in bits/symbol
• Binary source hits maximum entropy at P = 0.5

Redundancy

• Maximum possible entropy: H_max = log₂ M
• If H < log₂ M, the source is redundant
• Redundancy (R) = 1 - H/log₂ M
• Goal: Remove redundancy to lower average code length

Variable-Length Coding

• Fixed-length codes waste space on rare symbols
• Variable-length: Common symbols get shorter codes
• Exploits statistical structure for compression
• Requires unambiguous decoding rules

Prefix Codes & Kraft

• Prefix Code: No codeword is a prefix of another
• Guarantees "Instantaneous Decodability"
• Kraft Inequality dictates if a prefix code can exist
• Σ 2^(-l_i) ≤ 1 for binary codes

Huffman Algorithm

• Bottom-up construction of an optimal prefix tree
• Repeatedly combine the two least-probable nodes
• Leaves are symbols; paths are 0/1 codewords
• Optimal average length under standard assumptions

Shannon-Fano Coding

• Top-down partitioning algorithm
• Sort symbols by probability, split into equal halves
• Assign 0 to one group, 1 to the other
• Not strictly guaranteed to be as optimal as Huffman

Arithmetic Coding

• Represents entire message as an interval [0, 1)
• Each symbol dynamically subdivides the interval
• Final floating-point number identifies the sequence
• Can achieve fractional bit lengths (closer to H)

Dictionary Coding (LZ)

• Lempel-Ziv family (LZ77, LZ78, LZW)
• Builds a dictionary of repeated patterns
• Replaces repeated sequences with backward references
• Universal source coding (adapts without prior model)

Run-Length Encoding

• Represent repeated consecutive symbols simply
• "AAAAAAABBB" becomes "7A 3B"
• Excellent for files with long identical sequences
• Can expand file size if data is highly alternating

Predictive Coding

• Predict next value based on previous context
• Encode only the ERROR (Actual - Predicted)
• Residual errors have much lower variance/entropy
• Foundation of Delta/Differential coding and Video

Entropy Rate & Memory

• Conditional Entropy H(X|Y): Remaining uncertainty
• Mutual Information I(X;Y): Shared knowledge
• Predictability = Lower Conditional Uncertainty
• Memory reduces the asymptotic Entropy Rate

Lossless vs Lossy

• Lossless: Exact original recovered (Text, Software)
• Lossy: Approximation, discarding perceptual redundancy
• Rate-Distortion Theory: Lower Rate ↔ More Distortion
• Lossy achieves vastly higher compression (Audio, Video)

Source Coding Theorem

• Asymptotic Equipartition Property (AEP)
• Most probability mass lies in "Typical Sequences"
• Average code length cannot drop below source entropy
• H(X) ≤ L_avg < H(X)+1 (for optimal binary codes)

16 — The Compression Laboratory

By understanding the statistical predictability of the source, we have stripped away all wasted space. The data is now a highly dense, hyper-efficient stream of pure information. But this creates a new, terrifying problem: Because every bit now carries maximum meaning, a single error caused by channel noise will destroy the message. We must now selectively put redundancy back in. You are prepared for Realm 12: Channel Coding.