Binary translation of a quaternary prefix code ($L_2^{\ast }\le 2L_4^{\ast }\le L_2^{\ast }+1$)

Replacing every quaternary digit by its fixed two-bit representation preserves the prefix code property: a binary prefix between translated codewords would end at an even position and hence imply a quaternary prefix. Thus a translated quaternary Huffman code cannot beat binary Huffman coding in expected codeword length.

For the reverse bound, binary prefix code lengths ${\ell }_i$ give candidate quaternary lengths $k_i=\lceil {\ell }_i/2\rceil$. Since ${\sum }_i{4}^{-k_i}\le {\sum }_i{2}^{-{\ell }_i}\le 1$, the Kraft inequality supplies such a quaternary prefix code. Optimality of quaternary Huffman coding and $2\lceil {\ell }_i/2\rceil \le {\ell }_i+1$ give $2L_4^{\ast }\le L_2^{\ast }+1$. These quantities are expected codeword lengths for the same source probability distribution.