Speech Coding Algorithms: Foundation and Evolution of Standardized Coders

ENCODER AND DECODER 367 Input Frame / Perceptual Zero-input PCM subframe weighting response of speech segmentation m. f. s. f. filter LP Adaptive Gain analysis Impulse codebook codebook response of m. f. s. f. search search LPC LPC decoding Stochastic Gain encoder and codebook 1 decoder interpolation search Energy Energy Stochastic Total response, calculation and decoding and codebook 0 update of interpolation encoding search system’s state Stochastic Stochastic Adaptive Energy LPC codebook 1 codebook 0 codebook Gain index index index index index index Pack VSELP bit-stream Figure 13.2 Block diagram of the IS54 VSELP encoder (m. f. s. f. means modified formant synthesis filter). TABLE 13.2 Bit Allocation For the TIA IS54a VSELP Coder Parameter Number Resolution Total Bits per Frame per Frame LPC 10 6,5,5,4,4,3,3,3,3,2 38 Adaptive codebook index 4 7 28 Stochastic codebook 1 index 4 7 28 Stochastic codebook 0 index 4 7 28 Frame energy 1 5 5 Gain index 4 8 32 ——— Total 159 aData From Macres [1994], Table 2.

368 VECTOR SUM EXCITED LINEAR PREDICTION VSELP Unpack bit-stream Gain Energy LPC Excitation index index index codebook indices Gain Energy LPC decoding decoding and decoding and & computation interpolation interpolation Adaptive codebook Stochastic Formant codebook 0 synthesis filter Stochastic Postfilter codebook 1 Synthetic speech Figure 13.3 Block diagram of the IS54 VSELP decoder. 13.6 SUMMARY AND REFERENCES Eminent features of VSELP are presented in this chapter. It is shown that the coder is designed to have reduced computational load—fast search is realizable with the excitation codebooks. Limited memory cost is achieved with a finite set of basis vectors, providing also high robustness against channel errors. The IS54 outper- forms other standard CELP coders in quality, such as the FS1016 [Cox, 1995], although it operates at a higher bit-rate of 7.95 kbps. Thus, the IS54 is well suited for cellular telephony applications. As indicated in Section 13.1, the basis vectors from which the stochastic code- vectors are spanned contain white noise elements. It is possible to elevate the per- formance by further training the system using a large amount of speech data, with the objective of tuning the elements of the basis vectors in such a way that the total weighted error is minimized. For the case of the IS54, the optimal basis vectors are computed by solving the 14 basis vectors  40 samples/basis vector ¼ 560 simult- aneous equations, which are the results of taking the partial derivatives of the total weighted error with respect to each sample of each basis vector and setting them equal to zero. See Gerson and Jasiuk [1991] for additional information, where an

EXERCISES 369 increase of 13.41 to 14.05 dB in weighted segmental SNR after 16 iterations was reported. Major contributions of the IS54 coder can be summarized as follows:  First standardized medium bit-rate coder based on CELP.  Introduction of the concept of adaptive codebook, enabling closed-loop optimization of long-term prediction parameters.  Efficient implementation through the use of separate fixed codebooks with codevectors spanned by a small number of basis vectors.  Joint quantization of the gains associated with the excitation via VQ. The other two VSELP standards—GSM 6.20 and STD-27B—are based on simi- lar architecture, but with a differing number of stochastic codebooks and/or basis vectors. The coder works essentially the same way if only one stochastic codebook is present, leading to lower implementational cost and bit-rate with sacrifice in quality. Main features of the VSELP algorithm are described in Gerson and Jasiuk [1991]. See Macres [1994] for the actual implementation on a DSP platform. In DeMartino [1993], a quality measurement report is presented where three coders— GSM 6.10, IS54, and STD-27B—are compared. The conclusion is that the IS54 is better than the other two coders, providing higher perceptual quality. The IS54 coder was standardized by the TIA in approximately a year, beginning in early 1989. Due to insufficient time, the amount of testing was minimal and the coder suffers from a number of performance deficiencies that were never identified during testing, such as quality with background noise or music and tandem coding. The TIA attempted to repair the coder, but in 1994, discussion began about a total replacement [Cox, 1995]. The quest culminated in 1996 with the IS641 ACELP standard, operating at 7.4 kbps and described in Chapter 16. EXERCISES 13.1 Prove Lemma 13.1 by expanding the norm term and using the fact that yT z ¼ zT y ¼ 0 since y and z are orthogonal. 13.2 Let gN À 1 Á Á Á g2g1g0 denote a codeword in the N-bit Gray code, and let bN À 1 Á Á Á b2b1b0 designate the corresponding binary number, where the sub- scripts 0 and N À 1 denote the least significant and most significant digits, respectively. Then the ith digit gi can be obtained with gi ¼ bi È biþ1; 0 i N À 2; gNÀ1 ¼ bNÀ1; with È denoting the exclusive or operation [Sandige, 1990]. Using the above relations, find the 3-bit Gray code from the corresponding binary numbers.

370 VECTOR SUM EXCITED LINEAR PREDICTION 13.3 To convert from Gray code to binary, start with the most significant digit and proceed to the least significant digit. Then bi ¼ gi; if number of 1’s preceding gi is even; bi ¼ gi0; otherwise; with g0 denoting the logically inverted version of g. Using the rule, convert the 3-bit Gray code to binary. 13.4 The excitation gains are vector quantized as a three-dimensional vector containing the elements G, P2, and P1. To find the best codevector from the codebook, an error expression containing nine sum terms is used. These sum terms are denoted as g1 to g9. Note from the expression for g1 that the quantity rffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi À2 GðlÞ 1 À Pð2lÞ À Pð1lÞ must be evaluated for all index values l. The expression can be precomputed in an off-line fashion and stored in a codebook, recovered by the same index l. This will save valuable processing time when the gain codebook is searched; the price to pay is additional storage space. Following the same principle, evaluate the expressions for g2 to g9 and find out the terms that can be computed off-line and stored in a codebook. 13.5 Once the optimal gain codevector is found, the elements {G, P2, P1} must be converted to {b, g1, g0}. From the relations between these two sets of parameters, we can see that some quantities can be precomputed and stored in a codebook so as to save computational cost. For instance, in order to calculate b, we can precompute the quantity (GP2)1/2 and store them in a codebook. What can we do for g1 and g0? 13.6 Consider a VSELP coder without stochastic codebook 0; that is, the excitation is comprised of the adaptive codevector and one stochastic codevector. To quantize the excitation gains, a two-dimensional VQ is used, where the vector under consideration is {G, P2}, with rffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi b ¼ G Á P2 Á Ee R2 and sffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi g1 ¼ Gð1 À P2ÞEe: R1

EXERCISES 371 Find the error expression for this case that one can rely on to search the gain codebook. Express the answer as a function of G(l), P2ðlÞ, Ee, R1, R2, y1o, y2o, and u (see Section 13.4). 13.7 Gerson and Jasiuk [1991] propose using the ‘‘pitch prefilter’’ with system function HðzÞ ¼ 1 1 À bzÀT during decoding. The excitation signal going into the formant synthesis filter is first processed by this filter. The purpose of the filter is, as its name implies, to enhance the pitch periodicity of the excitation signal. How would you choose the parameters b and T of this filter? Justify your answer. 13.8 Find out the computational costs associated with the stochastic codebook search with and without the Gray code ordering scheme. How much is gained by deploying the Gray code ordering?

CHAPTER 14 LOW-DELAY CELP In the process of speech encoding and decoding, delay is inevitably introduced. Loosely defined, delay is the amount of time shift between the speech signal at the input of the encoder with respect to the synthetic speech at the output of the decoder, when the output of the encoder is directly connected to the input of the decoder. For schemes such as PCM and ADPCM (Chapter 6), the speech signal is encoded on a sample-by-sample basis: a few bits are found for each sample with the result transmitted immediately; the delay associated with these schemes is negligible. For many speech coders, such as CELP (Chapter 11), high compres- sion ratio is achieved by processing the signal on a frame-by-frame basis, thus requiring a buffering procedure consuming typically 20 to 30 ms, depending on the length of the frame. It is this buffering process associated with most low bit- rate coders that augment the overall delay. See Chapter 1 for a precise definition of coding delay. Delay is an important concern for real-time two-way conversations, and it basi- cally can be thought of as the time the sound takes to travel from speaker to listener. For an excessively large delay, that is, above 150 ms, the ability to hold a conversa- tion is impaired. The parties involved begin to interrupt or ‘‘talk over’’ each other because of the time it takes to realize the other party is speaking. When delay becomes high enough, conversations degrade to a half-duplex mode, taking place strictly in one direction at a time; hence, the lower the delay the better. Low delay is also highly desirable for typical telephone networks, since delay aggravates echo problems: the longer an echo is delayed, the more audible and annoying it is to the talker. Even though echo cancelers are normally incorporated, high delay makes the job of echo cancellation more difficult. 372 Speech Coding Algorithms: Foundation and Evolution of Standardized Coders. Wai C. Chu Copyright  2003 John Wiley & Sons, Inc. ISBN: 0-471-37312-5

STRATEGIES TO ACHIEVE LOW DELAY 373 There is always a price to pay for a certain attribute, and for the case of low delay there is no exception. The low-delay constraint is in conflict with other desir- able properties of a speech coder, such as low bit-rate, high quality, reduced com- putational cost, and robustness against channel errors. Therefore, delay reduction with minimum degradation of the good properties has been a great challenge to speech coding researchers. This chapter is devoted to the ITU-T G.728 LD-CELP coder, standardized in 1992. At a bit-rate of 16 kbps, it is perhaps the most successful low-delay coder available. Core techniques of the coder were developed mainly by Chen while at AT&T Bell Labs [Chen 1990, 1991, 1995; Chen et al., 1990, 1991, 1992]. Even though the coder is based on the same principles as CELP, it utilizes many uncon- ventional techniques to achieve low delay. In Section 14.1, strategies to achieve low delay are explained. Basic operational principles of the LD-CELP coder are described in Section 14.2, while issues related to LP analysis are given in Section 14.3. Excitation codebook structure and search procedures are covered in Section 14.4; the technique for backward gain adaptation is given in Section 14.5; operations of the encoder and decoder are covered in Section 14.6, followed by the algorithm for excitation codebook training in Section 14.7. A brief summary is given in the last section. 14.1 STRATEGIES TO ACHIEVE LOW DELAY In this section, we analyze the most important strategies adopted by the G.728 LD-CELP coder to achieve low delay while maintaining low bit-rate. Strategy 1. Reduce frame length to 20 samples. From Chapter 1 we know that the biggest component of coding delay is due to buffering at the encoder and is directly linked to the length of the frame selected for analysis. Therefore, an obvious solution is to reduce the length of the frame. Like conventional CELP, the LD-CELP coder partitions the input speech samples into frames that are further divided into subframes; each frame consists of 20 samples, containing four subframes of five samples each. As we will see later, encoding starts when five samples are buffered (one subframe); this leads to a buffering delay of 0.625 ms, producing a coding delay in the range of 1.25 to 1.875 ms. These value are much lower than conventional CELP, having a buffering delay of 20 to 30 ms. Strategy 2. Recursive autocorrelation estimation. The first step for finding the LPCs is to calculate the autocorrelation values, which can be done using conven- tional techniques such as Hamming windowing (nonrecursive); due to the short frame length, the scheme gets highly computationally expensive and inefficient since the windows become overlapping for consecutive frames. To simplify,

374 LOW-DELAY CELP recursive methods can be employed. The LD-CELP coder utilizes the Chen win- dowing method (Chapter 3) to estimate the autocorrelation values, which in prin- ciple is a hybrid technique, combining both recursive and nonrecursive approaches. Strategy 3. External prediction. Since the signal frame is relatively short, its statis- tical properties tend to be close to the near past or near future. It is therefore pos- sible to estimate the LPCs entirely from the past and apply these coefficients to the current frame, which is the definition of external prediction (Chapter 4). By using external prediction, the encoder does not have to wait to buffer the whole frame (20 samples) before analysis; instead, the LPCs are available at the instant that the frame begins; encoding starts as soon as one subframe (five samples) is available. This is in high contrast to conventional CELP, where the LPCs are derived from a long frame, with the resultant coefficients used inside the frame (internal prediction). Strategy 4. Backward adaptive linear prediction. Conventional speech coders use forward adaptation in linear prediction, where the LPCs are derived from the input speech samples; the coefficients are then quantized and transmitted as part of the bit-stream. The LD-CELP coder utilizes backward adaptation, with the LPCs obtained from the synthetic speech. By doing so, there is no need to quantize and transmit the LPCs since the synthetic speech is available at both the encoder and decoder side, thus saving a large number of bits for trans- mission. Note that this is a necessity to achieve low bit-rate, since otherwise the quantized LPCs must be transmitted at short frame intervals, leading to unacceptably high bit-rate. A disadvantage of the approach is its vulnerability toward channel errors: any error will propagate toward future frames while decoding. Strategy 5. High prediction order. The LD-CELP coder utilizes a short-term synth- esis filter with a prediction order equal to 50; no long-term predictor is employed. This design choice is due to the following reasons.  In general, two options are available for capturing the periodicity of voiced frames: a long-term predictor combined with a short-term predictor (with a typical order of 10), or a short-term predictor with high prediction order, for instance, a value of 50.  Long-term prediction with forward adaptation (i.e., parameters of the pred- ictors are obtained from the input speech signal and are quantized and transmitted to the decoder) is not an option, since the number of bits required to carry information regarding the long-term predictor’s parameters at short frame length would elevate the resultant bit-rate to prohibitive levels, ruining the low bit-rate goal.  Long-term prediction with backward adaptation (i.e., parameters of the predictor are extracted from the synthetic speech; these parameters are not required to be transmitted since the decoder has access to the same synthetic speech signal) is possible, since no extra bit allocation is necessary. However,

BASIC OPERATIONAL PRINCIPLES 375 it was found that backward block adaptation was extremely sensitive to channel errors and seemed to be inherently unstable [Chen, 1995]. Thus, the long-term predictor is abandoned.  Pitch period of female speech is typically less than 50 samples. By using a short-term predictor with a prediction order of 50, it is possible to reproduce female speech with high quality. In addition, prediction gain practically saturates when the order is beyond 50; that is, further increasing the prediction order beyond 50 does not improve the quality much and only increases the complexity.  High prediction order would create a burden for forward adaptation schemes since the LPCs must be quantized and transmitted; increasing the order implies an increasing number of bits for transmission. However, this is not an issue for LD-CELP, since backward adaptation is used with no need to encode the LPCs.  Without the long-term predictor, the coder becomes less speech-specific, since no pitch quasiperiodicity is assumed. This feature improves the perform- ance for nonspeech signals, like voice-band signaling tones found in most telecommunication systems and/or music. Strategy 6. Backward excitation gain adaptation. Excitation gain is updated once every subframe (five samples) by using a tenth-order adaptive linear predictor in the logarithmic-gain domain. The coefficients of this log-gain predictor are updated once every four subframes by performing linear prediction analysis on previous logarithmic gain values. By using a log-gain predictor of order ten, the predicted gain will be based on ten past gain values having a time span of 10 Á 5 ¼ 50 speech samples. This in turn allows the exploitation of pitch periodicity remaining in the excita- tion gain sequence for those female voices with a pitch period under 50 samples. Such a scheme is better at predicting the excitation gain for female voices. As a result, better coding efficiency can be achieved. By making the excitation gain backward adaptive, the current gain value is derived from the information embedded on previously quantized excitation, and there is no need to send any bits to specify the excitation gain, since the decoder can derive the same gain in the same manner. Transmission of the highly redundant gain information is thus eliminated. 14.2 BASIC OPERATIONAL PRINCIPLES After browsing the most distinguishing features of LD-CELP from the previous section, we are now ready for the basic operational principles. In LD-CELP, only five samples are needed to start the encoding process. On the other hand, only the excitation signal is transmitted: the predictor coefficients are updated by performing LP analysis on previously quantized speech. Thus, the

376 LOW-DELAY CELP LD-CELP coder is basically a backward adaptive version of the conventional CELP coder. The essence of CELP, which is the analysis-by-synthesis codebook search, is retained. Figure 14.1 shows the general structures of the LD-CELP encoder and decoder. The basic operational principle follows the conventional CELP algorithm, except that only the index to the excitation codebook is transmitted. The operation of the LD-CELP algorithm can be summarized as follows.  Like conventional CELP, samples of speech are partitioned into frames and subdivided into subframes. In LD-CELP, each frame consists of 20 samples, which contains four subframes of five samples each. Since LP analysis is performed in a backward adaptive fashion, there is no need to buffer an entire frame before processing. Only one subframe (five samples) needs to be stored before the encoding process begins. Input speech LP analysis Excitation Synthesis Perceptual codebook filter weighting filter Backward Backward gain predictor adaptation adaptation Error minimization LD-CELP bit-stream (Excitation index) LD-CELP Excitation S Synthesis Postfilter Synthetic bit-stream codebook filter speech Backward Backward gain predictor adaptation adaptation Figure 14.1 LD-CELP encoder (top) and decoder (bottom).

LINEAR PREDICTION ANALYSIS 377  The perceptual weighting filter has ten linear prediction coefficients derived from the original speech data. The filter is updated once per frame. The current frame’s coefficients are obtained from previous frames’ samples.  The synthesis filter corresponds to that of a 50th-order AR process. Its coefficients are obtained from synthetic speech data of previous frames. The filter is updated once per frame. The zero-input response of the current frame can be obtained from the known initial conditions.  Excitation gain is updated every subframe, with the updating process performed with a tenth-order adaptive linear predictor in the logarithmic-gain domain. The coefficients of this predictor are updated once per frame, with the LP analysis process done on gain values from previous subframes.  The excitation sequence is searched once per subframe, where the search procedure involves the generation of an ensemble of filtered sequences: each excitation sequence is used as input to the formant synthesis filter to obtain an output sequence. The excitation sequence that minimizes the final error is selected.  In the decoder, the initial conditions are restored. The synthetic speech is generated by filtering the indicated excitation sequence through the filter without any perceptual weighting. Since the excitation gain and the LPCs are backward adaptive, there is no need to transmit these parameters. A postfilter can be added to further enhance the output speech quality. Functionality of each block is presented in the next sections. 14.3 LINEAR PREDICTION ANALYSIS The LD-CELP algorithm requires multiple LP analysis procedures to be performed during operation since different sets of LPCs are used in various parts of the coder. These are:  Synthesis Filter. This is a 50th-order filter; its coefficients are obtained by analyzing the synthetic speech in a backward adaptive fashion. The same procedure is performed in the encoder and decoder. In the decoder, the resultant coefficients are also used by the postfilter.  Perceptual Weighting Filter. This is a tenth-order filter; its coefficients are obtained by analyzing the original input speech. This filter is available only in the encoder.  Backward Excitation Gain Adaptation. The gain is obtained through back- ward adaptation, where a tenth-order predictor is applied in the logarithmic- gain domain. Coefficients of the predictor are obtained by analyzing the past gain terms. The operation is the same for the encoder and the decoder. Details are given in Section 14.5.

378 LOW-DELAY CELP Synthetic Recursive Autocorrelation White speech autocorrelation windowing noise (optional) correction estimation Levinson− Bandwidth LPC Durbin expansion recursion Figure 14.2 Procedure to obtain the LPCs for the synthesis filter. Synthesis Filter The system function of the filter is HðzÞ ¼ 1 : ð14:1Þ P50 1 þ aizÀi i¼1 The LPCs ai; i ¼ 1; . . . ; 50; are obtained by backward adaptation, where the input to LP analysis is the synthetic speech signal. The procedure of LP analysis is summarized in Figure 14.2. A set of autocorrelation coefficients is first estimated from the synthetic speech signal: R½lŠ; l ¼ 0; . . . ; 50; the estimation is based on the Chen windowing procedure with parameters a ¼ ð3=4Þ1=40 ¼ 0:992833749; L ¼ 35: As explained in Chapter 3, the Chen window is hybrid in nature and consists of a recursive part and a nonrecursive part. It is highly efficient and provides good accuracy in practice. Backward LP analysis is inherently more unstable than forward adaptation, and many of the techniques discussed in Chapter 4 for the alleviation of ill-conditioning are necessary to ‘‘tame’’ the system. Spectral smoothing by windowing the autocor- relation coefficients is optional; however, its application is highly recommended since system divergence (state of the decoder does not follow the encoder) had been observed for certain synthetic signals when this block is not present [Chen, 1995]. White noise correction is applied next with l ¼ 257/256. After using the Levison–Durbin recursion, the LPCs are bandwidth expanded with g ¼ 253/ 256 & 0.9883. The LPCs are updated once every frame, or four subframes (20 samples). Within the frame–subframe structure, the update occurs at the third subframe. This scheme is illustrated in Figure 14.3. Note that the LPCs found from the samples before sub- frame 0 of the current frame are used by subframes 2 and 3 of the current frame,

Analyze the signal LINEAR PREDICTION ANALYSIS 379 at this interval to obtain the LPCs. Resultant LPCs are applied to this interval. Sf0 Sf1 Sf2 Sf3 Next frame Previous frame Current frame Figure 14.3 Illustration of LPC adaptation scheme for the synthesis filter. and subframes 0 and 1 of the future frame. This scheme allows a more even distri- bution of computational activity during the various cycles of the encoding process and thus facilitates real-time implementation. This can be seen by observing that even though the autocorrelation values are available at the first subframe of each frame, computations may require more than one subframe worth of time. And since the Levinson–Durbin recursion is quite demanding, by updating at the third subframe, plenty of time is available to complete the task. Perceptual Weighting Filter The system function of the perceptual weighting filter is W ðzÞ ¼ Aðz=g1Þ ¼ 1 þ P10 bigi1zÀi : ð14:2Þ Aðz=g2Þ 1 þ bigi2zÀi i¼1 P10 i¼1 The nominal values for (g1, g2) are (0.9, 0.6) and have been found to give good subjective quality. When compared with the form of weighting filter given in Chap- ter 11, (14.2) is more general, allowing more control over the spectral characteris- tics. Note that the prediction order is equal to 10, which is quite different from conventional CELP, where the order of the synthesis filter is equal to that of the weighting filter. Experimentally, a weighting filter with an order of 50 was found to produce occasional artifacts and was thus abandoned from consideration [Chen, 1995]. The LPCs bi, i ¼ 1 to 10, are derived from the original input speech; use of syn- thetic speech is avoided since it contains quantization errors. LP analysis follows a similar approach as for the synthesis filter, with a ¼ ð1=2Þ1=40 ¼ 0:982820598; L ¼ 30

380 LOW-DELAY CELP being the window parameters; white noise correction is the same as for the synth- esis filter. The LPCs bi in (14.2) are the output of the Levinson–Durbin module. Similar to the synthesis filter, the perceptual weighting filter is also updated once per frame, and the updates also occur at the third subframe. 14.4 EXCITATION CODEBOOK SEARCH Like conventional CELP, the zero-input response is first subtracted from the input speech to obtain the target sequence. The target sequence is then used as reference during the excitation codebook search, where the codevector capable of generating the sequence as close as possible (in a sum of squared error sense) to the reference is selected. In this section, various techniques for the excitation codebook search are analyzed. Due to architectural differences with conventional CELP, LD-CELP requires different methodologies to improve efficiency. The Analysis-by-Synthesis Loop Figure 14.4 shows the encoding loop of the LD-CELP coder; unlike conventional CELP, the excitation gain is known during encoding of the current subframe, which is obtained through prediction from past values. Due to this fact, some computa- tional saving is obtainable. Consider the alternative scheme shown in Figure 14.5. This new scheme has the excitation gain block moved out of the loop. After the zero-input response is subtracted from the original speech, the resultant sequence is divided by the excitation gain to generate the target sequence. In this way, there is no need to multiply all vectors of the excitation codebook by the gain. Using similar reasoning as for conventional CELP, it is possible to reposition the perceptual weighting filter as shown in Figure 14.6, leading to an additional cut in computa- tional cost. Synthesis Input speech filter − Excitation Synthesis − codebook filter (Zero) Gain Error Perceptual minimization weighting filter Figure 14.4 Analysis-by-synthesis loop of the LD-CELP encoder.