Huffman code efficiencies for extensions of sources

Abstract

The efficiency of noiseless coding may be improved by coding extensions of the source; for large extensions the efficiency is arbitrarily close to unity. The paper shows that the efficiency is not always improved just by coding the next extension. In some cases the code of a larger extension is markedly less efficient than its predecessor, although always within the theoretical limits of efficiency. The author shows how the phenomenon arises from changes to the Huffman coding tree as the source probabilities change and investigates it for binary and ternary codes.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>