= Shannon-Fano-Elias code
{c}
{title2=$l_k=\lceil-\log_2p_k\rceil+1$}
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_2p_k+2$, averaging proves $\mathbb EL<H(X)+2$. This is a direct cumulative construction and does not require sorting the <probabilities> or constructing a Huffman tree.
Back to article page
