= Binary translation of a quaternary prefix code
{title2=$L_2^*\leq2L_4^*\leq L_2^*+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_i4^{-k_i}\leq\sum_i2^{-\ell_i}\leq1$, the <Kraft inequality> supplies such a quaternary <prefix code>. Optimality of <quaternary Huffman coding> and $2\lceil\ell_i/2\rceil\leq\ell_i+1$ give $2L_4^*\leq L_2^*+1$. These quantities are <expected codeword lengths> for the same source <probability distribution>.
Back to article page
