Source Coding Theorem

The Source Coding Theorem, also called Shannon's First Theorem, establishes a fundamental limit on how efficiently a discrete information source can be compressed. It tells us exactly how many bits per symbol are required at minimum to represent a source without losing information. This theorem is the theoretical foundation for all lossless compression methods used in engineering practice.

Core Concept Explanation

A discrete memoryless source (DMS) generates one symbol at a time from a finite alphabet {s1, s2, ..., sM} with fixed probabilities {p1, p2, ..., pM}, and each output is independent of previous outputs. The source entropy H(S) = -sum pi log2(pi) bits/symbol tells us how much information, on average, each symbol carries. Shannon's First Theorem says this entropy is the absolute minimum average number of bits needed per symbol to represent the source output losslessly.

The theorem has two parts. The converse part says that any lossless code must have average length L >= H(S). You cannot compress below entropy without making errors. The achievability part says that codes exist that come arbitrarily close to H(S). Specifically, for a single symbol code, the best achievable average length satisfies H(S) <= L < H(S) + 1. The gap of up to 1 bit per symbol arises because codeword lengths must be integers.

This 1-bit gap can be reduced by encoding blocks of n symbols together instead of encoding one symbol at a time. The block approach gives H(S) <= L_n/n < H(S) + 1/n, where L_n is the average codeword length for a block of n symbols. As n grows large, 1/n becomes negligible and the per-symbol average rate approaches H(S) exactly. This is why practical systems often use block encoding for better compression efficiency.

Mathematical Expression

The entropy rate of a DMS is simply H(S) since symbols are independent. For a source with memory, the entropy rate is defined as H_inf = lim_{n->inf} H(S1, S2, ..., Sn) / n, where the numerator is the joint entropy of n consecutive symbols. For a stationary source, this limit exists and represents the irreducible bits per symbol needed.

The coding efficiency of a code is defined as eta = H(S) / L, expressed as a fraction or percentage. A perfectly efficient code would have eta = 1 (100%), which is theoretically achievable only in the limit of infinite block length. For practical codes, eta is close to but slightly below 1. The redundancy is defined as 1 - eta = (L - H(S)) / L, representing the fractional waste in bits per symbol.

The theorem also connects to the Kraft inequality, which states that a uniquely decodable prefix-free code over a binary alphabet must satisfy sum 2^{-li} <= 1, where li are the codeword lengths. Any set of lengths satisfying the Kraft inequality can be realized as a prefix-free code. The source coding theorem guarantees that an optimal assignment of lengths exists that achieves average length close to H(S).

Practical Understanding

In real communication systems, source coding is the first step in a transmission chain. The source encoder takes raw symbol sequences and outputs compressed binary sequences. The closer the encoder gets to the entropy rate, the fewer bits it sends per unit time, which reduces bandwidth requirements. Any bits beyond H(S) are redundant and represent an opportunity for further compression.

Entropy also sets a practical floor below which compression algorithms cannot go without introducing errors. File formats like PNG, FLAC, and ZIP use lossless compression, meaning they must respect this bound. When you observe that a highly compressed ZIP file cannot be compressed further with another pass, it is because the file's entropy per symbol is already close to the bit rate being used.

Given:
Source alphabet: {A, B, C, D}
Probabilities: p(A) = 0.5, p(B) = 0.25, p(C) = 0.125, p(D) = 0.125

Why this formula applies:
Shannon entropy H(S) = -sum pi log2(pi) gives the minimum average bits per symbol.

Formula:
H(S) = -[p(A) log2 p(A) + p(B) log2 p(B) + p(C) log2 p(C) + p(D) log2 p(D)]

Substitution:
H(S) = -[0.5 * log2(0.5) + 0.25 * log2(0.25) + 0.125 * log2(0.125) + 0.125 * log2(0.125)]
     = -[0.5 * (-1) + 0.25 * (-2) + 0.125 * (-3) + 0.125 * (-3)]
     = -[-0.5 - 0.5 - 0.375 - 0.375]

Calculation:
H(S) = -[-1.75] = 1.75 bits/symbol

Huffman code gives: A=0(1 bit), B=10(2 bits), C=110(3 bits), D=111(3 bits)
Average length L = 0.5*1 + 0.25*2 + 0.125*3 + 0.125*3 = 0.5+0.5+0.375+0.375 = 1.75 bits/symbol

Final Answer: H(S) = L = 1.75 bits/symbol, Efficiency = 1.75/1.75 = 100%
(This source has dyadic probabilities so Huffman achieves exact entropy.)

Exam Tip: When probabilities are powers of 1/2 (dyadic), Huffman coding achieves exactly H(S) with zero redundancy. For non-dyadic probabilities, Huffman gives H(S) <= L < H(S)+1. GATE often asks to verify whether a given code length assignment satisfies the source coding bound.

Entropy Rate and Block Coding

• Entropy H(S) is the theoretical minimum bits/symbol for lossless compression of a DMS. No code can go below this limit without introducing reconstruction errors.
• Single symbol coding gives H(S) <= L < H(S)+1. The maximum gap is just under 1 bit/symbol.
• Block coding of n symbols reduces the gap: H(S) <= L_n/n < H(S) + 1/n. Larger blocks achieve closer-to-optimal performance.
• Coding efficiency eta = H(S)/L. For the dyadic probability case, eta = 1 (perfect efficiency).
• For sources with memory, the entropy rate H_inf = lim H(S1,...,Sn)/n is the compression limit, which is less than or equal to H(S1) for individual symbols.

Quick Revision

• Shannon's Source Coding Theorem: H(S) is the minimum achievable average code length for a DMS. Compression below H(S) is impossible without loss.
• Single symbol bound: H(S) <= L < H(S) + 1. Block coding of n symbols: H(S) <= L_n/n < H(S) + 1/n.
• Entropy formula: H(S) = -sum pi log2(pi) bits/symbol.
• Coding efficiency: eta = H(S)/L. Redundancy = 1 - eta.
• Dyadic probabilities (powers of 1/2) allow Huffman coding to achieve exactly H(S) with 100% efficiency.
• Entropy rate of a source with memory: H_inf = lim H(S1,...,Sn)/n. Always <= H(S1).
• Exam trap: The theorem guarantees the existence of good codes but does not specify a construction method. Huffman and arithmetic coding are practical algorithms that approach this bound.