The Minimum Average Code for Finite Memoryless Monotone Sources

Mohammadali Khosravifard, Hossein Saidi, Morteza Esmaeili, T. Aaron Gulliver

IEEE Transactions on Information Theory · 2007 · 22 citations · 25 references

Concepts

Abstract

The problem of selecting a code for finite monotone sources with N symbols is considered. The selection criterion is based on minimizing the average redundancy (called Minave criterion) instead of its maximum (i.e., Minimax criterion). The average probability distribution P <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Nmacr</sup> , whose associated Huffman code has the minimum average redundancy, is derived. The entropy of the average distribution (i.e., H(P <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Nmacr</sup> )) and the average entropy of the monotone distributions (i.e., H(P <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Nmacr</sup> )) are studied. It is shown that both logN-H(P <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Nmacr</sup> ) and logN-H(P <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Nmacr</sup> ) are asymptotically equal to a constant (sime0.61). Therefore, there is only a negligible penalty (at most 1.61 bits/symbol) in using a simple fixed-length code with respect to the optimal code. An efficient near-optimal encoding technique is also proposed. The consequences of the two approaches, i.e., Minave and Minimax, are compared in terms of their associated distributions and associated codes. In order to evaluate the average performance of the Minimax code, we prove that the informational divergence of the average distribution and Minimax distribution asymptotically grows as -2.275+loglogN

References

25