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

Shu Chuan Chu, Zhe Ming Lu, Jeng Shyang Pan, Kuang Chih Huang

Research output: Contribution to conferencePaper

Abstract

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.

Original languageEnglish
Pages85-88
Number of pages4
DOIs
Publication statusPublished - 1 Dec 2004
Externally publishedYes
Event2004 IEEE Asia-Pacific Conference on Circuits and Systems, APCCAS 2004: SoC Design for Ubiquitous Information Technology - Tainan, Taiwan, Province of China
Duration: 6 Dec 20049 Dec 2004

Conference

Conference2004 IEEE Asia-Pacific Conference on Circuits and Systems, APCCAS 2004: SoC Design for Ubiquitous Information Technology
CountryTaiwan, Province of China
CityTainan
Period6/12/049/12/04

Fingerprint Dive into the research topics of 'Hadamard transform based fast codeword search algorithm for high-dimensional VQ encoding'. Together they form a unique fingerprint.

  • Cite this

    Chu, S. C., Lu, Z. M., Pan, J. S., & Huang, K. C. (2004). Hadamard transform based fast codeword search algorithm for high-dimensional VQ encoding. 85-88. Paper presented at 2004 IEEE Asia-Pacific Conference on Circuits and Systems, APCCAS 2004: SoC Design for Ubiquitous Information Technology, Tainan, Taiwan, Province of China. https://doi.org/10.1109/APCCAS.2004.1412697