Title of Invention	AN APPARATUS GENERATING AND ENCODING LINEAR PREDICTION CODING(LPC) COEFFICIENTS INA LINEAR PREDICTIVE CODER SIGNAL APPARATUS
Abstract	A novel and improved method and apparatus for encoding line predictive coding (LPC) data in a speech compression system using line spectral square root values is disclosed. A novel and computationally efficient procedure for determining the set of quantization sensitivities for the line spectral square root values is disclosed, which results in a computationally efficient error measure for use in vector quantization of the line spectral square root values. A novel method of weighting the quantization error is disclosed, which accumulates the quantization error in each line spectral square root value and weights that error by the sensitivity of that line spectral square root value.

Title of Invention

AN APPARATUS GENERATING AND ENCODING LINEAR PREDICTION CODING(LPC) COEFFICIENTS INA LINEAR PREDICTIVE CODER SIGNAL APPARATUS

Abstract

A novel and improved method and apparatus for encoding line predictive coding (LPC) data in a speech compression system using line spectral square root values is disclosed. A novel and computationally efficient procedure for determining the set of quantization sensitivities for the line spectral square root values is disclosed, which results in a computationally efficient error measure for use in vector quantization of the line spectral square root values. A novel method of weighting the quantization error is disclosed, which accumulates the quantization error in each line spectral square root value and weights that error by the sensitivity of that line spectral square root value.

Full Text	The invention relates to an apparatus for generating and encoding linear prediction coding (LPC) coefficients in a linear predictive coder signal apparatus. II. Description of the Related Art Transmission of voice by digital techniques has become widespread, particularly in long distance and digital radio telephone applications. This has created interest in methods which minimize the amount of information transmitted over a channel while maintaining the quality of the speech reconstructed from that information. If speech is transmitted by simply sampling the continuous speech signal and quantizing each sample independently, a data rate around 64 kilobits per second (kbps) is required to achieve a reconstructed speech quality similar to that of a conventional analog telephone. However, through the use of speech analysis, followed by the appropriate coding, transmission, and resynthesis at the receiver, a significant reduction in the data rate can be achieved. Devices which compress speech by extracting parameters of a model of human speech production are called vocoders. Such devices are composed of an encoder, which analyzes the incoming speech to extract the relevant parameters, and a decoder, which resynthesizes the speech using the parameters which it receives from the encoder over the transmission channel. To accurately represent the time varying speech signal, the model parameters are updated periodically. The speech is divided into blocks of time, or analysis frames, during which the parameters are calculated and , quantized. These quantized parameters are then transmitted over a transmission channel, and the speech is reconstructed from these quantized parameters at the receiver. The Code Excited Linear Predictive Coding (CELP) method is used in many speech compression algorithms. An example of a CELP coding algorithm is described in the paper "A 4.8 kbps Code Excited Linear Predictive Coder" by Thomas E. Tremain et al. Proceedings of the Mobile Satellite Conference, 1988. An example of a particularly efficient vocoder of this type is detailed in U.S. Patent No. 5,414,796, entitled "Variable Rate Vocoder" and assigned to the assignee of the present invention and incorporated by reference herein. Many speech compression algorithms use a filter to model the spectral magnitude of the speech signal. Because the coefficients of the filter are computed for each frame of speech using linear prediction techniques, the filter is referred to as the Linear Predictive Coding (LPC) filter. Once the filter coefficients have been determined, the filter coefficients must be quantized. Efficient methods for quantizing the LPC filter coefficients can be used to decrease the bit rate required to encode the speech signal. One method for quantizing the coefficients of the LPC filter involves transforming the filter coefficients to Line Spectral Pair (LSP) parameters, and quantizing the LSP parameters. The quantized LSPs are then transformed back to LPC filter coefficients, which are used in the speech synthesis model at the decoder. Quantization is performed in the LSP domain because LSP parameters have better quantization properties than LPC parameters, and because the ordering property of the quantized LSP parameters guarantees that the resulting quantized LPC filter will be stable. For a particular set of LSP parameters, quantization error in one parameter may result in a larger change in the LPC filter response, and thus a larger perceptual degradation, than the change produced by a similar amount of quantization error in another LSP parameter. The perceptual effect of quantization can be minimized by allowing more quantization error in LSP parameters which are less sensitive to quantization error. To determine the optimal distribution of quantization error, the individual sensitivity of each LSP parameter must be determined. A preferred method and apparatus for optimally encoding LSP parameters is described in detail in copending U.S. Patent Application, Serial No. 08/286,150, filed August 4, 1994, entitled "Sensitivity Weighted Vector Quantization of Line Spectral Pair Frequencies," which is assigned to the assignee of the present invention and incorporated by reference herein. SUMMARY OF THE INVENTION The present invention is a novel and improved method and apparatus for quantizing LPC parameters which uses line spectral square root (LSS) values. The present invention transforms the LPC filter coefficients into an alternative set of data which is more easily quantized than the LPC coefficients and which offers the reduced sensitivity to quantization errors that is a prime benefit of LSP frequency encoding. In addition, the transformations from LPC coefficients to LSS values and from LSS values to LPC coefficients are less computationally intensive than the corresponding transformations between LPC coefficients and LSP parameters. Accordingly the present invention provides an apparatus for generating and encoding linear prediction coding (LPC) coefficients in a linear predictive coder signal apparatus comprising: LPC generator means for receiving digitized speech samples and generating a set of LPC coefficients for said digitized speech samples in accordance with a linear prediction coding format; line spectral cosine generator means for receiving said set of LPC coefficients and generating a set of line spectral cosine values in accordance with a line spectral cosine transform format; and line spectral square root means for receiving said set of line spectral cosine values and for generating a set of line spectral square root values in accordance with a square root transformation format. With reference to the accompanying drawings : BRIEF DESCRIPTION OF THE DRAWINGS The features, objects, and advantages of the present invention will beconne more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein: FIG. 1 is a block diagram illustrating the prior art apparatus for generating and encoding LPC coefficients; FIG. 2 illustrates the plot of the normalizing function used to redistribute the line spectral cosine values in the present invention; FIG. 3 illustrates the block diagram illustrating the apparatus for generating sensitivity values for encoding the line spectral square root values of the present invention; and FIG. 4 is a block diagram illustrating the overall quantization mechanism for encoding the line spectral square root values. DETAILED DESCRIPTION OF THE PREFERREp EMBODIMENTS FIG. 1 illustrates the traditional apparatus for generating and encoding LPC filter data by determining the LPC coefficients (a(l),a(2),...,a(N)) and from those LPC coefficients generating the LSP frequencies (a)(l),co(2),,..,co(N)). N is the number of filter coefficients in the LPC filter. Speech autocorrelation element 1 computes a set of autocorrelation values, R(0) to R(N), from the frame of speech samples, s(n) in accordance with equation (1) below: (1) where L is the number of speech samples in the frame over which the LPC coefficients are being calculated. In the exemplary embodiment, the number of samples in a frame is 160 (L=160), and the number of LPC filter coefficients is 10 (N=10). Linear prediction coefficient (LPC) computation element 2 computes the LPC coefficients, a(l) to a(N), from the set of autocorrelation values, R(0) " to R(N). The LPC coefficients may be obtained by the autocorrelation method using Durbin's recursion as discussed in Digital Processing of Speech Signals. Rabiner & Schafer, Prentice-Hall, Inc., 1978. The algorithm element 1 and 2 are well known. In the exemplary embodiment, the formant filter is a tenth order filter, meaning that 11 autocorrelation values, R(0) to R(10), are computed by autocorrelation element 1, and 10 LPC coefficients, a(l) to a(10), are computed by LPC computation element 2. LSP computation element 3 converts the set of LPC coefficients into a set of LSP frequencies of values w1towN. The operation of LSP computation element 3 is well known and is described in detail in the aforementioned U.S. Patent No. 5,414,796. Motivation for the use of LSP frequencies is given in the article "Line Spectrum Pair (LSP) and Speech Data Compression", by Soong and Juang, ICASSP '84. The computation of the LSP parameters is shown below in equations (8) and (9) along with Table I. The LSP frequencies are the N roots which exist between 0 and TC of the following equations: In Table I, the a(l), ... , a(N) values are the scaled coefficients resulting from the LPC analysis. A property of the LSP frequencies is that, if the LPC filter is stable, the roots of the two functions alternate; i.e. the lowest root, C1, is the lowest root of p((o), the next lowest root, (02, is the lowest root of q(a)), and so on. Of the N frequencies, the odd frequencies are the roots of the p(co), and the even frequencies are the roots of the q(co). Solving equations (8) and (9) to obtain the LSP frequencies is a computationally intensive operation. One of the primary source of computational loading in transforming the LPC coefficients to LSP frequencies and back from LSP frequencies to LPC coefficients results from the extensive use of the trigonometric functions. One way to reduce the computational complexity is to make the substitution: and so on. By making these substitutions and grouping terms with common powers of x, equations (8) and (9) can be reduced to polynomials in x given by: Thus, it is possible to provide the information provided by the LSP frequencies ((01...CON) by providing the values (XI...XN)/ which are referred to as the line spectral cosines (x1...xN)- Determining the N line spectral cosine values involves finding the N roots of equations (14) and (15). This procedure requires no trigonometric evaluations, which greatly reduces the computational complexity. The problem with quantizing the line spectral cosine values, as opposed to the LSP frequencies, is that the line spectral cosine values with values near +1 and -1 are very sensitive to quantization noise. In the present invention, the line spectral cosine values are made more robust to quantization noise by transforming them to a set of values referred herein as line spectral square root (LSS) values (yi..yN)- The computation used to transform the line spectral cosine (xi.-xjsj) values to line spectral square root (yi-.yN) values is shown in equation (16) below: where xi is the ith line spectral cosine value and yi is the corresponding ith line spectral square root value. The transformation from line spectral cosines to line spectral square-roots can be viewed as a scaled approximation to the transformation from line spectral cosines to LSPs, co = arccos(x). FIG. 2 illustrates a plot of the function of equation (16). Because of this transformation, the line spectral square root values are more uniformly sensitive to quantization noise than are line spectral cosine values, and have properties similar to LSP frequencies. However, the transformations between LPC coefficients and LSS values require only product and square-root computations, which are much less computationally intensive than the trigonometric evaluations required by the transformations between LPC coefficients and LSP frequencies. In an improved embodiment of the present invention, the line spectral square root values are encoded in accordance with computed sensitivity values and codebook selection method and apparatus described herein. The method and apparatus for encoding the line spectral square root values of the present invention maximize the perceptual quality of the encoded speech with a minimum number of bits. FIG. 3 illustrates the apparatus of the present invention for generating the line spectral cosine values (x(l),x(2),...,x(N)) and the quantization sensitivities of the line spectral square root values (SI,S2,-..,SN). AS described earlier, N is the number of filter coefficients in the LPC filter. Speech autocorrelation element 101 computes a set of autocorrelation values, R(0) to R(N), from the frame of speech samples, s(n) in accordance with equation (1) above. Linear prediction coefficient (LPC) computation element 102 computes the LPC coefficients, a(l) to a(N), from the set of autocorrelation values, R(0) to R(N), as described above in equations (2) - (7). Line spectral cosine computation element 103 converts the set of LPC coefficients into a set of line spectral cosine values, x; to x-, as described above in equations (14) - (15). Sensitivity computation element 108 generates the sensitivity values (Si,..., SN) as described below. is being computed. For the line spectral cosine values with odd index (xi, Because of this symmetry only half of the division needs to be performed to determine the entire set of N Ji values. Similarly, if i is even. FIG. 4 illustrates the apparatus of the present invention for generating and quantizing the set of line spectral square root values. The present invention can be implemented in a digital signal processor (DSP) or in an application specific integrated circuit (ASIC) programmed to perform the function as described herein. Elements 111, 112 and 113 operate as described above for blocks 101,102 and 103 of FIG. 3. Line spectral cosine computation element 113 provides the line spectral cosine values (xi,..., XN) to line spectral square root computation element 121, which computes the line spectral square root values, y(l)...y(N), in accordance with equation (16) above. Sensitivity computation element 114 receives line spectral cosine values (xi,..., XN) from line spectral cosine computation element 113, LPC values (a(l),..., a(N)) from LPC computation element 112 and autocorrelation values (R(0),..., R(N)) from speech autocorrelation element 111. Sensitivity computation element 114 generates the set of sensitivity values. Si,..., SN/ as described regarding sensitivity computation element 108 of FIG. 3. Once the set of line spectral square root values, y(l)...y(N), and the set of sensitivities. Si,..., SN/ are computed, the quantization of the line spectral square root values begins. A first subvector of line spectral square root value differences, comprising Ayj, Ay2,... yN(i). is computed by subtractor elements 115a as: The set of values N(l), N(2), etc. define the partitioning of the line spectral square root vector into subvectors. In the exemplary embodiment with N=10, the line spectral square root vector is partitioned into 5 subvectors of 2 elements each, such that N(l)=2, N(2)=4, N(3)=6, N(4)=8, and N(5)=10. V is defined as the number of subvectors. In the exemplary embodiment, V=5. In alternate embodiments, the line spectral square root vector can be partitioned into different numbers of subvectors of differing dimension. For example, a partitioning into 3 subvectors with 3 elements in the first subvector, 3 elements in the second subvector, and 4 elements in the third iubvector would result in N(l)=3, N(2)=6, and N(3)=10. In this alternative embodiment V=3. After the first subvector of line spectral square root differences is computed in subtractor 115a, it is quantized by elements 116a, 117a, 118a, and 119a. Element 118a is a codebook of line spectral square root difference vectors. In the exemplary embodiment, there are 64 such vectors. The codebook of line spectral square root difference vectors can be determined using well known vector quantization training algorithms. Index generator 1, element 117a, provides a codebook index, m, to codebook element 118a. Codebook element 118a in response to index m provides the m* codevector, made up of elements AyCm),..., AyjsjQ\(m). Error computation and minimization element 116a computes the sensitivity weighted error, E(m), which represents the approximate spectral distortion which would be incurred by quantizing the original subvector of line spectral square root differences to this m*h codevector of line spectral square root differences. In the exemplary embodiment, E(m) is computed as ' described by the following equations. E(m) is the sum of sensitivity weighted squared errors in the LSS values. The procedure for determining the sensitivity weighted error illustrated in equations (31) - (36) accumulates the quantization error in each line spectral square root value and weights that error by the sensitivity of the LSS value. Once E(m) has been computed for all codevectors in the codebook, error computation and minimization (ERROR COMP. AND MINI.) element The quantized line spectral square root value yN(1) computed in block 119a, and the yi for i from N(l)+1 to N(2) are used to compute the second subvector of line spectral square root differences, comprising AyNn\+i. The operation for selecting the second index value I2 is performed in the same way as described above for selecting Ii. The remaining subvectors are quantized sequentially in a similar manner. The operation for all of the subvectors is essentially the same and for instance the last subvector, the Vth subvector, is quantized after all of the subvectors from 1 to V-1 have been quantized. The Vth subvector of line spectral square root differences is computed by an element 115V as Once the best codevector for the Vth subvector is determined, the quantized line spectral square root differences and the quantized line spectral square root values for that subvector are computed as described above. This procedure is repeated sequentially until all of the subvectors are quantized. In FIG. 3 and FIG. 4, the blocks may be implemented as structural blocks to perform the designated functions or the blocks may represent functions performed in programming of a digital signal processor (DSP) or an application specific integrated circuit ASIC. The description of the functionality of the present invention would enable one of ordinary skill to implement the present invention in a DSP or an ASIC without undue experimentation. The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. The various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. WE CLAIM : 1. An apparatus for generating and encoding linear prediction coding (LPC) coefficients in a linear predictive coder signal apparatus comprising: LPC generator means for receiving digitized speech samples and generating a set of LPC coefficients for said digitized speech samples in accordance with a linear prediction coding format; line spectral cosine generator means for receiving said set of LPC coefficients and generating a set of line spectral cosine values in accordance with a line spectral cosine transform format; and line spectral square root means for receiving said set of line spectral cosine values and for generating a set of line spectral square root values in accordance with a square roottrans formation format. 2. The apparatus of claim 1 wherein said line spectral square root means has a square root transformation format defined by where xi is the ith line spectral cosine value and yi is the corresponding ith line spectral square root value. 3. The apparatus as claimed in claim 1, wherein sensitivity computation means is provided for receiving said set of line spectral cosine values, said set of LPC coefficients, and a set of speech autocorrelation coefficients, and for computing a set of line spectral square root sensitivity coefficients in accordance with a weighted cross-correlation computation format. 4. The apparatus of claim 3, wherein said sensitivity computation means comprises polynomial division means for receiving said set of line spectral cosine values and a set of linear prediction coding (LPC) coefficients and for generating a set of quotient coefficients in accordance with a predetermined polynomial division format. 5. The apparatus of claim 4, wherein said sensitivity computation means comprises a sensitivity autocorrelation means for receiving said set of quotient coefficients and generating a set of sensitivity autocorrelation values for said set of quotient coefficients in accordance with a predetermined autocorrelation format. 6. The apparatus as claimed in claim 5 wherein said vector computation means computes two vectors P and Q in said set of vectors in accordance with the equations: 7. The apparatus as claimed in claim 6 wherein said polynomial division means provides said set of quotient coefficients Jj for odd line spectral square root values in accordance with the equation: where z is the polynomial variable, Xj is the ith line spectral cosine value, and N is the number of filter taps. 8. The apparatus as claimed in claim 6, wherein said polynomial division means provides said set of quotient coefficients Jj for even line spectral square root values in accordance with the equation: where z is the polynomial variable, Xj is the ith line spectral cosine value, and N is the number of filter taps. 9. The apparatus as claimed in claim 3 wherein said sensitivity cross correlation means provides said line spectral square root sensitivity values in accordance with the equation: where Xi is the ith line spectral square root value, R(k) is the kth speech autocorrelation coefficient of the set of speech samples and Rji(k) is the kth autocorrelation coefficient of said set of quotient coefficients. 10. The apparatus as claimed in claim 1 wherein the LPC generator has an input for receiving digitized speech samples and an output to provide a set of LPC coefficients; the line spectral cosine generator has an input coupled to said LPC generator output and an output; and the line spectral square root generator has an input coupled to said line spectral cosine generator output and an output. 11. The apparatus as claimed in claim 10 wherein a polynomial division calculator having an input is coupled to said line spectral square root generator output and an output; and sensitivity cross correlation calculator having an input is coupled to said polynomial division calculator output and an output. 12. The apparatus as claimed in claim 11 wherein a sensitivity autocorrelation calculator disposed between said polynomial division calculator and said sensitivity cross correlation calculator having an input coupled to said polynomial division calculator output and an output coupled to said sensitivity cross correlation calculator input. 13. An apparatus for generating and encoding linear prediction coding (LPC) coefficients in a linear predictive coder signal apparatus, substantially as hereinabove described and illustrated with reference to the accompanying drawings.

Full Text

The invention relates to an apparatus for generating and encoding linear prediction coding (LPC) coefficients in a linear predictive coder signal apparatus.
II. Description of the Related Art
Transmission of voice by digital techniques has become widespread, particularly in long distance and digital radio telephone applications. This has created interest in methods which minimize the amount of information transmitted over a channel while maintaining the quality of the speech reconstructed from that information. If speech is transmitted by simply sampling the continuous speech signal and quantizing each sample independently, a data rate around 64 kilobits per second (kbps) is required to achieve a reconstructed speech quality similar to that of a conventional analog telephone. However, through the use of speech analysis, followed by the appropriate coding, transmission, and resynthesis at the receiver, a significant reduction in the data rate can be achieved.
Devices which compress speech by extracting parameters of a model
of human speech production are called vocoders. Such devices are
composed of an encoder, which analyzes the incoming speech to extract the
relevant parameters, and a decoder, which resynthesizes the speech using
the parameters which it receives from the encoder over the transmission
channel. To accurately represent the time varying speech signal, the model
parameters are updated periodically. The speech is divided into blocks of
time, or analysis frames, during which the parameters are calculated and ,
quantized. These quantized parameters are then transmitted over a transmission channel, and the speech is reconstructed from these quantized parameters at the receiver.
The Code Excited Linear Predictive Coding (CELP) method is used in many speech compression algorithms. An example of a CELP coding algorithm is described in the paper "A 4.8 kbps Code Excited Linear Predictive Coder" by Thomas E. Tremain et al. Proceedings of the Mobile Satellite Conference, 1988. An example of a particularly efficient vocoder of

this type is detailed in U.S. Patent No. 5,414,796, entitled "Variable Rate Vocoder" and assigned to the assignee of the present invention and incorporated by reference herein.
Many speech compression algorithms use a filter to model the spectral magnitude of the speech signal. Because the coefficients of the filter are computed for each frame of speech using linear prediction techniques, the filter is referred to as the Linear Predictive Coding (LPC) filter. Once the filter coefficients have been determined, the filter coefficients must be quantized. Efficient methods for quantizing the LPC filter coefficients can be used to decrease the bit rate required to encode the speech signal.
One method for quantizing the coefficients of the LPC filter involves transforming the filter coefficients to Line Spectral Pair (LSP) parameters, and quantizing the LSP parameters. The quantized LSPs are then transformed back to LPC filter coefficients, which are used in the speech synthesis model at the decoder. Quantization is performed in the LSP domain because LSP parameters have better quantization properties than LPC parameters, and because the ordering property of the quantized LSP parameters guarantees that the resulting quantized LPC filter will be stable.
For a particular set of LSP parameters, quantization error in one parameter may result in a larger change in the LPC filter response, and thus a larger perceptual degradation, than the change produced by a similar amount of quantization error in another LSP parameter. The perceptual effect of quantization can be minimized by allowing more quantization error in LSP parameters which are less sensitive to quantization error. To determine the optimal distribution of quantization error, the individual sensitivity of each LSP parameter must be determined. A preferred method and apparatus for optimally encoding LSP parameters is described in detail in copending U.S. Patent Application, Serial No. 08/286,150, filed August 4, 1994, entitled "Sensitivity Weighted Vector Quantization of Line Spectral Pair Frequencies," which is assigned to the assignee of the present invention and incorporated by reference herein.
SUMMARY OF THE INVENTION
The present invention is a novel and improved method and apparatus for quantizing LPC parameters which uses line spectral square root (LSS) values. The present invention transforms the LPC filter coefficients into an alternative set of data which is more easily quantized than the LPC coefficients and which offers the reduced sensitivity to

quantization errors that is a prime benefit of LSP frequency encoding. In addition, the transformations from LPC coefficients to LSS values and from LSS values to LPC coefficients are less computationally intensive than the corresponding transformations between LPC coefficients and LSP parameters.
Accordingly the present invention provides an apparatus for generating and encoding linear prediction coding (LPC) coefficients in a linear predictive coder signal apparatus comprising: LPC generator means for receiving digitized speech samples and generating a set of LPC coefficients for said digitized speech samples in accordance with a linear prediction coding format; line spectral cosine generator means for receiving said set of LPC coefficients and generating a set of line spectral cosine values in accordance with a line spectral cosine transform format; and line spectral square root means for receiving said set of line spectral cosine values and for generating a set of line spectral square root values in accordance with a square root transformation format.
With reference to the accompanying drawings :

BRIEF DESCRIPTION OF THE DRAWINGS
The features, objects, and advantages of the present invention will beconne more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein:
FIG. 1 is a block diagram illustrating the prior art apparatus for generating and encoding LPC coefficients;
FIG. 2 illustrates the plot of the normalizing function used to redistribute the line spectral cosine values in the present invention;
FIG. 3 illustrates the block diagram illustrating the apparatus for generating sensitivity values for encoding the line spectral square root values of the present invention; and
FIG. 4 is a block diagram illustrating the overall quantization mechanism for encoding the line spectral square root values.
DETAILED DESCRIPTION OF THE PREFERREp EMBODIMENTS
FIG. 1 illustrates the traditional apparatus for generating and encoding LPC filter data by determining the LPC coefficients (a(l),a(2),...,a(N)) and from those LPC coefficients generating the LSP frequencies (a)(l),co(2),,..,co(N)). N is the number of filter coefficients in the LPC filter. Speech autocorrelation element 1 computes a set of autocorrelation values, R(0) to R(N), from the frame of speech samples, s(n) in accordance with equation (1) below:
(1)
where L is the number of speech samples in the frame over which the LPC coefficients are being calculated. In the exemplary embodiment, the number

of samples in a frame is 160 (L=160), and the number of LPC filter coefficients is 10 (N=10).
Linear prediction coefficient (LPC) computation element 2 computes
the LPC coefficients, a(l) to a(N), from the set of autocorrelation values, R(0)
" to R(N). The LPC coefficients may be obtained by the autocorrelation
method using Durbin's recursion as discussed in Digital Processing of
Speech Signals. Rabiner & Schafer, Prentice-Hall, Inc., 1978. The algorithm

element 1 and 2 are well known. In the exemplary embodiment, the formant filter is a tenth order filter, meaning that 11 autocorrelation values, R(0) to R(10), are computed by autocorrelation element 1, and 10 LPC coefficients, a(l) to a(10), are computed by LPC computation element 2.
LSP computation element 3 converts the set of LPC coefficients into a set of LSP frequencies of values w1towN. The operation of LSP
computation element 3 is well known and is described in detail in the aforementioned U.S. Patent No. 5,414,796. Motivation for the use of LSP frequencies is given in the article "Line Spectrum Pair (LSP) and Speech Data Compression", by Soong and Juang, ICASSP '84.
The computation of the LSP parameters is shown below in equations (8) and (9) along with Table I. The LSP frequencies are the N roots which exist between 0 and TC of the following equations:

In Table I, the a(l), ... , a(N) values are the scaled coefficients resulting from the LPC analysis. A property of the LSP frequencies is that, if the LPC filter is stable, the roots of the two functions alternate; i.e. the lowest root, C1, is the lowest root of p((o), the next lowest root, (02, is the lowest root of
q(a)), and so on. Of the N frequencies, the odd frequencies are the roots of the p(co), and the even frequencies are the roots of the q(co).
Solving equations (8) and (9) to obtain the LSP frequencies is a computationally intensive operation. One of the primary source of computational loading in transforming the LPC coefficients to LSP frequencies and back from LSP frequencies to LPC coefficients results from the extensive use of the trigonometric functions.
One way to reduce the computational complexity is to make the substitution:

and so on.
By making these substitutions and grouping terms with common powers of x, equations (8) and (9) can be reduced to polynomials in x given by:

Thus, it is possible to provide the information provided by the LSP frequencies ((01...CON) by providing the values (XI...XN)/ which are referred to as the line spectral cosines (x1...xN)- Determining the N line spectral cosine values involves finding the N roots of equations (14) and (15). This procedure requires no trigonometric evaluations, which greatly reduces the computational complexity. The problem with quantizing the line spectral cosine values, as opposed to the LSP frequencies, is that the line spectral cosine values with values near +1 and -1 are very sensitive to quantization noise.
In the present invention, the line spectral cosine values are made more robust to quantization noise by transforming them to a set of values referred herein as line spectral square root (LSS) values (yi..yN)- The computation used to transform the line spectral cosine (xi.-xjsj) values to line spectral square root (yi-.yN) values is shown in equation (16) below:

where xi is the ith line spectral cosine value and yi is the corresponding ith line spectral square root value. The transformation from line spectral cosines to line spectral square-roots can be viewed as a scaled approximation to the transformation from line spectral cosines to LSPs, co = arccos(x). FIG. 2 illustrates a plot of the function of equation (16).
Because of this transformation, the line spectral square root values are more uniformly sensitive to quantization noise than are line spectral

cosine values, and have properties similar to LSP frequencies. However, the transformations between LPC coefficients and LSS values require only product and square-root computations, which are much less computationally intensive than the trigonometric evaluations required by the transformations between LPC coefficients and LSP frequencies.
In an improved embodiment of the present invention, the line spectral square root values are encoded in accordance with computed sensitivity values and codebook selection method and apparatus described herein. The method and apparatus for encoding the line spectral square root values of the present invention maximize the perceptual quality of the encoded speech with a minimum number of bits.
FIG. 3 illustrates the apparatus of the present invention for generating the line spectral cosine values (x(l),x(2),...,x(N)) and the quantization sensitivities of the line spectral square root values (SI,S2,-..,SN). AS described earlier, N is the number of filter coefficients in the LPC filter. Speech autocorrelation element 101 computes a set of autocorrelation values, R(0) to R(N), from the frame of speech samples, s(n) in accordance with equation (1) above.
Linear prediction coefficient (LPC) computation element 102
computes the LPC coefficients, a(l) to a(N), from the set of autocorrelation
values, R(0) to R(N), as described above in equations (2) - (7). Line spectral
cosine computation element 103 converts the set of LPC coefficients into a set of line spectral cosine values, x; to x-, as described above in equations
(14) - (15). Sensitivity computation element 108 generates the sensitivity values (Si,..., SN) as described below.

is being computed. For the line spectral cosine values with odd index (xi,

Because of this symmetry only half of the division needs to be performed to determine the entire set of N Ji values. Similarly, if i is even.

FIG. 4 illustrates the apparatus of the present invention for generating and quantizing the set of line spectral square root values. The present invention can be implemented in a digital signal processor (DSP) or in an application specific integrated circuit (ASIC) programmed to perform the function as described herein. Elements 111, 112 and 113 operate as described above for blocks 101,102 and 103 of FIG. 3. Line spectral cosine computation element 113 provides the line spectral cosine values (xi,..., XN) to line spectral square root computation element 121, which computes the line spectral square root values, y(l)...y(N), in accordance with equation (16) above.
Sensitivity computation element 114 receives line spectral cosine values (xi,..., XN) from line spectral cosine computation element 113, LPC values (a(l),..., a(N)) from LPC computation element 112 and autocorrelation values (R(0),..., R(N)) from speech autocorrelation element 111. Sensitivity computation element 114 generates the set of sensitivity values. Si,..., SN/ as described regarding sensitivity computation element 108 of FIG. 3.
Once the set of line spectral square root values, y(l)...y(N), and the set of sensitivities. Si,..., SN/ are computed, the quantization of the line spectral square root values begins. A first subvector of line spectral square root value differences, comprising Ayj, Ay2,... yN(i). is computed by subtractor
elements 115a as:

The set of values N(l), N(2), etc. define the partitioning of the line spectral square root vector into subvectors. In the exemplary embodiment with N=10, the line spectral square root vector is partitioned into 5 subvectors of 2 elements each, such that N(l)=2, N(2)=4, N(3)=6, N(4)=8, and N(5)=10. V is defined as the number of subvectors. In the exemplary embodiment, V=5.
In alternate embodiments, the line spectral square root vector can be partitioned into different numbers of subvectors of differing dimension. For example, a partitioning into 3 subvectors with 3 elements in the first subvector, 3 elements in the second subvector, and 4 elements in the third iubvector would result in N(l)=3, N(2)=6, and N(3)=10. In this alternative embodiment V=3.

After the first subvector of line spectral square root differences is computed in subtractor 115a, it is quantized by elements 116a, 117a, 118a, and 119a. Element 118a is a codebook of line spectral square root difference vectors. In the exemplary embodiment, there are 64 such vectors. The codebook of line spectral square root difference vectors can be determined using well known vector quantization training algorithms. Index generator 1, element 117a, provides a codebook index, m, to codebook element 118a. Codebook element 118a in response to index m provides the m* codevector, made up of elements AyCm),..., AyjsjQ\(m).
Error computation and minimization element 116a computes the
sensitivity weighted error, E(m), which represents the approximate spectral distortion which would be incurred by quantizing the original subvector of line spectral square root differences to this m*h codevector of line spectral square root differences. In the exemplary embodiment, E(m) is computed as
' described by the following equations.

E(m) is the sum of sensitivity weighted squared errors in the LSS values. The procedure for determining the sensitivity weighted error illustrated in equations (31) - (36) accumulates the quantization error in each line spectral square root value and weights that error by the sensitivity of the LSS value.
Once E(m) has been computed for all codevectors in the codebook, error computation and minimization (ERROR COMP. AND MINI.) element

The quantized line spectral square root value yN(1) computed in block 119a, and the yi for i from N(l)+1 to N(2) are used to compute the second subvector of line spectral square root differences, comprising AyNn\+i.
The operation for selecting the second index value I2 is performed in the same way as described above for selecting Ii.
The remaining subvectors are quantized sequentially in a similar manner. The operation for all of the subvectors is essentially the same and for instance the last subvector, the Vth subvector, is quantized after all of the subvectors from 1 to V-1 have been quantized. The Vth subvector of line spectral square root differences is computed by an element 115V as

Once the best codevector for the Vth subvector is determined, the quantized line spectral square root differences and the quantized line spectral square root values for that subvector are computed as described above. This procedure is repeated sequentially until all of the subvectors are quantized.
In FIG. 3 and FIG. 4, the blocks may be implemented as structural blocks to perform the designated functions or the blocks may represent functions performed in programming of a digital signal processor (DSP) or an application specific integrated circuit ASIC. The description of the

functionality of the present invention would enable one of ordinary skill to implement the present invention in a DSP or an ASIC without undue experimentation.
The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. The various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

WE CLAIM :
1. An apparatus for generating and encoding linear prediction coding (LPC)
coefficients in a linear predictive coder signal apparatus comprising: LPC
generator means for receiving digitized speech samples and generating a set of
LPC coefficients for said digitized speech samples in accordance with a linear
prediction coding format; line spectral cosine generator means for receiving said
set of LPC coefficients and generating a set of line spectral cosine values in
accordance with a line spectral cosine transform format; and line spectral square
root means for receiving said set of line spectral cosine values and for
generating a set of line spectral square root values in accordance with a square
roottrans formation format.
2. The apparatus of claim 1 wherein said line spectral square root means has
a square root transformation format defined by

where xi is the ith line spectral cosine value and yi is the corresponding ith line spectral square root value.

3. The apparatus as claimed in claim 1, wherein sensitivity computation means is provided for receiving said set of line spectral cosine values, said set of LPC coefficients, and a set of speech autocorrelation coefficients, and for computing a set of line spectral square root sensitivity coefficients in accordance with a weighted cross-correlation computation format.
4. The apparatus of claim 3, wherein said sensitivity computation means comprises polynomial division means for receiving said set of line spectral cosine values and a set of linear prediction coding (LPC) coefficients and for generating a set of quotient coefficients in accordance with a predetermined polynomial division format.
5. The apparatus of claim 4, wherein said sensitivity computation means
comprises a sensitivity autocorrelation means for receiving said set of quotient
coefficients and generating a set of sensitivity autocorrelation values for said set
of quotient coefficients in accordance with a predetermined autocorrelation
format.
6. The apparatus as claimed in claim 5 wherein said vector computation
means computes two vectors P and Q in said set of vectors in accordance with
the equations:

7. The apparatus as claimed in claim 6 wherein said polynomial division
means provides said set of quotient coefficients Jj for odd line spectral square
root values in accordance with the equation:

where z is the polynomial variable, Xj is the ith line spectral cosine value, and N is the number of filter taps.
8. The apparatus as claimed in claim 6, wherein said polynomial division
means provides said set of quotient coefficients Jj for even line spectral square
root values in accordance with the equation:

where z is the polynomial variable, Xj is the ith line spectral cosine value, and N is the number of filter taps.
9. The apparatus as claimed in claim 3 wherein said sensitivity cross
correlation means provides said line spectral square root sensitivity values in
accordance with the equation:

where Xi is the ith line spectral square root value, R(k) is the kth speech autocorrelation coefficient of the set of speech samples and Rji(k) is the kth autocorrelation coefficient of said set of quotient coefficients.
10. The apparatus as claimed in claim 1 wherein the LPC generator has an
input for receiving digitized speech samples and an output to provide a set of
LPC coefficients; the line spectral cosine generator has an input coupled to said
LPC generator output and an output; and the line spectral square root generator
has an input coupled to said line spectral cosine generator output and an output.
11. The apparatus as claimed in claim 10 wherein a polynomial division
calculator having an input is coupled to said line spectral square root generator
output and an output; and sensitivity cross correlation calculator having an input
is coupled to said polynomial division calculator output and an output.
12. The apparatus as claimed in claim 11 wherein a sensitivity autocorrelation calculator disposed between said polynomial division calculator and said sensitivity cross correlation calculator having an input coupled to said polynomial division calculator output and an output coupled to said sensitivity cross correlation calculator input.
13. An apparatus for generating and encoding linear prediction coding (LPC) coefficients in a linear predictive coder signal apparatus, substantially as hereinabove described and illustrated with reference to the accompanying drawings.

Documents:

1340-mas-1996 abstract duplicate.pdf

1340-mas-1996 abstract.pdf

1340-mas-1996 assignment.pdf

1340-mas-1996 claims duplicate.pdf

1340-mas-1996 claims.pdf

1340-mas-1996 correspondence others.pdf

1340-mas-1996 correspondence po.pdf

1340-mas-1996 description (complete) duplicate.pdf

1340-mas-1996 description (complete).pdf

1340-mas-1996 drawings.pdf

1340-mas-1996 form-1.pdf

1340-mas-1996 form-26.pdf

1340-mas-1996 form-4.pdf

1340-mas-1996 others.pdf

1340-mas-1996 petition.pdf

« Previous Patent

Next Patent »

Patent Number

196344

Indian Patent Application Number

1340/MAS/1996

PG Journal Number

30/2009

Publication Date

24-Jul-2009

Grant Date

Date of Filing

30-Jul-1996

Name of Patentee

QUALCOMM INCORPORATED.,

Applicant Address

6455 LUSK BOULEVARD, SAN DIEGO, CALIFORNIA 92121

Inventors:

#	Inventor's Name	Inventor's Address
1	WILLAM R. GARDEN	4650 EXBURY COURT, SAN DIEGO, CALIFORNIA 92130
2	SHARATH MANJUNATH	12682 TORREY BLUFF DRIVE, #235, SAN DIEGO, CALIFORNIA 92122
3	PETER A. MONTA TORREY BLUFF DRIVE	624, SAN DIEGO, CALIFORNIA 92122

PCT International Classification Number

206G

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	08/509,848	1995-08-01	U.S.A.