gen-define-the-source-coding-theorem-and-give-one-short-worked-e-b3d9

Define the source coding theorem and give one short worked example.

# Source Coding Theorem ## Definition The **Source Coding Theorem** (Shannon's First Theorem) states that for a discrete memoryless source with entropy H(X), it is possible to encode the source with an average code length arbitrarily close to H(X) bits per symbol, but no lossless encoding scheme can achieve an average length less than H(X). Mathematically: - **H(X) ≤ L̄ < H(X) + 1** (for fixed-length encoding of single symbols) - **L̄ → H(X)** as block length n → ∞ where L̄ is the average codeword length per source symbol. ## Worked Example **Problem:** A source emits three symbols with probabilities: - P(A) = 1/2 - P(B) = 1/4 - P(C) = 1/4 Find the entropy and verify the source coding theorem using Huffman coding. **Solution:** **Step 1:** Calculate entropy H(X) ``` H(X) = -∑ P(x) log₂ P(x) = -(1/2)log₂(1/2) - (1/4)log₂(1/4) - (1/4)log₂(1/4) = (1/2)(1) + (1/4)(2) + (1/4)(2) = 1/2 + 1/2 + 1/2 = 1.5 bits/symbol ``` **Step 2:** Construct Huffman code - A: 0 (length 1) - B: 10 (length 2) - C: 11 (length 2) **Step 3:** Calculate average code length ``` L̄ = (1/2)(1) + (1/4)(2) + (1/4)(2) = 1.5 bits/symbol ``` **Conclusion:** L̄ = H(X) = 1.5 bits/symbol ✓ The theorem is satisfied: L̄ = 1.5 ≥ H(X) = 1.5