Reduced Real-Time Processing in Stochastic Celp Encoding

The present invention relates to improvements in a method for digital compression of speech and other audio signals, and, more particularly, to improvements in stochastic code excited linear predictive encoding.

Code Excited Linear Predictive encoding (CELP) is well-known as a means of digitally compressing speech and other audio signals for improving the efficiency of communication. Using CELP, the speech to be transmitted, referred to hereinafter as the "target speech," is analyzed by an encoder to determine a set of parameters and indices in a codebook of excitation vectors which best characterize the actual target speech waveform. It is these parameters and codebook indices which are transmitted, rather than signals representing the waveform of the target speech itself. Doing so realizes substantial savings in transmission costs, since the parameters and codebook indices require far less bandwidth to transmit than unprocessed speech. At the other end of the transmission, a compatible decoder synthesizes waveforms according to the received parameters and codebook indices, and thereby reconstructs the target speech. The present application uses the term "speech" to denote any analogs signals over a spectrum up to 4 KHz.

In order to perform the analysis by which the codebook indices and parameters are determined, the original analog target speech waveform is first digitally sampled according to the Nyquist criterion at a minimum of twice the maximum frequency of the desired spectrum. For example, to attain a commonly-found 4 KHz maximum frequency, the sampling rate must be at least 8 KHz. The speech samples are then divided into sequential time frames. A typical frame at an 8 KHz sampling rate would contain 160 samples, corresponding to a 20 msec segment of speech. The frames are next divided into subframes. The codebook excitation vectors, represent Gaussian noise samples; their vector size corresponds to the number of samples in a subframe. Hereinafter, N denotes the number of excitation vectors in a codebook. Typically, N is of the order of 128. When the appropriate excitation vector is selected from such a codebook and input into a weighted synthesis filter which has been set with suitable linear predictive coefficients (LPC's), the output of the weighted synthesis filter is a waveform which can closely approximate a segment of the speech waveform. It is the index of this excitation vector in the codebook which is transmitted along with the LPC's and associated parameters to compress the speech of that segment. All of the filters used in such an encoder are linear filters, and therefore when reference is made to a filter in the present application, it will be understood that it is a linear filter.

A crucial portion of the analysis performed by the encoder, therefore, is a search through the codebook to find the optimum excitation vector to use. This requires testing all the excitation vectors one at a time, by sending each excitation vector to the input of the weighted synthesis filter, and then comparing the output of the weighted synthesis filter to the sampled target speech waveform. The excitation vector which yields the closest fit to the target speech segment is selected. This excitation vector is simply and easily referenced by its index in the codebook and therefore specifying i is equivalent to specifying c.sub.i.

FIG. 1, to which reference is now briefly made, illustrates conceptually the prior art method for selecting the optimum excitation vector from a codebook. Each excitation vector in the codebook is referenced by an index i, c.sub.i is thus the excitation vector corresponding to the index i. The target speech sample 14 t(n) is processed by a weighting filter 16 which is a function of the LPC, to yield the weighted target speech sample t.sub.w (n). Each excitation vector c.sub.i of the codebook 10 is processed by the weighted synthesis filter 12 to result in a weighted synthesized speech sediment S.sub.i (n), Which is compared against weighted target speech sample by comparator 18, Whose output is the difference t.sub.w (n)-S.sub.i (n), which is the error vector E(n). Error computation 20 computes the mean squared error over the error vector for each codebook index i. The index i whose c.sub.i has minimal mean squared error is the selected index.

In practice, the computation for selecting the codebook index is different from the conceptual procedure illustrated in FIG. 1, although it is mathematically equivalent. The impulse response of the weighted synthesis filter is a matrix denoted by H, which may be selected, for example, to be the truncated impulse response of the weighted synthesis filter. The matrix H will be changed from one adaptive codebook subframe to the next. As is known in the art, the optimum excitation vector c.sub.i selected by the process illustrated in FIG. 1 has the property that there is a selection function which is maximum over the set of excitation vectors in the codebook for c.sub.i. This selection function is usually given as the error function .epsilon..sub.i. ##EQU1## where t.sub.w.sup.T is the transpose of t.sub.w. The numerator of Equation (1) is the square of the cross-correlation of t.sub.w with the convolution of the impulse response H with the excitation vector c.sub.i. In general, a selection function will be a function of the energy term .parallel.Hc.sub.i .parallel..sup.2, which is the self-correlation of the convolution of the impulse response H with the excitation vector c.sub.i. When the error function is used as the selection function, Equation (1) is evaluated for each excitation vector to determine the optimal c.sub.i, and hence the desired index i. The vector quantity Hc.sub.i is the convolution of the impulse response of the weighted synthesis filter with the excitation vector c.sub.i, and therefore represents the excited weighted synthesized speech segment S.sub.i as shown in FIG. 1, which is the output of the weighted synthesis filter. A measure of similarity of the excited weighted synthesized speech segment S.sub.i and the target speech sample t.sub.w is their cross-correlation, t.sub.w.sup.T .multidot.Hc.sub.i. This is a scalar quantity, and the higher its value, the closer the excited weighted synthesized speech segment S.sub.i is to the target speech sample t.sub.w, and the better the excitation vector c.sub.i is for synthesizing the output speech sample. The numerator of the right-hand side expression in Equation (1) is the square of the cross-correlation of the excited weighted synthesized speech segment and the target speech sample. The denominator of the right-hand side expression in Equation (1) represents the energy term of the excited weighted synthesized speech segment S.sub.i. Note that the convolution of H and c.sub.i is an important operation which appears in several places in the calculation of .epsilon..sub.i.

Usually, CELP encoders utilize a pair of codebooks: an adaptive codebook and a fixed stochastic codebook. The excitation vectors of the fixed stochastic codebook are constant, whereas those of the adaptive codebook are updated by the encoder to accommodate the particular characteristics of the current target speech waveform. In analyzing a target speech waveform segment, an excitation vector is selected from each codebook. The two excitation vectors are combined in a weighted linear fashion and then sent as an input to the weighted synthesis filter. The procedure for selecting the optimum excitation vector as discussed above and illustrated in FIG. 1, and equivalently manifest in Equation (1), must be carried out for each of the codebooks.

Unfortunately, intensive numerical computation is needed to evaluate Equation (1), and so the processing required for codebook searching presents a major obstacle to improved CELP performance. Therefore, this is an area of interest in the field. For example, "Real-Time Vector Excitation Coding of Speech at 4800 BPS" by Davidson et al. (in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), April, 1987, pages 2189-2192) explores issues as the use of small, optimized codebooks that are easier to search, and presents an approximation for the evaluation of the energy term as given in Equation (1) by an autocorrelation approach which requires reduced computation U.S. Pat. No. 5,265,190 discloses a method of simplifying the convolution computation in the cross-correlation terms for adaptive codebook searching. While improvements such as these have been useful in reducing the complexity of codebook searching, however, the computation is still intensive, and moreover does not address some of the specific needs of fixed stochastic codebook searching. For example. U.S. Pat. No. 5,265,190 does not disclose methods for fixed stochastic codebook searches, and, moreover, the method disclosed therein applies only to the cross-correlation term but not to the energy term.

Thus there is a recognized need for, and it would be advantageous to have, methods of further reducing the amount of processing needed to select the optimum excitation vector from a codebook, in particular for a CELP encoder that has both a fixed stochastic codebook as well as an adaptive codebook. The innovation of the present invention attains this goal for a certain class of CELP encoders with both an adaptive codebook and a fixed stochastic codebook. In addition, CELP techniques currently attain a very high degree of perceptual fidelity, and it is desired to retain this fidelity while making improvements to the CELP process itself. Therefore, a further goal realized by the present invention is the improvement of processing efficiencies without the introduction of any perceptible distortion or other degradation in the quality of the reconstructed speech.

It is possible to reduce amount of processing required to calculate values of .epsilon. in Equation (1) for a certain class of CELP encoders, specifically, those encoders for which there is a plurality of fixed stochastic codebook subframes corresponding to a single adaptive codebook subframe. The innovation of the present application applies to this particular class of CELP encoders, hereinafter denoted by the term "compacted codebook CELP encoders". The present application discloses a method whereby the processing required to calculate values of .epsilon. may be reduced by calculating energy terms and convolution terms only at the beginning of each adaptive codebook subframe and storing them in an adaptive energy lookup table.

Therefore, according to the present invention there is provided a compacted codebook CELP encoder having a weighted synthesis filter with an impulse response, an adaptive codebook, and a fixed stochastic codebook containing excitation vectors, such that a plurality of fixed stochastic codebook subframes corresponds to a single adaptive codebook subframe, the compacted codebook CELP encoder including an adaptive energy lookup table storing a plurality of values of at least one function of the convolution of the impulse response of the weighted synthesis filter with the excitation vectors of the fixed stochastic codebook.

Furthermore according to the present invention there are provided additional methods using linear interpolation to reduce the amount of computation necessary to calculate the values for the adaptive energy lookup table. In this method the values of Hc.sub.i are calculated only once per adaptive codebook subframe, and the values for the adaptive codebook subframes are derived by interpolating the calculated values according to a linear formula.

In addition the present invention discloses a simplified method of calculating the cross-correlation terms for a fixed stochastic codebook which involves a de-convolution operation instead of a convolution operation. Once the de-convolution is done, it requires only vector multiplication instead of matrix multiplication to calculate the cross-correlation, thereby simplifying the computations.

The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein:

FIG. 1 is a flowchart showing the prior art procedure to search for the optimum excitation vector in a stochastic codebook for a given target speech sample.

FIG. 2 illustrates an example of the relationship between prior art frames, adaptive codebook subframes, and fixed stochastic codebook subframes for compacted codebook CELP encoder.

FIG. 3 illustrates an adaptive energy lookup table for a compacted codebook CELP encoder.

FIG. 4 illustrates a reduced adaptive energy lookup table for a compacted codebook CELP encoder.

FIG. 5 is a flowchart illustrating conceptually how the adaptive energy lookup table is used to select the optimum excitation vector from a fixed stochastic codebook.

The present invention is of a method for reducing the computation needed to select the optimum excitation vector from the fixed stochastic codebook of a compacted codebook CELP encoder. The optimum excitation vector is the one having the maximum normalized cross-correlation with a weighted target speech sample, as given in Equation (1). The cross-correlation is normalized by dividing it by the energy term.

There is a property of compacted codebook CELP encoders which is useful in reducing the computation required to search the fixed stochastic codebook. In addition to the variability of the adaptive codebook excitation vectors versus the static nature of the fixed stochastic codebook excitation vectors, the fixed stochastic codebook for this class of CELP encoders has a smaller subframe than that of the adaptive codebook. An adaptive codebook subframe is sometimes referred to as a "pitch subframe," and a fixed stochastic codebook subframe is sometimes referred to as a "codebook subframe," but for clarity, the present application will use the terms "adaptive codebook subframe" and "fixed stochastic codebook subframe," respectively. As an example of typical sampling practices, an adaptive codebook subframe may contain 40 samples (representing 5 msec of speech at a sampling rate of 8 KHz), whereas the fixed stochastic codebook subframe may contain only 10 samples (representing 1.25 msec of speech at a sampling rate of 8 KHz). Recall that for compacted codebook CELP encoders, there is a plurality of fixed stochastic codebook subframes corresponding to a single adaptive codebook subframe. The present innovation makes use of this to reduce the real-time processing requirements in selecting the optimum excitation vector from the fixed stochastic codebook.

Referring once again to FIG. 1, which illustrates conceptually how the optimum excitation vector is selected, target speech sample 14 t(n) is processed by weighting filter 16 which is a function of the LPC, to yield a weighted target speech sample t.sub.w (n). Each excitation vector c.sub.i of codebook 10 is processed by weighted synthesis filter 12 to result in a weighted synthesized speech segment S.sub.i (n), which is compared against the weighted target speech sample by comparator 18, whose output is the difference t.sub.w (n)-S.sub.i (n), which is the error vector E(n). Error computation 20 computes the mean squared error over the error vector for each codebook index i. The index i whose c.sub.i has minimal mean squared error is the selected index.

For a compacted codebook CELP encoder, let m represent the number of adaptive codebook subframes in each frame, and let n represent the number of fixed stochastic codebook subframes corresponding to a single adaptive codebook subframe. FIG. 2. to which reference is now made, shows this situation for an example of a prior art compacted codebook CELP encoder in which a frame 30 consists of 160 samples, an adaptive codebook subframe 32 consists of 40 samples, and a fixed stochastic codebook subframe 34 consists of 10 samples. In this example, there are therefore m=4 adaptive codebook subframes in each frame, and n=4 fixed stochastic codebook subframes corresponding to ever single fixed stochastic codebook subframe.

For a compacted codebook CELP encoder, it is noted that the LPC's are updated for each adaptive codebook subframe 34, and the selected excitation vector c.sub.i changes for each fixed stochastic codebook subframe 34. The impulse response matrix H, however, changes only every adaptive codebook subframe 32. Therefore, since the fixed stochastic codebook itself (the set of excitation vectors c.sub.i) is constant, the set of possible terms in the denominator of the right-hand side of Equation (1). Hc.sub.i, will be constant for any given adaptive codebook subframe 32, and is therefore constant over n fixed stochastic codebook subframes 34. To exploit this fact, the present invention innovates an adaptive energy lookup table associated with the impulse response of a weighted synthesis filter and the excitation vectors of a fixed stochastic codebook. This association is such that the adaptive energy lookup table stores the N values of at least one function of the convolution Hc.sub.i and the energy term .parallel.Hc.sub.i .parallel..sup.2 applicable to each adaptive codebook subframe 32, and these values may be used to evaluate a function which determines the selection of the optimum excitation vector from the fixed stochastic codebook for the n corresponding fixed stochastic codebook subframes 34. An example of such a function is the function .epsilon..sub.i in Equation (1). Note that an adaptive energy lookup table will be associated with the impulse response of a particular weighted synthesis filter and the excitation vectors of a particular fixed stochastic codebook. Through the use of the adaptive energy lookup table, the set of energy terms for substitution into the denominator of the right-hand side of Equation (1) and the set of convolution terms for evaluating the cross-correlation in the numerator of the right-hand side of Equation (1) need be computed only m times per frame, rather than mn times per frame, thereby reducing the computation needed.

In a preferred embodiment of the present invention, an adaptive energy lookup table contains N entries, each entry corresponding to exactly one of the excitation vectors c.sub.i in the fixed stochastic codebook, and having the same index i. Each c.sub.i is convolved with H to yield Hc.sub.i, and this is used to calculate the value .parallel.Hc.sub.i .parallel..sup.2. These are placed into the adaptive energy lookup table at index i. This is illustrated conceptually in FIG. 3. Column 40 of the table contains the index i. Column 42 contains the convolution Hc.sub.i corresponding to the index i, and column 44 contains the energy term values .parallel.Hc.sub.i .parallel..sup.2 corresponding to index i. Note that the convolution Hc.sub. i is a vector, whereas the energy .parallel.Hc.sub.i .parallel..sup.2 is a scalar quantity. Furthermore, note that the convolution Hc.sub.i is a by-product of calculating the energy term .parallel.Hc.sub.i .parallel..sup.2. To use this embodiment of the present invention to calculate a selection function such as .epsilon..sub.i as in Equation (1), it is necessary to retrieve the convolution vector Hc.sub.i from the adaptive energy lookup table and multiply it by the transpose of the target speech sample t.sub.w.sup.T to obtain the cross-correlation. This value is then squared and normalized by dividing it by the energy term .parallel.Hc.sub.i .parallel..sup.2 from the adaptive energy lookup table to obtain .epsilon..sub.i.

In another embodiment of the present invention, an adaptive energy lookup table may be reduced to contain only a single column of values related to both the convolution and the energy terms. This is illustrated conceptually in FIG. 4 column 40 contains the index i, as in FIG. 3. In this particular embodiment, column 46 contains the normalized convolution terms, which are the vectors Hc.sub.i divided by the energy term .parallel.Hc.sub.i .parallel..sup.2. Such a reduced adaptive energy lookup table cannot be used to calculate values of .epsilon..sub.i as given in Equation (1), because the normalization is applied directly to the convolution prior to calculating the cross-correlation. However, a reduced adaptive energy lookup table can be used to calculate other functions which can serve as measure of the suitability of an excitation vector c.sub.i in synthesizing reconstructed speech, such that selecting c.sub.i based on a maximum of such a function approximates the c.sub.i based on a maximum of .epsilon..sub.i. For example, the reduced adaptive energy lookup table can be used to calculate a selection function of the form: ##EQU2## where the maximum .phi..sub.i serves to identify the optimum excitation vector c.sub.i. The selection function of Equation (2) will not select precisely the same c.sub.i as that of Equation (1), because the denominator is .parallel.Hc.sub.i .parallel..sup.4 instead of .parallel.Hc.sub.i .parallel..sup.2. If, however, the excitation vectors are selected such that .parallel.Hc.sub.i .parallel..sup.2 does not vary significantly over the fixed stochastic codebook for typical impulse response matrices H, then this function will select c.sub.i 's which perceptually approximate those which would be selected by Equation (1).

The adaptive energy lookup tables are illustrated in FIG. 3 and FIG. 4 only conceptually. In practice, since the tables are normally to be implemented in data memory, it is not necessary to store the index i explicitly, such as in a column 40, as the index can be implicit in the address locations of the entries relative to the starting locations of the tables.

From a consideration of the embodiments discussed above it will be appreciated that many variations of the adaptive energy lookup table are possible. As discussed above, for example, other functions besides .epsilon..sub.i as in Equation (1) are possible, for use in selecting the optimum excitation vector. Therefore, an adaptive energy lookup table in its most general form stores values of at least one specified function of the convolution Hc.sub.i corresponding to the excitation vectors c.sub.i of the fixed stochastic codebook.

FIG. 5 illustrates conceptually how the adaptive energy lookup table is used in the selection of the index i corresponding to the optimum excitation vector c.sub.i. The procedure of FIG. 5 commences at the start of a fixed stochastic codebook subframe and determines the index i corresponding to the optimum excitation vector c.sub.i for that fixed stochastic codebook subframe and for each following fixed stochastic codebook subframe. Decision point 50 first determines whether it is necessary to load the adaptive energy lookup table with new values, depending on whether the encoder is also at the start of an adaptive codebook subframe. Note that decision point 50 is reached at the start of every fixed stochastic codebook subframe. Refer to FIG. 2, which illustrates the relationships between frames, adaptive codebook subframes, and fixed stochastic codebook subframes for a compacted codebook CELP encoder. It is seen that the start of every adaptive codebook subframe coincides with the start of a fixed stochastic codebook subframe, but not every fixed stochastic codebook subframe coincides with the start of an adaptive codebook subframe. If the encoder is at the start of an adaptive codebook subframe, step 52 computes the impulse response matrix H, and step 54 fills the adaptive energy lookup table with values for each index i. If, however, the encoder is not at the start of an adaptive codebook subframe, step 52 and step 54 are skipped. In either case, the adaptive energy lookup table will have a complete set of applicable cross-correlation terms and energy terms for the excitation vectors of the fixed stochastic codebook for the current fixed stochastic codebook subframe. Next, step 56 is performed to calculate the transpose of the weighted target speech sample, t.sub.w.sup.T. An iterative loop 58 goes through the adaptive energy lookup table and retrieves values of Hc.sub.i and .parallel.Hc.sub.i .parallel..sup.2 in step 60, and then uses them to calculate .epsilon..sub.i by evaluating, Equation (1) in step 62. When iterative loop 58 is complete, the maximum .epsilon..sub.i is determined and the optimal index i is output in step 64.

The flowchart of FIG. 5 presents the procedure conceptually, and in practice it may be implemented in a number of different ways with variations. For example, it might be more efficient to store Hc.sub.i and .parallel.Hc.sub.i .parallel..sup.2 into the adaptive energy lookup table as a by-product of the first iteration of iterative loop 58 when calculating the .epsilon..sub.i 's, rather than to compute them, store them, and then have to retrieve them again, in the order conceptually illustrated by FIG. 5. Likewise, efficiency would be improved by incorporating step 64, which finds the maximum .epsilon..sub.i, directly into iterative loop 58 rather than to search for the maximum subsequent to the execution of iterative loop 64, in the order conceptually illustrated by FIG. 5. To find the maximum .epsilon..sub.i outside iterative loop 58 would require storing all the values of .epsilon..sub.i in a separate table and then iterating through that table looking for the maximum. Various techniques for optimizing such calculations are well-known in the art.

In a preferred embodiment of the present invention, further savings in computation may be realized by applying linear interpolation in the computation of the convolution Hc.sub.i. Let the current frame be represented by the subscript j and the number of the current adaptive codebook subframe be represented by the integer k, such that 1.ltoreq.k.ltoreq.m. Then the values of Hc.sub.i for the adaptive energy lookup table corresponding to the adaptive codebook subframe are given by: ##EQU3##

That is, the values of Hc.sub.i for an adaptive codebook subframe are weighted sums of the values calculated for the previous frame, denoted by {Hc.sub.i }.sub.j-1 and those calculated for the current frame, denoted by {Hc.sub.i }.sub.j. In this case, for example, the weighted sums are linear combinations as depicted in Equation (3). Once again, since the fixed stochastic codebook (the set of excitation vectors c.sub.i) is constant, only H will change from one adaptive codebook subframe to another. Therefore, when interpolation according to Equation (3) is performed, the computation of {Hc.sub.i } need be done only once per frame instead of m times per frame. The adaptive energy lookup table containing the values of .parallel.Hc.sub.2 .parallel..sup.2 can thus be updated with minimal computation for most of the fixed stochastic codebook subframes. Linear interpolation does not provide complete accuracy in calculating the convolutions, but the results are within approximately 98% of the correct values. The inaccuracy of linear interpolation is imperceptible to the human ear.

In another embodiment of the present invention, a transformation is made in the computation of the cross-correlation when searching for the optimum fixed stochastic codebook excitation vector. The cross-correlation is represented in the numerator in the right-hand side of Equation (1):

Referring again briefly to FIG. 1, it can be seen that the term Hc.sub.i is a vector which corresponds to the physical filtering of c.sub.i to yield the output weighted synthesized speech segment S.sub.i from weighted synthesis filter 12. The cross-correlation is the vector dot product of the filtered target speech sample with S.sub.i. Calculating this for each c.sub.i in the fixed stochastic codebook requires a matrix multiplication for each c.sub.i to obtain S.sub.i =Hc.sub.i, and then a vector multiplication, t.sub.w.sup.T .multidot.S.sub.i, to obtain the cross-correlation. This set of operations must be repeated for each fixed stochastic codebook subframe. If, on the other hand, Equation (4) is written as:

then only a vector multiplication, instead of a matrix multiplication, is needed for each c.sub.i to obtain the cross-correlation. A matrix multiplication to calculate the transpose vector t.sub.w.sup.T H need be done only once per fixed stochastic codebook subframe, instead of N times per fixed stochastic codebook subframe, resulting in a net savings of N-1 matrix multiplications per fixed stochastic codebook subframe. The transpose vector resulting from the operation t.sub.w.sup.T H is an innovative artifice to reduce the complexity of the calculations for the fixed stochastic codebook. The present application uses the term "transpose convolution" to denote the transpose of a vector multiplied by the matrix representing an impulse response; an example of a transpose convolution is the transpose vector t.sub.w.sup.T H.

While the invention has been described with respect to a limited number of embodiments, it will be appreciated that variations and modifications of the invention may be made.