A radius-bucketing approach to fast vector quantization encoding

The authors present a computationally efficient encoding scheme for vector quantization. Efficiency is achieved by combining techniques: homes are bucketed into the subset of codewords in the same region as the input point; the energy of the input point eliminates codewords not in the same energy range; the smallest hyperrectangle parallel to the coordinate axes that bounds the Voronoi region associated with the codeword acts as a discriminant; and approximations to the actual distortion are used to avoid multiplications. Simulations on Gaussian sources with ranges of codebook sizes and block sizes indicate that the encoding time, measured in multiplications, actually falls with increasing codebook size. It is shown that with no increase in signal/noise ratio the algorithm substantially outperforms tree search and binary hyperplane testing search