Past exam of the information theory course of the University of Oxford / 2023 / 2 / d / 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, soFor 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 givesThe quaternary converse of the Kraft inequality supplies a quaternary prefix code with lengths $k_i$. Optimality of the quaternary Huffman code then impliesThus binary translation of an optimal quaternary code costs at most one extra bit per source symbol: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.