Source Coding for Quasiarithmetic Penalties
Author:
- 25 September 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 52 (10) , 4380-4393
Abstract
Whereas Huffman coding finds a prefix code minimizing mean codeword length for a given finite-item probability distribution, quasiarithmetic or quasilinear coding problems have the goal of minimizing a generalized mean of the form rho-1(Sigmaipirho(li )), where li denotes the length of the ith codeword, p i denotes the corresponding probability, and rho is a monotonically increasing cost function. Such problems, proposed by Campbell, have a number of diverse applications. Several cost functions are shown here to yield quasiarithmetic problems with simple redundancy bounds in terms of a generalized entropy. A related property, also shown here, involves the existence of optimal codes: For "well-behaved" cost functions, optimal codes always exist for (possibly infinite-alphabet) sources having finite generalized entropy. An algorithm is introduced for finding binary codes optimal for convex cost functions. This algorithm, which can be extended to other minimization utilities, can be performed using quadratic time and linear space. This reduces the computational complexity of a problem involving minimum delay in a queue, allows combinations of previously considered problems to be optimized, and greatly expands the set of problems solvable in quadratic time and linear spaceKeywords
All Related Versions
This publication has 30 references indexed in Scilit:
- On the cost of worst case coding length constraintsIEEE Transactions on Information Theory, 2001
- Elements of Information Theory2001
- Maximal codeword lengths in Huffman codesComputers & Mathematics with Applications, 2000
- A flexible algorithm for construction of 3-D vessel networks for use in thermal modelingIEEE Transactions on Biomedical Engineering, 1998
- A Fast Algorithm For Optimum Height-Limited Alphabetic Binary TreesSIAM Journal on Computing, 1994
- On the maximum length of Huffman codesInformation Processing Letters, 1993
- On the redundancy of optimal codes with limited word lengthIEEE Transactions on Information Theory, 1992
- The Renyi redundancy of generalized Huffman codesIEEE Transactions on Information Theory, 1988
- A Short Note on the Redundancy of Degree αInformation Sciences, 1986
- Binary Trees Optimum Under Various CriteriaSIAM Journal on Applied Mathematics, 1979