Multiplication-free fast codeword search algorithm using Haar transform with squared-distance measure

This letter presents novel multiplication-free fast codeword search algorit hms for encoding of vector quantizers (VQs) based on squared-distance measu re. The algorithms accomplish fast codeword search by performing the partia l distance search (PDS) in the wavelet domain. To eliminate the requirement for multiplication, simple Haar wavelet is used so that the wavelet coeffi cients of codewords are finite precision numbers. The computation of square d distance for PDS can therefore be effectively realized using additions. T o further enhance the computational efficiency of the algorithms, the addit ion-based squared-distance computation is decomposed into a number of stage s. The PDS process is then extended to these stages to reduce the addition complexity of the algorithm. In addition, by performing PDS over smaller nu mber of stages, lower computational complexity can be obtained at the expen se of slightly higher average distortion for encoding. Simulation results s how that our algorithms are very effective for the encoding of VQs, where b oth low computational complexity and average distortion are desired. (C) 20 00 Elsevier Science B.V. All rights reserved.