Source coding theorem

The source coding theorem, also known as Shannon's first theorem, establishes the fundamental limit of lossless compression for a given information source. It states that the expected length of any lossless compression scheme for a source with Shannon entropy H is bounded below by H — and that there exist codes that approach this bound arbitrarily closely. This theorem transforms entropy from a measure of uncertainty into an operational limit: H is not merely descriptive; it is the minimal resource cost of representation.

The theorem's practical realization came through Huffman coding and arithmetic coding, both of which produce codes whose expected length converges to the entropy for sufficiently long messages. However, the theorem assumes a known, stationary source distribution — an assumption that rarely holds in real-world data, where distributions drift, context matters, and the true model is unknown. The source coding theorem is a boundary, not a recipe.

Epistemic Dimensions of Compression

The source coding theorem is rarely read as an epistemic claim, but it is one. When Shannon proved that entropy is the lower bound on lossless compression, he established not merely a physical limit but an epistemic one: the minimal cost of preserving a signal is determined by the signal's uncertainty. What the theorem does not address — and what contemporary information science must — is who decides which signals are worth preserving, which distributions are assumed stationary, and which codes are made available.

Compression is never neutral. A lossless compression scheme for English text assumes the statistical structure of English — its letter frequencies, its word patterns, its syntactic regularities. A compression scheme for scientific data assumes that the noise is separable from the signal, that the relevant structure is captured by the chosen representation, and that future researchers will not need the discarded information. These assumptions are epistemic commitments disguised as engineering choices. The JPEG compression standard, for example, discards high-frequency information that the human visual system is less sensitive to — a biologically informed choice that shapes how digital images represent reality.

In machine learning, the epistemic dimensions of compression are even more consequential. Model compression — quantization, pruning, distillation — reduces the size of neural networks by discarding parameters deemed less important. But importance is defined by the training objective, and the training objective is not identical to epistemic quality. A compressed model may retain the parameters that optimize for accuracy while discarding parameters that encode rare but critical patterns. The source coding theorem tells us that compression is bounded by entropy; it does not tell us whether the entropy we measure is the entropy of the world or the entropy of our measurement.

The epistemic infrastructure of science depends on compression at every level: data compression in storage, model compression in deployment, citation compression in literature reviews. Each compression step is a decision about what matters, and each decision is made by agents with interests, constraints, and blind spots. The source coding theorem is the mathematical foundation of this infrastructure, but it cannot tell us whether the infrastructure is just. For that, we need epistemic infrastructure theory — the study of how the architectures of knowledge production shape what knowledge is produced.

The source coding theorem tells us what compression is possible. It does not tell us what compression is desirable. The gap between the possible and the desirable is where politics lives — and where mathematics, however elegant, cannot save us from the consequences of our own designs.