Redundancy-Related Bounds for Generalized Huffman Codes
Michael B. Baer · IEEE Transactions on Information Theory · 2011
This paper presents new lower and upper bounds for the compression rate of binary prefix codes optimized over memoryless sources according to various nonlinear codeword length objectives. Like the most well-known redundancy bounds for minimum average redundancy coding-Huffman coding-these are in terms of a form of entropy and/or the probability of an input symbol, often the most probable one. The bounds here, some of which are tight, improve on known bounds of the formL∈ [H,H+1), whereHis some form of entropy in bits (or, in the case of redundancy objectives, 0) andLis the length objective, also in bits. The objectives explored here include exponential-average length, maximum pointwise redundancy, and exponential-average pointwise redundancy (also calleddthexponential redundancy). The first of these relates to various problems involving queueing, uncertainty, and lossless communications; the second relates to problems involving Shannon coding and universal modeling. Also explored here for these two objectives is the related matter of individual codeword length.