In this paper we study the bit allocation problem under multiple rate constraints. This problem has been arisen in many practical situations, such as optimal image and video quantization, buffer-constrained multimedia transmission, joint source channel coding and unequal error protection. One example is bit allocation for image compression, where the goal is to minimize the total distortion by properly allocating quantization levels for the various blocks with a specified total rate budget constraint. Another example is that buffer constraint is introduced in the bit allocation problem, with one specific situation that a source encoded using variable rate coding is to be transmitted through a constant bit rate channel, and the source bits are buffer prior to transmission. To solve the bit allocation problem under both total rate budget and maximum buffer size constraints, Lagrangian-based iterative technique can be used. Since the bit allocation problems under rate multiple rate constraints are usually equivalent to Knapsack problems, which is NP-hard in general, without having good properties, the optimal solution can not be guaranteed by any polynomial time algorithms.
展开▼