[IEEE Trans. on Information Theory, submitted November 13, 2023]
Characterizations of Minimal Expected Length Codes
Spencer Congero and Kenneth Zeger
Abstract
A property of prefix codes called strong monotonicity is introduced.
Then it is proven that for a prefix code C for a given probability distribution,
the following are equivalent:
(i) C is expected length minimal;
(ii) C is length equivalent to a Huffman code; and
(iii) C is complete and strongly monotone.
Also, three relations are introduced between prefix code trees
called same-parent, same-row, and same-probability swap equivalence,
and it is shown that for a given source,
all Huffman codes are same-parent, same-probability swap equivalent,
and all expected length minimal prefix codes
are same-row, same-probability swap equivalent.