= Solution
First, the binary translation of a quaternary <prefix code> is still a <prefix code>: every translated <codeword length> is even, and a binary prefix relation would split into complete two-<bit> blocks, giving a prefix relation between the original quaternary <codewords>. Binary <Huffman coding> is optimal among binary <prefix codes>, so
$$
\mathbb E|c_B(X_1)|\leq\mathbb E|c_{QB}(X_1)|.
$$
For the other direction, let $\ell_i=|c_B(x_i)|$ and round these binary <codeword lengths> to quaternary lengths $k_i=\lceil\ell_i/2\rceil$. The <Kraft inequality> gives
$$
\sum_i4^{-k_i}=\sum_i2^{-2\lceil\ell_i/2\rceil}
\leq\sum_i2^{-\ell_i}\leq1.
$$
The quaternary converse of the <Kraft inequality> supplies a quaternary <prefix code> with lengths $k_i$. Optimality of the <quaternary Huffman code> then implies
$$
\begin{aligned}
\mathbb E|c_{QB}(X_1)|
&=2\mathbb E|c_Q(X_1)|
\leq2\sum_i p_i\left\lceil\frac{\ell_i}2\right\rceil\\
&\leq\sum_i p_i(\ell_i+1)
=\mathbb E|c_B(X_1)|+1.
\end{aligned}
$$
Thus \b[binary translation of an optimal quaternary code costs at most one extra bit per source symbol]:
$$
\boxed{\mathbb E|c_B(X_1)|\leq\mathbb E|c_{QB}(X_1)|\leq\mathbb E|c_B(X_1)|+1.}
$$
The <quaternary Huffman code> uses the usual adjustment of adding zero-weight dummy leaves when needed. If the <alphabet> has one symbol, both optimal codes may use the empty <codeword>, giving the trivial endpoint.
Back to article page
