Asymptotically optimal block quantization

Abstract

In 1948 W. R. Bennett used a companding model for nonuniform quantization and proposed the formula <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D \: = \: \frac{1}{12N^{2}} \: \int \: p(x) [ É(x) ]^{-2} \dx</tex> for the mean-square quantizing error where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</tex> is the number of levels, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</tex> (x) is the probability density of the input, and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E \prime</tex> (x) is the slope of the compressor curve. The formula, an approximation based on the assumption that the number of levels is large and overload distortion is negligible, is a useful tool for analytical studies of quantization. This paper gives a heuristic argument generalizing Bennett's formula to block quantization where a vector of random variables is quantized. The approach is again based on the asymptotic situation where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</tex> , the number of quantized output vectors, is very large. Using the resulting heuristic formula, an optimization is performed leading to an expression for the minimum quantizing noise attainable for any block quantizer of a given block size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</tex> . The results are consistent with Zador's results and specialize to known results for the one- and two-dimensional cases and for the case of infinite block length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(k \rightarrow \infty)</tex> . The same heuristic approach also gives an alternate derivation of a bound of Elias for multidimensional quantization. Our approach leads to a rigorous method for obtaining upper bounds on the minimum distortion for block quantizers. In particular, for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k = 3</tex> we give a tight upper bound that may in fact be exact. The idea of representing a block quantizer by a block "compressor" mapping followed with an optimal quantizer for uniformly distributed random vectors is also explored. It is not always possible to represent an optimal quantizer with this block companding model.

Keywords

Related Publications