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.
|Number of pages||4|
|Publication status||Published - 1 Dec 2004|
|Event||2004 IEEE Asia-Pacific Conference on Circuits and Systems, APCCAS 2004: SoC Design for Ubiquitous Information Technology - Tainan, Taiwan, Republic of China|
Duration: 6 Dec 2004 → 9 Dec 2004
|Conference||2004 IEEE Asia-Pacific Conference on Circuits and Systems, APCCAS 2004: SoC Design for Ubiquitous Information Technology|
|Country/Territory||Taiwan, Republic of China|
|Period||6/12/04 → 9/12/04|