Cumulative Shannon code

Order source probabilities as $p_1\ge \cdots \ge p_N$, putand take the first $l_i$ binary digits of $b_i$ as the codeword for symbol $i$. Since $b_j-b_i\ge p_i\ge 2^{-l_i}$ for $j>i$, two cumulative probabilities cannot lie in the same dyadic interval selected by the earlier codeword. The resulting code is prefix-free.

If the Shannon length is $l_S(x)=\lceil {\log }_2(1/p_x)\rceil$ and $l_C$ is the length of any binary decipherable code, thenThus the probability that the Shannon code loses to another code by $k$ or more bits decreases exponentially in $k$.