Patent Publication Number: US-5893061-A

Title: Method of synthesizing a block of a speech signal in a celp-type coder

Description:
DESCRIPTION 
     This invention relates to speech coding, particularly to a method of synthesizing a block of a speech signal in a CELP-type (Code Excited Linear Predictive) coder, the method comprising the steps of applying an excitation vector to a synthesizer filter of the coder, said excitation vector consisting of two gain normalized components derived, on the one hand, from an adaptive codebook and from a stochastic codebook, on the other hand. 
     Efficient speech coding methods are continuously developed. The principles of Code Excited Linear Prediction (CELP) are described in an article of M. R. Schroeder and B. S. Atal: &#34;Code-Excited Linear Prediction (CELP): High Quality Speech at Very Low Bit Rates&#34; Proceedings of the IEEE International Conference of Acoustics, Speech and Signal Processing--ICASSP, Volume 3, pp 937-940, March 1985. The basic structure of the CELP-type speech coders developed up to date is quite similar. A LPC synthesis filter (LPC=Linear Predictive Coding) is excited by so-called &#34;adaptive&#34; and &#34;stochastic&#34; excitations. The speech excitation vector is scaled by its respective gain and the gains are often Jointly optimized. 
     The CELP approach offers good speech quality at low bit rates, however, degradations of speech quality can be heard if the synthesized speech is compared with the original (band limited) speech, especially at bit rates below 16 kb/sec. One reason is the need to restrict the computational requirements of the search for the &#34;best&#34; excitation to reasonable values in order to make the algorithm practical. Therefore many CELP-type coders use simplified structures for the codebooks as already indirectly suggested by Schroeder/Atal in the said basic article. Such methods cause some degradations in speech quality. It is known that the speech quality is strongly related to the &#34;quality&#34; of the stochastic codebook(s) which give(s) the innovation sequence for the speech signal to be synthesized. Although it is possible to implement very good full search codebooks at reasonable data rates, it is still impossible to implement a full search in real time on existing digital signal processors. For overcoming this problem a reasonable approach is a pre-selection of a relatively small number of &#34;good&#34; code vector candidates, so that the codebook search can be done in real time and the speech quality is retained. 
     So-called trained codebooks can have adavantages over algebraic codebooks in terms of speech quality, nevertheless, in a lot of today&#39;s CELP-type speech coders algebraic codebooks are employed to provide the stochastic excitation to reduce complexity and memory requirements. 
     FIG. 1 shows the typical structure of an &#34;analysis-by-synthesis-loop&#34; of a CELP-type speech codec. A common scheme is that the synthesis filter, i.e. blocks 1 and 2, providing the spectral envelope of the speech signal to be coded is excited with two different excitation parts. One of them is called &#34;adaptive excitation&#34;. The other excitation part is called &#34;stochastic excitation&#34;. The first excitation part is taken from a buffer where old excitation samples of the synthesis filter are stored. Its task is to insert the harmonic structure of speech. The second excitation part is a so-called stochastic excitation which rebuilds the noisy components of the signal. Both excitation parts are taken from &#34;codebooks&#34;, i.e. from an adaptive codebook 3 and from a stochastic codebook 4. The adaptive codebook 3 is time variant and updated each time a new excitation of the synthesis filter has been found. The stochastic codebook 4 is fixed. A synthetic speech signal is generated already in the speech encoder by a process called &#34;analysis-by-synthesis&#34;. Codebooks 3, 4 are searched for the vectors which scaled and filtered versions (gains g1, g2) give the &#34;best&#34; approximation of the signal to be transmitted as &#34;reconstructed target vector&#34;. The &#34;best&#34; excitation vectors are chosen according to an error measure (block 5) which is computed from the perceptual weighted error vector In block 6. 
     In theory, the approximation of the target vector can be performed quite well in terms of perception even at relatively low bit rates. In practice, however, there are limitations namely, as already mentioned, the time required to perform the codebook search and the memory needed to store the codebooks. Therefore, only suboptimal search procedures can be applied to keep the complexity low. The codebooks 3, 4 are searched for the &#34;best&#34; code vector sequentially and each single codebook search is performed also suboptimal to some extent. These limitations can cause a perceptible decrease in speech quality. Therefore, a lot of work has been done in the past to find the excitation with reasonable effort while retaining high speech quality. One approach for simplifying the search procedures is described in EP-A-0 515 138. 
     Typically, CELP coders are driven by the stochastic excitation, since the adaptive codebook 3 only depends on vectors previously chosen from the stochastic codebook 4. For this reason, the content of the stochastic code book 4 is not only important for rebuilding noisy components of speech but also for the reproduction of the harmonic parts. Therefore, most CELP-type coders mainly differ in the stochastic excitation part. The other parts are often quite similar. 
     As already mentioned there are two different stochastic codebook approaches, i.e. trained codebooks and algebraic codebooks. Trained codebooks often have candidate vectors with all samples being nonzero and different in amplitude and sign. In contrast, algebraic codebooks usually have only a few nonzero samples and often the amplitudes of all nonzero samples are set to one. A full search in a trained codebook takes more complexity than a full search in an algebraic codebook of the same size. In addition, there is no memory required to store an algebraic codebook, since the candidate vectors can be constructed online during the codebook search is performed. Therefore, an algebraic codebook seems to be the better choice. However, to ensure good reproduction of speech, a &#34;large&#34; number of different codevector candidates including speech characteristics is needed. Due to this, trained codebooks have advantages over algebraic ones. On the other hand, the &#34;best&#34; candidate vector should be found with &#34;small&#34; effort. These are contrary requirements. 
     SUMMARY OF THE INVENTION 
     It is an object of the invention to make trained codebooks applicable by a new process of preselecting a reasonable number of candidate codevectors in order to limit the &#34;closed-loop&#34; search for the best codevector to a &#34;small&#34; subset of candidate codevectors. 
     It is a further object of the invention to do such preselection with limited efforts such that the following codebook search applied to the preselected candidate vectors takes clearly less complexity than a full search in the codebook. 
     As a first approach to the invention such preselection measure is derived from an &#34;ideal&#34; RPE sequence (RPE=Regular Pulse Excitation). 
     According to the invention a method for synthesizing a block of a speech signal in a CELP-type coder comprises the step of applying an excitation vector to a synthesizing filter of the coder, said excitation vector consisting of two gain normalized components derived, on the one hand from an adaptive codebook and from a stochastic codebook, on the other hand, said method being characterized in that for limiting the computational effort of the stochastic codebook components search, an ideal regular pulse excitation sequence is computed from a target vector derived from a weighted speech sample signal and the impulse response of the synthesis filter followed by determination of four parameters therefrom, namely 
     the position of the first nonzero pulse of the ideal RPE excitation sequence, 
     the position of the maximum pulse within said RPE excitation sequence, 
     the overall sign of the RPE sequence defined as the respective sign of said maximum pulse, and 
     the position of the corresponding part of the pulse codebook. as the position of the maximum pulse, 
     said four parameters being transmitted to the speech decoder. 
     The starting point of the invention is the Regular Pulse Excitation (RPE) which Is principally known since the early eighties. The invention, however, takes specific advantages from this approach. 
     In the following, the computing of an ideal RPE is briefly described. For more details specific reference is made to a paper by Peter Kroon: &#34;Time-domain coding of (near) toll quality speech at rates below 16 kb/s&#34;, Delft University of Technology, March 1985. 
     The Regular Pulse Excitation (RPE) 
     Assume the excitation vector to be N samples long. In general, each of those samples has different sign and amplitude. In practice, it is necessary either to limit the number of codevectors and/or to reduce the number of nonzero pulses in the excitation vector in order to make codebook search possible with today&#39;s signal processors. One possibility to reduce the number of nonzero pulses is to employ RPE. RPE means, that the spacing between adjacent nonzero pulses is constant. If for example every second. excitation pulse has nonzero amplitude, there are two possibilities to place N/2 nonzero pulses in a vector of the length N. The first, third, fifth, . . . pulse is nonzero or the second. fourth, sixth, . . . pulse is nonzero. If the number of nonzero pulses is L, L&lt;=N, every (N/L)-th pulse is nonzero and there are (N-(N/L)*(L-1)) possibilities to place L nonzero pulses as RPE sequence in a vector of length N (both divisions are integer-divisions). That means the first nonzero pulse can be located at (N-(N/L)*(L-1)) different positions. The best set of pulse amplitudes for those different possibilities can be computed in a straightforward manner. The following variables are defined: 
     
         ______________________________________
p      target vector to rebuild, (1*N)-Matrix
h      impulse response of synthesis filter, (1*N)-Matrix
H      impulse response matrix, (N*N)-Matrix
M      matrix which gives the contribution of the nonzero pulses
       in excitation vector, (N*L)-Matrix
b      vector containing L non zero pulse amplitudes and signs,
       (1*L)-Matrix
c      excitation vector, (1*N)-Matrix
c&#39;     filtered excitation vector, (1*N)-Matrix
e      difference vector between target vector and filtered code-
       vector (error vector)
E      error measure.
______________________________________
 
    
     The excitation vector is given by 
     
         c=b·M, 
    
     the matrix product of vector b and matrix M. Its filtered version is 
     
         c&#39;=b·M·H. 
    
     The error to be minimized is the difference between the target vector and this signal. 
     
         e=p-c&#39; 
    
     The error measure is the simple Euclidean distance measure. 
     
         E=e·e.sup.T 
    
     Replacing e by the above given equations, we obtain 
     
         E=p·p.sup.T -2·H.sup.T ·M.sup.T ·b.sup.T +b·M·H·H.sup.T ·M.sup.T ·b.sup.T. 
    
     The partial derivation ##EQU1## leads to the &#34;best&#34; set of amplitudes and signs which are computed by 
     
         b.sup.T =p·H.sup.T ·M.sup.T ·(M·H·H.sup.T ·M.sup.T)-.sup.1. 
    
     The impulse response matrix H looks like 
     
         ______________________________________
        h(0)   h(1)      h(2) h(3)   ..  h(N-1)
        0      h(0)      h(1) h(2)   ..  h(N-2)
H =     0      0         h(0) h(1)   ..  h(N-3)
        0      0         0    h(0)   ..  h(n-4)
        ..     ..        ..   ..     ..  ..
        0      0         0    0      0   h(0)
______________________________________
 
    
     If, for example, L=N/2, M is structured as shown below for the first and second possibility to place pulses, respectively. 
     
         ______________________________________
     1      0      0    0   0    0    0    ..  ..   0
     0      0      1    0   0    0    0    ..  ..   0
M.sup.(1) =
     0      0      0    0   1    0    0    ..  ..   0
     ..     ..     ..   ..  ..   ..   ..   ..  ..   ..
     0      0      0    0   0    0    0    ..  1    0
     0      1      0    0   0    0    0    ..  ..   0
     0      0      0    1   0    0    0    ..  ..   0
M.sup.(2) =
     0      0      0    0   0    1    0    ..  ..   0
     ..     ..     ..   ..  ..   ..   ..   ..  ..   ..
     0      0      0    0   0    0    0    ..  ..   1
______________________________________
 
    
     In general, each row of M has just a single element being 1, the other elements are zero. The n-th row gives the position of the n-th pulse. If there are m possibilities to place L pulses as RPE sequence, there are m different versions of the matrix M. With m different matrixes M, there are also m different sets of amplitudes. The set which provides the smallest error E is denoted as &#34;ideal&#34; RPE sequence. 
     This method applied here may be called &#34;hybrid&#34; since the preselection of codevectors to be tested in the &#34;analysis-by-synthesis-loop&#34; is done outside of said loop. The part of the codebook to which those loop search is applied is determined before the analysis-by-synthesis-loop is entered. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     The new synthesizing method according to the invention and adavantageous examples therefore are described in detail in the following with reference to the drawings in which 
     FIG. 1 shows a speech analysis-by-synthesis-loop already explained above; 
     FIGS. 2(a) and 2(b) serve to explain a stochastic pulse codebook in its relation to an excitation generator; 
     FIG. 3 gives an example for L=N/2 pulses in an ideal RPE sequence in accordance with the invention; 
     FIG. 4 explains the functioning of an excitation generator; 
     FIG. 5 depicts an example for a speech encoder as used for performing the speech synthesizing method according to the invention; and 
     FIGS. 6(a) and 6(b) show for the reason of completeness of description an example of the speech decoder as used in connection with the speech encoder of FIG. 5. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     At first, the RPE based preselection of a stochastic codebook part and the derivation of the pulse codebook are described with reference to FIGS. 2(a), 2(b), 3 and 4. 
     The maximum pulse position of an &#34;ideal&#34; RPE sequence is used as preselection measure to limit the closed loop codebook search to a &#34;small&#34; number of candidate vectors. 
     Assume the codebook structure given in FIG. 2(a) to be available. There is a pulse codebook having L parts (L=number of nonzero samples). Codebook part i (i=1,2, . . . ,L) consists of M i  vectors of L samples. These vectors are candidate vectors for the nonzero pulses of an RPE sequence. The n-th sample of all vectors of the n-th part has maximum amount. The L parts are joined together to one codebook. 
     FIG. 2(b) shows as example for codebook part 2, how the preselection procedure works and a code vector is constructed. The &#34;ideal&#34; RPE sequence is computed as depicted in keywords in FIG. 2(a) and FIG. 2(b). The position of the first nonzero pulse, the maximum pulse position and the overall sign are taken from the &#34;ideal&#34; RPE. If the maximum pulse is negative, the overall sign is negative. Otherwise the overall sign is positive. The overall sign is required since the pulse codebook 4a contains only codevectors with positive maximum pulse. 
     FIG. 3 shows the derivation of the &#34;position of a first nonzero pulse&#34;, the &#34;maximum pulse position&#34; and the &#34;overall sign&#34; from an example RPE sequence. FIG. 4 gives an example how the excitation generator 14 of FIG. 2(b) works. If the ideal RPE&#39;s maximum pulse is negative, all pulses of the pulse vector to be tested are multiplied by -1. If the n-th nonzero sample of the ideal RPE sequence has maximum amount, the n-th part of the pulse codebook is searched for the best candidate vector. That means that as a significant advantage of the invention, the codebook search is applied to Just (100/(L))% of all candidate vectors. 
     As a result, the following parameters are transmitted to the speech decoder: 
     position of the first nonzero pulse, 
     position of the maximum pulse (=codebook part to which closed-loop search is applied), 
     overall sign, 
     position in corresponding part of the pulse codebook. 
     The speech codec in which the above described scheme shall be introduced is run with a sufficient set of training speech data in order to derive the pulse codebook described before. To generate the stochastic excitation during the training process. the following is done: 
     The ideal RPE sequence is computed from the target vector to be rebuilt and the impulse response of the synthesis filter. The position of the first nonzero pulse, the maximum pulse position and the overall sign are taken from the ideal RPE as given above. 
     If the n-th nonzero sample of the ideal RPE sequence has maximum amount, the normalized RPE sequence is stored in the n-th database. The normalization is performed in two steps. In the first step, the RPE sequence is normalized such that the maximum pulse has positive value. In the second step. the sequence obtained after the first step is divided by the energy of the target vector to which the RPE sequence belongs. This is done to remove the influence of the loudness of the signal from the codebook entries. In this way, L databases are obtained. The databases contain &#34;normalized waveforms&#34;. Therefore, also the codebooks trained based on the databases contain &#34;normalized waveforms&#34;. 
     For each database, codebook training is performed separately according to the LBG-algorithm. (For details see description in Y. Linde, A. Buzo, R. M. Gray: &#34;An Algorithm for Vector Quantizer Design&#34;, IEEE Transactions on Communications, January 1980). 
     Finally, the different codebooks are joined together such that the n-th part of the overall codebook contains candidate vectors where the n-th sample has maximum amount. 
     An example of the speech codec which employs the new stochastic codebook scheme is described below with reference to FIG. 5. Note that the block diagram or scheme doesn&#39;t depend on this codec. It can also be used with other CELP-type speech codecs. 
     The synthesis filter shown in FIG. 5 gives the spectral envelope of the signal. Another interpretation is that the short term correlation of the signal is given by this filter. This filter is excited by vectors taken from codebooks which contain a reasonably large number of candidate vectors. One vector is taken from the adaptive codebook 3 where old excitation vectors are stored. This excitation part rebuilds the harmonic structure of speech (or the long term correlation of the speech signal) and is called the &#34;adaptive excitation&#34;. The second part of the excitation is taken from the stochastic codebook 4. This codebook introduces the noisy parts of the synthesized speech signal or the innovation of the signal which cannot be provided by linear prediction. 
     With reference to FIG. 5, the computations are divided into frame and subframe processings. A speech frame consists of N frame  speech samples. The codec delay is N frame  times the sample period. Each frame has k subframes of the length N frame  /k samples. Parameters which are computed once per frame are called &#34;frame parameters&#34;. Parameters which are computed for each subframe are called &#34;subframe parameters&#34;. First, the frame parameters are computed. These parameters are 
     LPC&#39;s (Linear Predictive Coefficients) derived via blocks 21, 22, 23, 24, 25 and 28 (explained later) and 
     loudness derived via blocks 21, 26, 27 and 28 (explained later). 
     The LPC&#39;s out of block 28 describe the spectral envelope and the loudness value gives the loudness of the signal in the current speech frame. Then, the excitation of this synthesis filter is calculated for each subframe. The excitation is described by the subframe parameters 
     position in adaptive codebook 3, 
     position in pulse codebook 4a, 
     maximum pulse position in block 15, 
     first nonzero pulse position in block 15, 
     overall sign in block 15, and 
     position in gain codebook 16. 
     These parameters are transmitted to the decoder (see FIG. 6b). 
     Before entering the LPC-analysis stage, a current speech frame is windowed in block 21. LPC-analysis 22 is performed via LEVINSON-DURBIN recursion. The LPC&#39;s are transformed into LSF&#39;s (Line Spectrum Frequencies) in block 23 and vector-quantized in block 24. For further use in the encoder the quantized LSF&#39;s are converted into quantized LPC&#39;s in block 25. The LPC&#39;s are interpolated with the LPC&#39;s of the previous speech frame in block 28. A loudness value is computed from the windowed speech frame in block 26. quantized in block 27 and interpolated with the loudness value of the previous frame In block 28. 
     Each speech subframe is weighted in block 20 to enhance the perceptual speech quality. From the weighted speech subframe, the zero input response of the synthesis filter 1 is subtracted in a first substractor 29. The resulting signal is called &#34;target vector&#34;. This target vector has to be rebuild by the &#34;analysis-by-synthesis-loop&#34;. The following computations are done for each subframe. 
     First, the adaptive excitation is taken from the adaptive codebook 3. It is scaled by the optimal gain g1 and subtracted from the target vector in a second subtractor 30. The remaining signal is to be rebuilt by the stochastic excitation. In accordance with the invention, the ideal RPE sequence is computed from the remaining signal to be rebuild and the impulse response of the synthesis filter. The position of the first nonzero pulse, the maximum pulse position and the overall sign are taken from the ideal RPE as described above. 
     The RPE sequence is computed once before the closed loop codebook search is started. If the n-th nonzero sample of the ideal RPE has maximum amount, the codebook part n is searched closed-loop for the best excitation vector in blocks 4a via 14. Finally, the excitation of the synthesis filter is computed from the stochastic and adaptive excitations and the respective gains g1, g2 and the adaptive codebook 3 is updated. 
     FIG. 6(a) and 6(b) show in block diagrams essential parts of the decoder. As in most analysis-by-synthesis-coders the operations to be performed (except post processing) are quite similar to those ones already performed in the corresponding encoder stages. Accordingly, a detailed description of the schemes of FIG. 6(a) and 6(b) is omitted. To decode the transmitted parameters just a few table look-ups are required to obtain the filter coefficients for loudness and excitation of the synthesis filter. 
     As shown in FIG. 6(b), the price to pay for the sake of bit rate needed to transmit the speech signal is that it cannot be reconstructed completely. Noisy components (coding noise) are introduced by the speech encoder which can be heard (more or less). To avoid annoying effects, post filtering is employed. The target is to suppress the coding noise while retaining the naturalness of the speech signal. In this codec a post filter 70 including long term and short term filtering is employed to increase the perceptual speech quality. 
     Summarizing the above, instead of applying the search for the stochastic excitation to all pulse vector candidates, a hybrid search technique is used. After computation of the ideal RPE sequence, firstly the position of first nonzero pulse and the position of the maximum pulse are computed in the &#34;ideal&#34; pulse vector. Second, the codebook search is performed. Since there is one pulse vector codebook for each position of the maximum pulse, only the pulse vector codebook belonging to this position has to be searched for the &#34;best&#34; codevector. This technique according to the invention reduces the computational requirements for finding the &#34;best&#34; stochastic excitation drastically compared with applying the codebook search to all pulse vector codebooks.