A fast VQ codebook generation algorithm using codeword displacement

摘要

In this paper, we present a fast codebook generation algorithm called CGAUCD (Codebook Generation Algorithm Using Codeword Displacement) by making use of the codeword displacement between successive partition processes. By implementing a fast search algorithm named MFAUPI (Modified Fast Algorithm Using Projection and Inequality) for VQ encoding in the partition step of CGAUCD, the codebook generation time can be further reduced significantly. Using MFAUPI, the computing time of CGAUCD can be reduced by a factor of 4.7–7.6. Compared to Generalized Lloyd Algorithm (GLA), our proposed method can reduce the codebook generation time by a factor of 35.9–121.2. Compared to the best codebook generation algorithm to our knowledge, our approach can further reduce the corresponding computing time by 26.0–32.8%. It is noted that our proposed algorithm can generate the same codebook as that produced by the GLA. The superiority of our method is more remarkable when a larger codebook is generated.