Kraft–McMillan code-length bound

Necessary and sufficient length inequality for a binary prefix code.

Specification version 1Published 2006-07-181 evidence records

About this problem

The question, scope, and sources behind this Registry record.

Formal question

Characterize integer codeword lengths realizable by a binary prefix code.

Scope & constraints

code: binary prefix
lengths: positive integers
alphabetSize: 2

Primary sources

Elements of Information Theory, second edition — Kraft–McMillan code-length bound Chapters 2, 5, 7, 10, 13 and 15

What we know

Current frontiers derived from accepted Claims.

KNOWN LOWER BOUNDKNOWN UPPER BOUND

Unknown

OPEN FRONTIER

sum_i 2^(-l_i) <= 1

Lower boundGap: UnknownUpper bound

Claims

Assertions tied to evidence, attribution, and review.

2026

CLM-INFO-003209<= sum_i 2^(-l_i) <= 1UPPER BOUNDThe cited theorem establishes sum_i 2^(-l_i) <= 1 under the current specification; this does not assert universal empirical attainability.Source: Elements of Information Theory, second edition — Kraft–McMillan code-length bound ↗

PROVEN

Timeline

The frontier as it changed over time.

How this frontier is derived

Only accepted Claims matching the current specification contribute to the displayed bounds. Strict inequalities remain open; contradictory Claims require editorial review.

—No breakthrough events recorded yetEvents appear here when an accepted Claim tightens a bound or closes the frontier.