Fast Vector Quantization (Communication Theory, Source Coding, Data Compression).

Abstract

This thesis proposes a quantization technique that requires much fewer computations than a general vector quantizer, but requires more storage. The two main goals of the thesis are to investigate the practicality of the fast technique when compared with other quantizers, and to analyze its performance. Given the codebook of some vector quantizer, the goal is to find a fast quantization rule for this codebook. This is achieved by breaking the encoding into two stages; first, a source vector is quantized by a "fine" and fast vector quantizer (fine means its codewords are closely spaced). Second, a table look-up finds the closest (in distortion) codeword of the original codebook to that of the fine codebook. The fast quantization technique is capable of yielding distortion arbitrarily close to that of the minimum distortion rule for the original codebook at the price of an increasing amount of storage. The performance loss, which is the gap between the distortion of the fast and the minimum distortion rules, is studied when the fine quantizer is a rectangular lattice code. Upper bounds to the performance loss are derived in the cases of mean absolute and mean squared error fidelity criteria. Both bounds vanish as the lattice code gets finer. Then, a more detailed analysis is done which yields expressions for the limiting value of the performance loss as the lattice gets finer. In the case of a lattice code with r and om orientation a simpler formula for the performance loss is derived. It is shown that the performance loss when the original codebook is very large, is the same as the distortion of the lattice code regardless of the source and the codebook. Experimental results in support of the analytical results are included. Fast rules based on the rectangular lattice code and the Tree Searched Vector Quantizer (TSVQ) are applied to a number of codebooks designed for the i.i.d. Gaussian and Gauss-Markov sources as well as sampled speech. The overall performance of the fast rule is compared to that of the minimum distortion rule and also that of the TSVQ.