This paper presents lossless prefix codes optimized with respect to a payoff criterion consisting of a convex combination of maximum codeword length and average codeword length. The optimal codeword lengths obtained are based on a new coding algorithm, which transforms the initial source probability vector into a new probability vector according to a merging rule. The coding algorithm is equivalent to a partition of the source alphabet into disjoint sets on which a new transformed probability vector is defined as a function of the initial source probability vector and scalar parameter. The payoff criterion considered encompasses a tradeoff between maximum and average codeword length; it is related to a payoff criterion consisting of a convex combination of average codeword length and average of an exponential function of the codeword length, and to an average codeword length payoff criterion subject to a limited length constraint. A special case of the first related payoff is connected to coding problems involving source probability uncertainty and codeword overflow probability, whereas the second related payoff compliments limited length Huffman coding algorithms.

This paper presents prefix codes which minimize various criteria constructed as a convex combination of maximum codeword length and average codeword length, or, a convex combination of the average of an exponential function of the codeword length and the average codeword length. This framework encompasses as a special case several criteria previously investigated in the literature, while relations to universal coding is discussed. The coding algorithm derived is parametric resulting in re-adjusting the initial source probabilities via a weighted probability vector according to a merging rule. An algorithm is presented to compute the weighting vector.

This paper is concerned with designing minimum average length uniquely decodable codes, for a family of source distributions for which the relative entropy with respect to a given nominal distribution is bounded above by some fixed number. This formulation leads to a minimax source coding problem, in which the minimizing players are the codeword lengths, while the maximizing players are the uncertain source distributions. It is further shown, via a large deviations duality relation, that the minimax source coding problem is equivalent to a coding problem which minimizes the average of an exponential pay-off instead of the conventional average length pay-off. Both Shannon coding and Huffman coding methods are generalized to this new criterion of performance, leading to robust codes which perform well with respect to an uncountable family of source distributions. However, the code lengths are designed with respect to a known nominal distribution, which is obtained either through modeling assumptions or via empirical techniques. Simulations are also presented comparing the Shannon/Huffman codes with the robust codes, when the source distribution is uncertain, while a sensitivity analysis shows that the new codes are much less sensitive to the uncertainty description. In addition, a fixed length source coding theorem is derived in which the encoding error tends to zero as the length of the codes tends to infinity, uniformly over the set of uncertain distributions which satisfy the relative entropy bound. Finally, generalizations to uncertainty described by the total variation norm is discussed.