= Solution
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> gives
$$
a_k=2^{-l_k}\lfloor2^{l_k}G_k\rfloor.
$$
The 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}\leq p_k/2$. Consequently
$$
a_k>G_k-2^{-l_k}\geq F_k,\qquad a_k+2^{-l_k}\leq G_k+2^{-l_k}\leq F_k+p_k.
$$
Thus $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_2p_k\rceil+1<-\log_2p_k+2$. Multiplying by $p_k$ and summing yields
$$
\boxed{\mathbb EL<H(X)+2.}
$$
This is the <Shannon-Fano-Elias code>: the extra <bit> makes the <dyadic interval> narrow enough to remain inside the cell around its <midpoint>.
\Image[/past-exam-of-the-communication-theory-course-of-the-university-of-oxford/2011-midpoint-prefix-code.png]
{title=Midpoint coding places disjoint dyadic intervals inside probability cells}
{description=An original example with probabilities two fifths, three tenths, one fifth, and one tenth. Each orange dyadic code interval contains its black midpoint and lies inside its blue probability cell, proving that the displayed codewords cannot be prefixes of one another.}
Back to article page
