Source Coding Theorem

Shannon's source coding theorem sets entropy as the hard floor on lossless compression.

The statement

For a source with entropy H bits per symbol, no lossless code can achieve an average length below H bits per symbol, and codes exist that approach H arbitrarily closely by encoding long blocks.

Why entropy is the limit

Kronos motion — number counters

Entropy is the true average information per symbol. A code shorter than that would, on average, fail to distinguish all the outcomes it must, so some inputs could not be recovered. Losslessness forces the floor.

Approaching the bound

Coding symbols one at a time, an optimal prefix code lands within one bit of entropy. Coding blocks of many symbols together drives the average per-symbol length down toward entropy, since the fixed overhead is amortized.

Practical codes

Huffman coding is optimal among per-symbol prefix codes. Arithmetic and range coding get closer to entropy by not rounding each symbol to a whole number of bits, encoding a whole message as one fraction.

What it does not promise

The theorem assumes an accurate probability model of the source. Real compressors also model context and correlations; the better the model predicts the data, the lower the effective entropy and the smaller the output.

python

import math
def entropy(ps):
    return -sum(p*math.log2(p) for p in ps if p>0)
# Lower bound on avg bits/symbol for this distribution
print(entropy([0.5,0.25,0.125,0.125]))  # 1.75