Introduction

In the rate distortion theory a rate-distortion function $R(D)$ is the infimum of rates $R$ such that $(R,D)$, a rate distortion pair, is in the closure of the set of achievable rate pairs of the source for a given distortion $D$, [1]:

$$R(D) = \min_{p(\hat{x}\vert x) \ : \ \sum_{(x,\hat{x})} p (x) p(\hat{x}\vert x) d(x,\hat{x}) \leq D} I (X, \hat{X})$$ (1)

where $X$ is the source sequence and the decoder represents $X$ by an estimate $\hat{X}$; the distortion $d(x,\hat{x})$ is a measure of the cost of representing the source $x$ by an estimate $\hat{x}$ and $I (X, \hat{X})$ denotes the mutual information between $X$ and $\hat{X}$. The minimization is over all conditional distributions $p(\hat{x}\vert x)$ for which the joint distribution $p(x,\hat{x}) = p (x) p(\hat{x}\vert x)$ satisfies the expected distortion constraint.

Bit allocation is a major concern in any coding scheme where a given quota of bits must be efficiently distributed among a number of different quantizers. Then, in the traditional analysis of the Rate Distortion theory, a bit rate allocation problem among competing quantizers is optimally solved for a given bit budget if the marginal change in distortion is the same for all quantizers, [2]. In this ``marginal analysis'' for bit allocation the concept of rate distortion function is unnecessarily restrictive. It, in a sense, presupposes the existence of a ``managerial choice'' so that from the beginning it is specified what quantizer-based allocations in the transmission problem should be first adopted to achieve some distortion constraint at the minimum bit rate (going beyond the discarding of unwanted quantizer-based allocation processes). The rate distortion function so obtained is descriptive of reality only if and when the assumption of managerial choice is a good approximation to reality.

In this paper we propose a new theory of bit allocation, the ``bit-allocation analysis'', capable of efficiently allocating a given quota of bits to an arbitrary set of different quantizers. The bit-allocation analysis discards the above concept of rate distortion function. Instead it postulates the set of bit allocation processes attainable in a given problem of quantizer based coding and then the relations of bit consumption and quantizer-based allocations are treated formally. The most important concept in this analysis is ``efficient allocation process'' such that no desired allocation for a particular quantizer can be increased without decreasing other desired quantizer allocation or increasing bit consumption. Application of the criterion of efficiency thus servers only to eliminate a set of clearly wasteful modes of quantizer-based allocation.

The modus operandi of bit-allocation analysis is to be through the use of set theory and the fundamental theorems of mathematical optimization. They play an important role in bit-allocation analysis just as derivatives and marginal analysis played an important role in the rate distortion theory proposed by Shannon in 1948. Based on the existence of a hyperplane that separates two disjoint convex sets, this paper characterizes the concept of efficient allocation process by profit maximization. That is, the maximization of $p \cdot y$ with respect to $y$ over the set of allocation processes; where $p$ is a profit vector and $p \cdot y$ represents the profit from $y$. The algorithmic solution is based on the simplex method. Then we can use the imputed profit vector $p$ at any given time in order to make a choice from the set of efficient allocations. It allows to achieve efficient allocations which may be descriptive of reality at any given time, since the profit vector $p$ can change its value over time and a user of the system may choose the appropriate strategy.

It is important to realize the basic features of the traditional rate distortion function approach in terms of the novel bit-allocation analysis terminology: (i) It deals with a set of allocation processes which cannot be generated from a finite number of basic allocations processes, rather a continuum of vectors is required to characterize the set of allocation processes in rate-distortion (ii) the existence of a ``managerial choice'' is presupposed so that the combination of allocation-consumption processes always takes place to achieve some distortion constraint at the minimum bit rate which is nothing but the set of efficient allocations defined by the rate distortion function; and (iii) the set of efficient allocations in rate-distortion constitutes a differentiable function. Instead, in the following sections, the bit allocation analysis is confined to a study of processes when the number of basic allocation processes is finite. In other words, the set of allocation processes is to be confined to a ``truncated'' convex polyhedral cone. However the innovative character of bit allocation analysis is not in a particular shape of the set of allocation processes. It is in the set-theoretic approach which is more fundamental and powerful than the smooth (differentiable) function approach.

In Section II of this paper we introduce the theory of bit allocation analysis. Section III demonstrates the practical and computational significance of the bit allocation analysis. An example of application of bit allocation analysis for progressive transmission of moving targets at very low bit rates is outlined in Section IV. Results of a perception experiment of target detection using decoded sequences are reported in Section V. The main conclusions of the paper are summarized in Section VI.