One-to-one source code

A one-to-one source code is an injective function from source symbols to finite codewords. Unlike a prefix code, it need not permit instantaneous decoding of concatenated codewords.

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\ge p_2\ge \cdots$, and assign distinct binary words in increasing length order. Then the $i$th word has length $\lfloor {\log }_{2}i\rfloor$, minimizing expected codeword length among one-to-one source codes.^[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.