Обработка сигналов в системах телекоммуникаций

3.1. Dependencies in LSF codebook

Observations of LSF properties coefficients can allow discovering conception to reduce computational complexity for codebook searching [9]. Our intention is quantity limitation of comparisons of examined vectors through preliminary elimination from search area codevectors with very large distance to investigated test vectors. Analysis of distances between codebook vectors and test vectors for individual LFS dimensions as well as range of changeability for singular LSF coefficients allow us to draw a conclusion. About 99 % of test LSF vectors in each dimension are at distance less than 0.06 from codevectors. Let’s divide each of codebook dimensions for some number of classes. For each test vector we can simply appoint classes with large and with minimal probability of belonging to its codebook. Only large probability classes were chosen to code vector searching.

The main question is: how to split individual LSF dimensions into pieces allows mentioning above observations. We propose new procedure for codebook structuralize and search space reduction.

4. Codebook Structure

Fig. 1. Structuralized codebook creation procedure

Codebook design process was spitted into two steps (see figure 1). First of them is standard 2-Split, 5-5 dimensional codebook creation. Second – structuralization of prepared codebooks using internal splitting methods, sorting codevectors and designing tree structure for higher performance of codebook search. Each of 2 codebooks was designed independently from other.

4.1. Codebook structuralization procedure

Standard codebook created using LBG algorithm have a large correlations between successive vector coefficients in each codebook cell [7]. Taking this fact into consideration, we can affirm that number of comparisons between codebook and test vectors can be strongly reduced. Only codebook vectors with individual coefficients lying in specified regions stand a chance to be chosen to direct seeking.

So we can propose new algorithm for structuralize codebook. Let’s take first dimension coefficients of codebook vectors. Entire range of variability can be spitted into established numbers of parts. For each partition, vectors were sorted and spitted, and division points were stored in nodes of tree. The same procedure is repeated for all of partitions, but for successive dimensions of codebook vectors.

Illustration of structuralized 10-dimensional, 2*12-bit codebook with simple 2 split is shown on figure 2.



Fig. 2. Proposed new structure of LSF vectors codebook

4.2. Fast codebook search procedure

For each test vector 10-dimensional codebook searching procedure is performed. First of all, for single codebook dimension, individual coefficients of test vector are compared to tree nodes and one of codebook classes for processed dimension is selected. Each transition to next dimension reduces number of codebook vectors. Iteration process for each dimension give us reduced codebook consist only a few percent of codevectors, according to method of internal splitting and number of classes. For reduced codebook a standard search method is applied. Great computational reduction relate to only inconsiderable spectral distortion degradation.

5. Performance of Structuralized Split Vector Quantizer

Method to obtain maximum computational complexity reduction with minimal spectral distortion degradation is selecting proper kind of internal vectors splitting. A variety of splitting method was tested. First of them is simple division all range of coefficient changeability into selected number of classes. We tested simple internal splitting for 2 and 3 classes per dimension (methods Simple 2 Split and Simple 3 Split). In second kind of splitting we used Generalized Lloyd Algorithm to select better technique of class splitting. 2 and 3 classes for each dimension were used (methods Linear VQ 2 and Linear VQ 3). Last tested scheme use splitting for 3 classes per dimension and selection of 2 best groups (3/2 Split method).

Table 1 shows the results of our research: spectral distortions, computational complexity and required additional memory for tested codebooks in comparison to 2–Split Vector Quantizer at 24 bit per frame.

Table 1. Spectral distortion and computational efficiency for Structuralized Split VQ at 24 bit/frame

Codebook internal splitting method	Bits/ frame	Avg. SD in dB	Outliers (in %)		Computational complexity reduction	Additional memory (integers)
			2-4 dB	> 4dB
Standard Split VQ	24	1,01	1,28	0	-	-
Simple 2 Split	24	1,12	3,16	0	32,3	124
Simple 3 Split	24	1,25	6,50	0.04	257,7	726
Linear VQ 2	24	1,11	3,15	0	22,3	124
Linear VQ 3	24	1,26	8,39	0,18	129,6	726
3/2 Split	24	1,08	2,44	0	17,6	726

Our structuralized codebook search scheme provides about 32 times reduction of computational complexity with only about 10% of spectral distortion deteriorates for Simple 2 Split method. For 3/2 Split scheme we get 17,6 times reduction of computation and only 7 % of distortion degradation.