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

This letter presents novel multiplication-free fast codeword search algorithms for encoding of vector quantizers (VQs) based on squared-distance measure. The algorithms accomplish fast codeword search by performing the partial distance search (PDS) in the wavelet domain. To eliminate the requirement for multiplication, simple Haar wavelet is used so that the wavelet coefficients of codewords are finite precision numbers. The computation of squared distance for PDS can therefore be effectively realized using additions. To further enhance the computational efficiency of the algorithms, the addition-based squared-distance computation is decomposed into a number of stages. The PDS process is then extended to these stages to reduce the addition complexity of the algorithm. In addition, by performing PDS over smaller number of stages, lower computational complexity can be obtained at the expense of slightly higher average distortion for encoding. Simulation results show that our algorithms are very effective for the encoding of VQs, where both low computational complexity and average distortion are desired.