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

An efficient nearest neighbor codeword search algorithm based on Hadamard transform for vector quantization is presented in this paper. Four efficient elimination criteria are derived from two important inequalities based on three characteristic values in the Hadamard transform domain. Before the encoding process, all codewords in the codebook are Hadamard-transformed and sorted in the ascending order of their first elements. During the encoding process, we firstly perform the transform on the input vector and calculate its characteristic values, and initialize the current closest codeword of the input vector to be the codeword whose first element of Hadamard transform is nearest to that of the input vector, and secondly use the proposed elimination criteria to find the nearest codeword to the input vector using the up-down search mechanism near the initial best-match codeword. Experimental results demonstrate the proposed algorithm is much more efficient than most existing nearest neighbor codeword search algorithms in the case of high dimension.