基于子空间三角不等式的高维码字搜索算法

本文分析了码字搜索算法中基于均值、方差和范数的删除准则,指出基于方差和范数的删除准则之间存在冗余缺陷.在此基础上,提出了一种新的子空间三角不等式删除准则,根据子空间中码字与参考点之间的距离来排除候选码字.基于方差的删除准则可以看成是子空间三角不等式删除准则的特例.在新的删除准则中,通过选择合适的子空间参考点,能够排除更...

A Fast Codeword Search Algorithm for High-Dimensional VQ Encoding Using Triangle Inequality in Subspace

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 Equal-variance Equal-norm Nearest Neighbor Search algorithm,the proposed algorithm reduces the computational time by 8% to 26%.