Quantization of Multiple Sources Using Nonnegative Integer Bit

Asymptotically optimal real-valued bit allocation among a set of
quantizers for a finite collection of sources was derived in 1963 by Huang
and Schultheiss, and an algorithm for obtaining an optimal nonnegative
integer-valued bit allocation was given by Fox in 1966. We prove that,
for a given bit budget, the set of optimal nonnegative integer-valued bit
allocations is equal to the set of nonnegative integer-valued bit
allocation vectors which minimize the Euclidean distance to the optimal
real-valued bit-allocation vector of Huang and Schultheiss. We also give
an algorithm for finding optimal nonnegative integer-valued bit
allocations. The algorithm has lower computational complexity than Fox's
algorithm, as the bit budget grows. Finally, we compare the performance
of the Huang-Schultheiss solution to that of an optimal integer-valued bit
allocation. Specifically, we derive upper and lower bounds on the
deviation of the mean-squared error using optimal integer-valued bit
allocation from the mean-squared error using optimal real-valued bit
allocation. It is shown that, for asymptotically large transmission
rates, optimal integer-valued bit allocations do not necessarily achieve
the same performance as that predicted by Huang-Schultheiss for optimal
real-valued bit allocations.
Benjamin Farber earned his bachelors in Electrical Engineering from
Cornell University in 1999. He completed his PhD in Electrical and
Computer Engineering from the University of California, San Diego, in 2005
under the supervision of Professor Kenneth Zeger. His research is
focused on scalar quantization over noisy channels and the bit allocation
problem for a finite set of quantizers.