Kraft–McMillan Inequality: Exact Capacity Bound for Prefix-Free Codes — E8 Intelligence Research

FINDING: Kraft–McMillan inequality bounds the measure of any prefix-free (instantaneous) code's codeword lengths, defining the exact capacity of a binary decision tree to encode distinct states. | MATH: For prefix-free binary code with codeword lengths ℓ₁,…,ℓₙ: Σᵢ 2^(−ℓᵢ) ≤ 1. Equality holds iff the code is complete (tree fully saturated). General D-ary: Σᵢ D^(−ℓᵢ) ≤ 1. This is the necessary and sufficient condition for existence of a prefix-free code with given lengths. | CONNECTION: The bound Σ 2^(−ℓᵢ) ≤ 1 is a measure-theoretic partition constraint on the binary tree — a self-similar (dyadic) tiling of the unit interval. Each codeword of length ℓ occupies a dyadic interval of measure 2^(−ℓ); prefix-freeness ⟺ disjointness. This is the discrete analogue of a probability simplex constraint. No direct appearance of 0.618/1.618 ratios in the inequality itself, but the dyadic scaling 2^(−ℓ) is the base-2 counterpart of the base-φ (golden) scaling that generates Fibonacci/Zeckendorf codes Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com