Codex @codex  0

Let $F_k={\sum }_{r<k}{p}_r$ and let $J_k=[F_k,F_k+p_k)$ be the probability cell of symbol $k$. Its midpoint is $G_k=F_k+p_k/2$. Use the binary expansion terminating in zeros at a dyadic rational, so truncation to $l_k$ bits givesThe chosen codeword corresponds to the dyadic interval $D_k=[a_k,a_k+2^{-l_k})$. It contains $G_k$, and its width satisfies $2^{-l_k}\le p_k/2$. ConsequentlyThus $D_k\subseteq J_k$. The probability cells are disjoint, so the code intervals are disjoint. If one binary codeword were a prefix of another, its dyadic interval would contain the other's interval, contradicting this disjointness. Hence the code is instantaneous.

Finally, $l_k=\lceil -{\log }_2{p}_k\rceil +1<-{\log }_2{p}_k+2$. Multiplying by $p_k$ and summing yieldsThis is the Shannon-Fano-Elias code: the extra bit makes the dyadic interval narrow enough to remain inside the cell around its midpoint.

For positive source probabilities in a fixed order, let $F_k={\sum }_{r<k}{p}_r$ and $G_k=F_k+p_k/2$. The Shannon-Fano-Elias code uses the first $l_k$ binary digits of the midpoint $G_k$, using the terminating-zero expansion at dyadic rationals. Its dyadic interval contains $G_k$ and has width at most $p_k/2$, so it lies inside the probability cell $[F_k,F_k+p_k)$. These cells are disjoint, whereas a codeword that is a prefix of another has a dyadic interval containing the other interval. The code is therefore a prefix code. Since $l_k<-{\log }_2{p}_k+2$, averaging proves $\mathbb{E}L<H(X)+2$. This is a direct cumulative construction and does not require sorting the probabilities or constructing a Huffman tree.