= Optimal one-to-one binary code
Suppose one source message is transmitted with its endpoint supplied externally, and allow the <empty word>. List source symbols in decreasing order of <probability>, $p_1\geq p_2\geq\cdots$, and assign distinct binary words in increasing length order. Then the $i$th word has length $\lfloor\log_2i\rfloor$, minimizing <expected codeword length> among <one-to-one source codes>.<Information Theory: From Coding to Learning, October 2022 draft by Yury Polyanskiy and others>[Section 10.1, Theorem 10.2, printed pp. 163–164]{ref}
There are $1+2+\cdots+2^\ell=2^{\ell+1}-1$ binary words of length at most $\ell$. This proves the length formula. If a more probable symbol had a longer word than a less probable one, exchanging the two would decrease or preserve the <expected value> of the length, proving optimality.
For <probabilities> $(1/2,1/4,1/4)$, use the <empty word>, `0` and `1`. The average is $1/2$ <bit>, compared with $3/2$ <bits> for an optimal binary <prefix code>. The difference uses the supplied endpoint: the three-word assignment cannot decode an arbitrary concatenated message stream without framing information.
Back to article page
