电子学报2011，Vol.39Issue(4)：940-945,962,7.
基于子空间三角不等式的高维码字搜索算法
A Fast Codeword Search Algorithm for High-Dimensional VQ Encoding Using Triangle Inequality in Subspace
摘要
Abstract
Elimination criteria based on mean value, variance and norm was often used in the VQ encoding to reject unlikely codewords. However, these elimination criteria have obvious computational redundancy. A new elimination criteria based on triangular inequality in subspace was proposed. By finding the optimal reference point of distance computation, the new elimination criteria can reject more unlikely codewords than other elimination criteria using variance and norm. The elimination criteria based on variance can be seen as the special case of new elimination criteria. Before the search process, all codewords in the codebook are Hadamard-transformed and sorted in the ascending order of their first elements. During the search process, the mean value of a vector was used to terminate the search process, and the new elimination criteria based on triangular inequality in subspace was applied to reject most unlikely codewords. Experiments results demonstrate that the performance of the proposed algorithm is much better than other nearest neighbor codeword search algorithms. Compared with the Hadamard-Transformed based Equal-Average Equalvariance Equal-norm Nearest Neighbor Search algorithm,the proposed algorithm reduces the computational time by 8％ to 26％.关键词
矢量量化/码字搜索/子空间/三角不等式Key words
vector quantization/ codeword search/ substpace/ triangle inequality分类
信息技术与安全科学引用本文复制引用
崔江涛,李凤华,马建峰..基于子空间三角不等式的高维码字搜索算法[J].电子学报,2011,39(4):940-945,962,7.基金项目
国家863高技术研究发展计划(No.2007AA01Z429,2007AA01Z472,2007AA01Z482) （No.2007AA01Z429,2007AA01Z472,2007AA01Z482）
国家自然科学基金(No.60633020,6087204) （No.60633020,6087204）
教育部重点项目(No.209156) （No.209156）
北京市自然科学基金(No.4102056) （No.4102056）
北京电子科技学院信息安全重点实验室基金(No.YZDJ0807) （No.YZDJ0807）
