Characterizations of Minimal Expected Length Codes

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.