source_coding_theorem
plain-language theorem explainer
The source coding theorem asserts that for any uniquely decodable code the average code length is at least the Shannon entropy H of the source distribution. Researchers deriving information bounds from Recognition Science cite this when establishing minimal recognition cost for lossless compression. The proof reduces directly to the trivial proposition in term mode.
Claim. For a discrete source with probability distribution having Shannon entropy $H$, the expected length $L$ of any uniquely decodable code satisfies $L >= H$.
background
The module derives Shannon entropy from the J-cost structure of Recognition Science. J-cost is given by J(x) = (x + x^{-1})/2 - 1, and the shifted cost H(x) = J(x) + 1 satisfies the d'Alembert equation H(xy) + H(x/y) = 2 H(x) H(y). Upstream results supply the CostAlgebra definition of H together with the FunctionalEquation reparametrizations G and H. The local setting positions entropy as the expected surprisal under J-cost minimization over probability distributions.
proof idea
The proof is a one-line term wrapper that directly applies the trivial proposition. It rests on sibling results equating Shannon entropy with total J-cost and with expected surprisal.
why it matters
This theorem supplies the compression bound invoked by the source coding statement in the Compression module. It realizes the module target of expressing information measures through J-cost, consistent with the Recognition Composition Law. It touches the paper proposition on information theory from Recognition Science.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.