IEEE Transactions on Information Theory · 2007 · 22 citations · 25 references
Natural SciencesComputer ScienceMathematicsInformation TheoryOptimizationProbability TheoryCoding TheoryEntropyError-correcting CodesSource CodingEncoding AlgorithmsEntropy CodingEntropy In Coding TheoryHuffman CodingMinimax Optimization
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
25