Hadamard transform based fast codeword search algorithm for high-dimensional VQ encoding

An efficient nearest neighbor codeword search algorithm for vector quantization based on the Hadamard transform is presented in this paper. Four elimination criteria are derived from two important inequalities based on three characteristic values in the Hadamard transform domain. Before the encoding process, the Hadamard transform is performed on all the codewords in the codebook and then the transformed codewords are sorted in the ascending order of their first elements. During the encoding process, firstly the Hadamard transform is applied to the input vector and its characteristic values are calculated; secondly, the codeword search is initialized with the codeword whose Hadamard-transformed first element is nearest to that of the input vector; and finally the closest codeword is; found by an up-and-down search procedure using the four elimination criteria. Experimental results demonstrate that the proposed algorithm is much more efficient than the most existing nearest neighbor codeword search algorithms in the case of problems of high dimensionality. (C) 2006 Elsevier Inc. All rights reserved.