SEARCH VECTORS IN THE CODEBOOK DURING COMPACTION BEAMS BASED ON BINARY TREE

Abstract

Speech signals transmission without coding requires high-speed communication channels because of a large redundancy of data. That is why in modern digital communication systems are widely used speech coding algorithms that implement a high degree of coding while maintaining a sufficient level of sound quality, in particular including codebooks using. It is widely used vector quantization. However, the practical use of vector quantization in real time is limited due to the sharp increase in costs of memory and coded vector search time in the codebooks. To reduce the nearest vector search time in codebooks the method of structuring the codebook is proposed. Shown that using of the binary tree allows to reduce the distance measurements number significantly that are needed to find the nearest neighbor vector. The main factors influencing search performance are analyzed. Several parameters partition options are considered when creating the tree, namely: midpt, which cuts the current cell by the splitting plane through its midpoint orthogonal to its longest side; sl_midpt, that differs from the previous by ''sliding" the splitting plane, if a trivial split were to result in order to avoid this; sl_fair, that combines split at the median with sl_midpt taking into account the aspect ratio bound. The results of comparative analysis of the listed methods are presented. Properties LSF as an object of quantization are considered when building the binary tree. The methods performance are studied experimentally. As all vectors in codebooks cover only the top of the rectangular area it was proposed to rotate the coordinate axis 45 degrees counterclockwise, recalculating the vectors coordinates. This enabled us to reduce the search time due to the achieving more symmetrical tree partitioning. Results evaluation was based on distances calculations number in the codebooks needed to find the nearest vector, among the sample test. The method using for speech quantization reduced the nearest vector search time to 5% of full-time search. Search time reducing (? 17 times) when the transmission of speech signals is achieved by additional computational costs of the preparatory steps needed for building a binary tree, and also increase the amount of memory needed to store.