Process for the Vector Quantization of Low Bit Rate Vocoders

1. Field of the Invention

The present invention relates to a process for the vector quantization of low bit rate vocoders.

It applies in particular to linear-prediction vocoders similar to those described for example in the THOMSON-CSF Technical Journal, Volume 14. No. 3, Sep. 1982, pages 715 to 731, and according to which the speech signal is identified at the output of a digital filter whose input receives, either a periodic waveform corresponding to those of the voiced sounds, viz. vowels, or to a random waveform corresponding to those of the unvoiced sounds, viz. the majority of consonants.

2. Discussion of the Background

It is known that the auditory quality of linear-prediction vocoders depends in large part on the accuracy with which their predictive filter is quantized and that this quality generally decreases as the digital bit rate between vocoders decreases since the accuracy of quantization of the filter then becomes insufficient. Numerous quantization processes of the type of those described for example in Patent Application EP 0504485 A2 or in U.S. Pat. No. 4,907,276 have been developed in order to solve this problem. In general, the speech signal is segmented into independent frames of constant duration and the filter is renewed at each frame. Thus, to arrive at a bit rate of around 1820 bits per second, the filter must, according to a standard implementation, be represented by a packet of 41 bits transmitted every 22.5 milliseconds. For non-standard links with a lower bit rate, of the order of 800 bits per second, fewer than 800 bits per second have to be transmitted in order to represent the filter, this constituting a bit rate ratio of approximately 3 as compared with standard implementations. 30 bits on average are used to quantize one filter out of two, and these 30 bits are composed of 3 bits defining a quantization scheme and 27 bits for quantizing 10 quantities obtained from LAR (Log Area Ratio) coefficients by displacement and rotation in the 10-dimensional space thus defined. As a result the quantization now begins to be only approximately transparent, and auditory compensation of this artefact is necessary, by coarse quantization of the filters located in the transitions of the speech signal and fine quantization of those corresponding to stable zones. To obtain sufficient accuracy of quantization of the predictive filter despite everything, the conventional approach consists in employing a vector quantization scheme which is intrinsically more efficient than that used in standard systems where the 41 bits employed serve for the scalar quantization of the P=10 coefficients of their prediction filter. The method relies on using a dictionary containing a specified number of standard filters obtained by learning. It consists in transmitting only the page or the index at which the standard filter rate which is obtained, only 10 to 15 bits per filter being transmitted instead of the 41 bits required in scalar quantization mode, however this bit rate reduction is obtained at the cost of a very large increase in the memory size required to store the elements of the dictionary and of a considerable computational burden attributable to the complexity of the filter search algorithm.

By applying this approach also to low bit rate vocoders of 800 bits/s and less, it is commonly supposed that 24 bits are sufficient for a composite dictionary produced from two dictionaries with 4,096 elements accounting for the first four and last six LSPs respectively. The major drawback of this type of quantization again resides in the need to compile this dictionary, to store it and to perform the quantization proper.

Alternatives to the vector quantization scheme have also been proposed in order to reduce the number of elements stored in the dictionary. Thus, a technique of pyramidal vector quantization is in particular known, a description of which may be found in the journal IEEE trans. on INFTH Vol. IT 32 No. 4, July 1986, pages 568 to 582 by Thomas R. Fischer entitled "A pyramid vector quantizer". According to this technique the multidimensional input data are distributed over the vertices of a regular grid included within a pyramid of multiple dimension. This quantization technique is applied mainly in respect of data with a Laplacian distribution characteristic. However, the reduction in bit rate which results from this is not always sufficiently appreciable. This is due in particular to the fact that in practice the overall shape of the multidimensional data to be processed is in actual fact inscribed within an ellipsoid, especially when using a prediction/extrapolation computation system which always involves a Gaussian characteristic shape of data. Moreover, the pyramid which is inscribed on this ellipsoid leads to the coding of the points which lie outside the ellipsoid surrounding the scatter of points to be coded, thereby making it necessary to dimension code words with a number of bits which exceeds what is strictly necessary.

The objective of the invention is to overcome the aforementioned drawbacks.

To this end, the subject of the invention is a process for the vector quantization of low bit rate vocoders, characterized in that it consists in determining the coding region by surrounding with an envelope the scatter of the points of the auto-correlation matrix of the reflection coefficients of the filter for modelling the vocal tract, in determining the principal axes of the volume of points inside the envelope, in projecting the coefficients of the autocorrelation matrix onto the principal axes, in partitioning the interior volume of the envelope into elementary volumes and in coding the coefficients resulting from the projection on the basis of their coordinates in the space defined by the principal axes of the volume of the points inside the envelope, while allocating as code values only those values corresponding to the locations of the elementary volumes in which they lie.

The main advantage of the invention is that it employs a prediction filter quantization process which requires virtually no more binary elements to quantize the points representing the prediction filters than a dictionary-based vector quantization process, whilst remaining simple and fast to implement and occupying only a small memory space.

Other characteristics and advantages of the invention will emerge below with the aid of the description which follows with regard to the figures of the appended drawings which represent:

FIG. 1 a flow chart illustrating the speech coding process employed by the invention.

FIG. 2 a two-dimensional vector space depicting a distribution of area coefficients derived from the reflection coefficients modelling the vocal tract.

FIG. 3 an illustration of the coding process according to the invention in a three-dimensional space.

FIGS. 4 to 8b, example distributions of the coding of points in a three-dimensional space obtained by implementing the process according to the invention.

The coding process according to the invention consists, after having partitioned the speech signal into frames of constant length of around 20 to 25 ms, as is customarily the case in vocoders, in determining and coding the characteristics of the speech signal on successive frames by determining the energy of the signal P times per frame.

The synthesis of the speech signal on each frame is then carried out by deframing and decoding the values of the coded characteristics of the speech signal.

The representative steps of the coding process according to the invention which are represented in FIG. 1 consist in computing in step 1, after a step (not represented) of sampling the speech signal S.sub.K on each frame and quantizing the samples over a specified number of bits followed by a pre-emphasizing of these samples, the coefficients K.sub.i of a filter for modelling the vocal tract on the basis of autocorrelation coefficients R.sub.i of the samples S.sub.K according to a relation of the form ##EQU1##

The coefficients K.sub.i are computed for example by applying the known algorithm by M. Leroux-Guegen, a description of which can be found in the article from the journal IEEE Transaction on Acoustics Speech, and Signal Processing, June 1977 entitled "A fixed point computation of partial correlation coefficients". This computation amounts to inverting a square matrix whose elements are the coefficients R.sub.i of relation (1).

The next step 2 consists in non-linearly distorting the reflection coefficients by transforming them into area coefficients denoted LAR.sub.i from the abbreviation LOG AREA RATIO using the relation ##EQU2## so as in step 3 to compute the eigenvectors of an autocorrelation matrix of the coefficients LAR.sub.i which define in the P-dimensional space the favoured directions of a scatter of points whose coordinates are the coefficients LAR.sub.i with i=1-P. By way of example the scatter of points represented in FIG. 2 in a space with just two dimensions exhibits two favoured directions symbolized by the eigenvectors V.sub.1 and V.sub.2.

Returning to FIG. 1, step 4 consists in projecting the LAR coefficients onto the favoured directions by computing for example coefficients .lambda..sub.i, representing the sum of the projections of the coefficients (LAR.sub.j LARj) onto the eigenvectors V.sub.i to V.sub.p of the autocorrelation matrix of the coefficients LAR, using the relation ##EQU3## in which V.sub.i,j denotes the eigenvectors and LAR.sub.j is the mean value of each coefficient LAR.sub.j of rank j.

Since each of the coefficients .lambda..sub.i moves between a minimum value -.lambda..sub.imax and a maximum value +.lambda..sub.imax, this movement makes it possible to approximate the shape of the observed scatter of points by a hyperellipsoid, the values of the semi-major axes of which are represented by the coefficients .lambda..sub.imax.

For each of the .lambda..sub.i, a uniform quantization is then performed between a minimum value .lambda..sub.imini and a maximum value .lambda..sub.imax using a number of bits n.sub.i which is computed by the conventional means on the basis of the total number N of bits used to quantize the filter and the percentages of inertia corresponding to the eigenvectors V.sub.i.

The coefficients .lambda..sub.i are quantized using a measure of distance between filters, the most natural of which is the weighted Euclidean distance of the form: ##EQU4## in which the coefficients .gamma..sub.i are a decreasing function of their rank i and are fitted experimentally.

In an equivalent manner, given that the coefficients .gamma..sub.i are centred about the barycentre of the hyperellipsoid, the same result can also be achieved by using a purely Euclidean distance measure pertaining to the modified coefficients, such as ##EQU5## The representative points of the filters with coordinates .mu..sub.i then lie inside a hyperellipsoid of dimension P, the P semi-major axes of which are respectively equal to .mu..sub.imax with .mu..sub.imax =.lambda..sub.imax .gamma..sub.i.sup.1/2.

Under these conditions if each of the coordinates .mu..sub.i were quantized uniformly between -.mu..sub.imax and +.mu..sub.imax, the number of bits required would then be equal to the logarithm to the base 2 of the ratio between the quantizable parallelepipedal volume (slab) and the volume of an elementary hypercube according to the relation ##EQU6## where .DELTA. is the quantization interval. However, this definition leads to the representation not only of the points inside the ellipsoid but also a multitude of exterior points. For example, in dimension 3, this leads to the representation of twice as many points as necessary. This expansion in the number of points to be coded grows as the number of dimensions of the space to be considered increases.

Thus considering the volume of an ellipsoid defined for P even by the relation ##EQU7## the number of bits N.sub.E strictly necessary is then given by ##EQU8## thus giving ##EQU9##

In the case of a prediction filter with P=10 coefficients this represents a difference of -8.65 bits and shows that in principle it is sufficient to use only 24 bits for N.sub.E instead of the 33 bits required to quantize the coefficients .mu..sub.i independently.

Under these conditions it appears that the only means of actually making a saving in the bits desired consists in forming a quantization in a space which is strictly limited inside the useful volume, of the ellipsoid of the points .mu..sub.i. The invention achieves this by executing, in step 5, an algorithm which makes it possible unambiguously to enumerate all the points lying inside this volume.

For the convenience of the account, it will be assumed in what follows that the volume of the points is delimited by an envelope of ellipsoidal or pyramidal shape, but it will be appreciated that the coding process of the invention which is described also holds true for volumes of any envelope.

Assuming for simplicity that the space of the data to be quantized is a space of dimension 3 (N=3) and that all the points inside an ellipsoid with orthonormal axes 2X, 2Y, 2Z can be quantized using a quantization interval equal to one, the quantization process according to the invention applied to this space consists in associating a unique number with each set of integer coordinates x0, y0, z0 satisfying the relation: ##EQU10##

As FIG. 3 shows, this association is carried out in three steps. A first step consists in traversing the x axis and in computing the total number of points lying in the slices of the ellipsoid which are perpendicular thereto and which cut the x axis at points for which x takes the successive integer values -X, -X+1, . . . , x-2, x-1. The second step consists in traversing the y axis while adding to the previous result the sum of the numbers of points lying in the slices of the ellipsoid whose abscissa is equal to x and whose ordinate is equal in succession to -Y(x), -Y(x+1), . . . , y-2, y-1 where Y(x).ltoreq.Y and is the largest value for which the point with coordinates (x Y(x), 0) lies in the ellipsoid or its surface. Finally, according to the third step, the z axis is traversed while adding to the previous result the sum of the numbers of points lying in the slices whose abscissa is equal to x, whose ordinate is equal to y and whose altitude is equal successively to -Z(x,y), -Z(x,y)+1, . . . , z-2, z-1 where Z(x,y).ltoreq.Z and is the largest value for which the point with coordinates (x,y,Z(x,y) lies in the ellipsoid or its surface. The final result gives the exact number of points extending ahead of the point to be quantized, that is to say the points for which x or y or z is less than xo, yo or zo respectively. This principle can naturally be extended to spatial dimensions of any order. For a space of order N, the various volumes of dimensions 2, 3, . . . , N-1 are precomputed and stored in a read-only memory. By generalizing this principle to an ellipsoid with N dimensions, and denoting the dimensions of the semi-axes as A.sub.1, A.sub.2, . . . , A.sub.N, the volume inside the ellipsoid is defined by the relation:

with .alpha..sub.m = ##EQU11## and the equation of its surface is defined by the relation: ##EQU12## Denoting by V.sub.m(A) the volume of a slice with m dimensions (m<or equal to N) of the ellipsoid, in which the m.sup.th coordinate lies between -A and +A, the latter is expressed by the relation: ##EQU13## Using the relation (14) it is easy to deduce a recurrence relation linking two volumes with consecutive dimensions, i.e.: ##EQU14## The number of points to be quantized can then be obtained from the above relations by considering for example that the quantization interval is equal to 1 and that the dimensions of the axes Ai are positive integers. This determination can be achieved by considering in succession the isolated points (dimension 0), the series of contiguous points (dimension 1), and then by iteratively computing the volumes of dimensions 2 . . . N-1.

A microprogram enabling this result to be obtained is given in Appendix 1.

The quantization algorithm according to the invention is deduced from the abovementioned example in 3 dimensions. This algorithm consists in accumulating in the code value the number of points encountered on starting from a minimum value of the coordinates so as to arrive at the code value of the point considered. To perform this processing operation, the actual values of the coordinates X.sub.i are firstly converted into their nearest integer value. The resulting values are then corrected so as to be certain that the corresponding point does indeed lie inside the ellipsoid, since for any points which may be outside, it is supposed that the quantization error may be larger than that obtained for the points inside. An optimum procedure for processing these points would be to find the points which seem to be nearest to the interior of the ellipse. However, with the exception of a quantizing of points inside a sphere, there is unfortunately no simple process for performing this processing operation. A suboptimum algorithm for placing these points iteratively inside the ellipsoid by modifying their successive coordinates is as follows:

R=A.sub.N

FOR n=N DOWN TO 1

IF X.sub.n >R THEN X.sub.n =R

ELSE IF X.sub.n <-R THEN X.sub.n =-R

R=(A.sub.n-1 /A.sub.n) (R.sup.2 -X.sub.n.sup.2)1/2

END FOR

In practice the instructions of the above algorithm have to be incorporated into the microprogram for the coding proper by using the volumes V.sub.n (A) already computed. This algorithm involves accumulating, in the final code, the number of points left behind the coded point with coordinates (X.sub.1 . . . X.sub.N) when starting from a point with coordinates (0, 0 . . . 0, A.sub.N) on the surface of the ellipse and descending toward the point to be quantized. A microprogram for executing this coding algorithm is given in Appendix 2.

Naturally the maximum execution time for the above algorithm can be shortened by virtue of the symmetries. Thus, if Code0 represents the code of the origin point with coordinates (00 . . . 0) and C represents the code value for the point with coordinates X.sub.1, . . . , X.sub.N the code corresponding to the symmetric point (-X.sub.1, . . . , -X.sub.N) is exactly equal to 2* Code0-C. To take this into account, the above microprogram can be supplemented with the following instructions:

Inversion=FALSE

IF X.sub.N >=0

Inversion=TRUE

FORi=1 TO N DO X.sub.i =-X.sub.i

END IF

IF Inversion THEN Code 2 Code0-Code

An example quantization is represented in FIG. 4 for the axis values A.sub.1 =1, A.sub.1 =3 and A.sub.1 =4. In this representation there are in total 37 centroids of elementary cubes and the barycentre of the ellipsoid corresponds to the code 18. For comparison, an example of an equivalent pyramid quantization is represented in FIG. 5. In this case the barycentre corresponds to the code 14.

The dequantization algorithm proceeds by seeking to reconstruct the terms which were added to give the value of the code, knowing that this reconstruction is by nature unique.

A corresponding microprogram is given in Appendix 3.

In order to account for certain situations in which it may be of interest to displace the origin of the set of centroids, the above algorithms may again be modified by considering half-integer rather than integer coordinates. A first possibility can consist in making a quantizer whose axes are twice the dimension of the axes A, required. A vector of N actual values can then be quantized after doubling, using odd integers only. The above algorithm can then be used, the output code obtained being converted by a table giving the final code. This transcoding is necessary for the reason that although only around a quarter of the original centroids need to be considered, this reduction does not correspondingly ease the execution of the algorithm. This is because, as FIG. 6 shows, with axis dimensions A.sub.1 =1, A.sub.2 =3, A.sub.3 =4, an extended ellipsoid of dimensions 2, 6 and 8 is then obtained which contains 369 centroids, this being very substantial compared with the 56 centroids of the ellipsoid devised with half-integer coordinates.

A second possibility can consist in modifying the initialization of the algorithm, the coding and the decoding in such a way as to use even coordinates only. Corresponding modified microprograms are given in Appendix 4.

The codes are transmitted as binary words. However, since a priori there is no particular reason why the number of points lying inside an ellipsoid should form an exact power of two, it appears highly desirable in order to use an optimal number of bits in the formation of the code, that this number be as close as possible to an exact power of two. This can be obtained by adjusting the volume of the ellipsoid by fractional rather than integer axis lengths.

In order to simplify the account, it will be assumed that the fractions representing the axes A, have a common denominator. In practice, the denominator values 1, 2, 3 are sufficient to obtain without difficulty ellipsoids containing a number of centroids as near as possible to an exact power of two.

For example, by considering in dimension 4 an ellipsoid of dimensions (3, 4, 5, 6), the latter contains exactly 1765 points. This number lies exactly between 1024 and 2048. By modifying these dimensions in the ratios (9/3, 13/3, 15/3, 19/3) this number is changed by the number 2025 which is 98.87% close to 2048 and may be said to represent an equivalent binary loss of log.2(0.9887)=0.016 bits. The difference 2048-2025=23 codes lost can then be used for coding particular configurations if necessary.

Consequently, the above algorithms may again be modified by considering axis lengths of the form (A.sub.1 /D, A.sub.2 /D, . . . , A.sub.N /D) where D is a common denominator of small value. High values of D are not necessary since in practice, it is always possible to obtain good coding with D=1, 2 or 3.

The introduction of a common denominator leads to the following processing operations being performed:

1--definition of the axes:

2--equation of the ellipsoid (K=2) of the pyramid (K=1): ##EQU15## 3--maximum value of X.sub.n ##EQU16## 4--By reducing to the same denominator and keeping only the numerators, the following recurrence formulae are defined: ##EQU17##

The above relations show that if D is different from 1 or if the axes A.sub.i do not have small dimensions or if the dimensions N are large, a large number of points must be computed and that this computation must be performed in multiprecision arithmetic. The maximum value of X.sub.n is exactly (Num.sub.n /Den.sub.n).sup.1/2, and this value is almost never an integer, and therefore it is impossible to use the arrays such as V.sub.n (X.sub.n) when programming. In practice, this problem can be solved by using two arrays, one array for the volumes and one array of values corresponding to the numerator since the denominators do not change. In this way, access to a specified volume may be achieved through the numerator corresponding to that sought. To reduce the computation time the numerators are stored in ascending order together with their corresponding volume. The initialization, coding and decoding microprograms are then modified in the manner represented in Appendix 5.

Another possibility consists in considering only the centroids for which the sum of the coordinates is even or odd. This amounts to keeping only half the original centroids, the latter being distributed over the original grid with origin DN here denoted D.sub.n0 where its complement D.sub.n1 which does not include the origin.

The main advantage of proceeding in this way is that it makes it possible to decrease the average quantization error by -0.25 db if N=3 where by around -0.4 db for N=4 to 10. This leads to modifying the initial quantization algorithm by considering only the points with even or odd coordinates respectively. Under these conditions the quantization algorithm consists in quantizing the points as before by searching for the nearest integer values of each coordinate and in modifying the integer coordinates which are most distant from their actual original value. However, the coding and decoding are then slightly more complex than for a grid of points having integer coordinates.

This is because two sets of volumes have to be found for dimensions 1 to N-1, a first set V.sub.0,n(A) of n-dimensional volumes having an odd sum of coordinates to a second set V.sub.1n (A) of volumes of dimension n having an even sum of coordinates. Under these conditions the computation of the volumes takes place in the manner described by the microprogram of Appendix 6.

An example of ellipsoidal vector quantization for D.sub.3,0 and D.sub.3,1 is represented in FIGS. 7a and 7b. In this representation, the three axes have dimensions 2, 4, 5 respectively, that is to say they are slightly larger than those of the earlier examples in order to obtain a sufficient number of points. Each centroid is joined to its nearest neighbours in the same way as in FIGS. 4 and 6. It can be verified in these figures that the barycentre belongs (FIG. 7a) or does not belong (FIG. 7b) to the set of centroids.

A generalization of the process to a pyramid quantization is also represented in FIGS. 8a and 8b.