On the Structure of the Minimum Average Redundancy Code for Monotone Sources

Abstract—The source coding problem is considered where the only information known about the source is the number of symbols n and the order of the symbol probabilities. In this case, the code which achieves the minimum average redundancy is known as the M code. It is the Huffman code for the average distribution of monotone sources, and thus is a fixed code which does not depend on the symbol probabilities. The M code is a near-optimal code not only in the sense of average redundancy, but also in terms of the redundancy for almost all monotone sources. No simple expression is known for the codeword lengths of the M code for a given alphabet size. In this letter, the structure of this code is investigated, and an estimate is given for the number of codewords of a given length. In particular, the number of codewords of length j + 1 for encoding 2n symbols is shown to be almost twice the number of codewords of length j for encoding n symbols.
Index Terms—Average redundancy, monotone sources,M code, Kraft sum, multiplicity of codelengths.