Next: Practical and Computational Significance Up: A Theory of Bit Previous: Introduction

# Bit Allocation Analysis

In this section a theory of quantizer-based allocation will be developed in which the relations of bit consumption and quantizer-based allocations are treated formally and then an analysis using these relations is pursued.

The first element of the bit allocation analysis is the set of allocation processes which represents the attainable relations between quantizer-based allocations and bit consumption (where superscript T'' means transpose):

Definition 1: Set of Allocation Processes. Given m'' competing quantizers , let be the set of attainable combinations of allocation-consumption processes where a process is an ordered (m+1)-tuple which describes a relation of bit allocations among competing quantizers and consumption of bits at a given time:

 (2)

where denotes the bit allocation for quantizer , with ; the bit consumption is represented by a nonpositive value .

The second element of the bit allocation analysis is axiomatic and thus imposes four postulates over the collection of consumption-allocation combinations that are attainable at a given time. These axioms indicate the technological possibilities in the allocation problem and take resource limitations into account.

Axiom 1. There exists a finite set of basic allocation processes, represented by vectors , , such that the set of allocation process can be represented by

 (3)

where for the basic processes are operated at intensity ; for some , , denoting the limitation of use of the resource up to its availability limit.

This means that an allocation process in can be expressed as a nonnegative linear combination of m'' basic processes , with m'' being the number of quantizers :

such that .

Axiom 2. There exists at least one positive element for some attainable combination of allocation-consumption processes in the set of allocation processes .

In other case we have that there is no possibility of bit allocation for some quantizer over in the set of allocation processes.

Axiom 3. Every positive allocation in any attainable combination of allocation-consumption processes produces bit consumption.

It means that, (with bit consumption represented by a nonpositive element of ) implies . Given two vectors and , the notation means that for all , and for at least one . This should be distinguished from the notation which requires only the first of the above conditions, that is, for all .

Axiom 4. Every combination of quantizer-based allocations and the consequent bit consumption at any given time is irreversible.

That is, and imply .

The following definition introduces the most important concept in bit allocation analysis: Efficient allocation process. A combination of quantizer-based allocations and bit consumption is called efficient whenever an increase in one quantizer allocation for some can be achieved only at the cost of a decrease in some other quantizer allocation or increasing bit consumption.

Definition 2: Efficient Allocation Process. Let be a set of allocation processes. A process in is called efficient allocation process of if there does not exists a such that .

The notion expressed by this definition is one of efficiency in converting available bit resources into desired quantizer allocations. Generally, we must expect to find more than one process satisfying this definition. Application of the criterion of efficiency thus serves only to eliminate a set of clearly wasteful modes of bit allocation, leaving us with a set of efficient points from which further choice by other criteria is to be made.

The third element of the bit allocation analysis is a theorem which, following [3], allows to characterize the concept of efficient allocation process'' by maximization of with respect to over , for some vector . An interesting interpretation can be given to vector on an efficient point . We shall call the (m+1)-tuple a profit vector of the quantizer-based allocations in the efficient point :

where denotes the profit per bit for quantizer , with ; and denotes the price per bit for bit consumption. The expression is now interpreted as the profit from allocation process .

Theorem 1: Characterization of Efficient Allocation Process. Let be a convex set of allocation processes. If is an efficient allocation process of then there exists a (m+1)-tuple , such that maximizes the profit from an allocation process, with respect to over .

Proof. Let , then is convex as it is a linear sum of two convex sets, [4].

Also, let be the positive orthant of (m+1)-dimensions (that is, the analogue of a quadrant in the plane, which is defined by a system of inequalities in geometry of (m+1)-dimensions).

Then we have that and are two disjoint nonempty convex sets since . If it is not true, there exists a such that . It follows that and thus is not an efficient allocation of , which is a contradiction.

Hence, following the Minkowski's Theorem, [5], there exists a , , and such that

It asserts the existence of a hyperplane that separates two disjoint convex sets, which is probably the most fundamental theorem in the mathematical theory of optimization.

We have that since for . Then, . In other case, there exists a negative element of , since . By choosing the corresponding element of large enough, it follows which is a contradiction.

But also since, in other case, for all and therefore we can have choosing small enough, which is a contradiction.

From and it follows that . Hence, we have that for all with which concludes the proof, since there exists a profit vector , such that

If there exists a , such that , then is an efficient allocation process of . In other case, there exists a such that and, since , we have that , which is a contradiction.

Next: Practical and Computational Significance Up: A Theory of Bit Previous: Introduction
J. Fdez-Valdivia 2006-03-13