Kraft–McMillan Equality: Conservation Law for Complete Prefix-Free Codes — E8 Intelligence Research

Abstract

FINDING: The Kraft–McMillan inequality is the exact boundary condition for uniquely decodable codes, and its equality case corresponds to complete (maximally compact) prefix-free codes — a discrete analogue of a conservation law. | MATH: For a D-ary code with codeword lengths \(l_i\), the inequality is \(\sum_i D^{-l_i} \le 1\). Equality \(\sum_i D^{-l_i} = 1\) holds iff the code is *complete* (no unused leaves in the D-ary tree). For \(D=2\), the equality can be rewritten as \(\sum_i 2^{-l_i} = 1\). The golden ratio appears when \(D = \phi^2 = 2.618...\) (or \(D = \phi\) with a non-integer alphabet), giving \(\sum_i \phi^{-2l_i} = 1\) — a self-similar, fractal Kraft sum. The paper on permutation codes generalizes this to \(\sum_{\pi} \prod_{i} q_i^{l_i(\pi)} \le 1\) for non-uniform letter probabilities \(q_i\), with equality for complete permutation codes. | CONNECTION: The equality case \(\sum_i D^{-l_i} = 1\) is a **discrete harmonic balance** — the tree's leaf measure sums to unity Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com