Fast vector quantization based on lattice prequantization

A scheme for fast vector quantization is proposed. Instead of searching the whole code book directly, the proposed algorithm restricts the search to a very small subset of the code book. Given any input vector, the search process is divided into two steps: (1) define a subset that contains the nearest code vector and (2) find the optimal code vector from the subset. The main task of this algorithm is to define a minimum-size subset that is certain to contain the nearest code vector. A method that takes advantage of the relations of two kinds of Dirichlet partition, one of a lattice quantizer and the other of an ordinary vector quantizer, is given. Simulations using Gaussian and Laplacian sources show that the computational complexity can be substantially reduced with little loss (less than 0.1 dB) in performance