LPC Pole Encoding Using Reduced Spectral Shaping Polynomial

The present invention relates to method and apparatus for encoding speech signals.

It is highly desirable to be able to store and transmit speech signals using a reduced bandwidth. For example, if 8000 Hz of a speech signal is sampled at the Nyquist rate with 12-bit accuracy, the resulting data rate required is almost 200 kilobits per second of speech. Since the actual information content of speech is far smaller than this, it is extremely desirable to reduce the data rate required to encode speech down to something closer to the actual information content as received by a human listener. Such compressed speech coding has three principal areas of application, each of major importance: synthetic speech, transmission of spoken messages, and speech recognition.

A principal area of efforts to accomplish this end has been linear predictive coding of speech. In the general linear prediction model, a signal s.sub.n is considered to be the output of a system with an input u.sub.n such that the following relation hold: ##EQU1## where b.sub.0 is defined as one, and a.sub.k (k ranging over integers between l and p inclusive), and b.sub.m (m ranging over integers between l and q inclusive), and the gain G are the parameters of the hypothesized system. Since the signal s.sub.n is modeled as a linear function of past outputs and present and past inputs, linear prediction from these outputs and inputs specifies the value of s.sub.n.

A slightly simplified version of this model, which is much more tractable, is the autoregressive or all-pole model. In this model, the signal s.sub.n is assumed to be a linear combination of past values and of a single input value u.sub.n : ##EQU2## where G is a gain factor. By taking the z transform of both sides of this equation, the system transfer function H(z) is ##EQU3## Given a particular signal sequence s.sub.n, analysis according to this model requires that the predictor coefficients a.sub.k and the gain G be determined in some manner.

In the model of human speech upon which the present invention is based, the human voice is modeled as a combination of an excitation function with a linear predictive filter. Once the system has been analyzed according to this fashion, the excitation function can normally be transmitted at quite a low bit rate. However, the present invention is not directed to excitation function modeling, and conventional modeling, analysis, and encoding methods are used for this aspect. See generally Rabmer & Schafer, Digital Processing of Speech Signals (1978). Markel & Gray, Linear Prediction of Speech (1976); Atal et al, "Speech Analysis and Synthesis by Linear Prediction of the Speech Wave", 50 Journal of the Acoustical Society of America 637 (1971); Makharl "Linear Prediction: A Tutorial Review", 63 Proceedings IEEE p. 561 (1975); all of which are hereby incorporated by reference. Pitch and gain energy are commonly used as a minimum set of excitation parameters.

To represent speech in accordance with the LPC model, the predictor coefficients a.sub.k, or some equivalent set of parameters, must be transmitted so that the linear predictive model can be used to resynthesize the speech signal at the receiver. In the prior art, reflection coefficients have often been used as the transmitted parameters. The desirable features to be selected for, in deciding which set of parameters is to be transmitted to permit resynthesis of speech according to the LPC model, include: 1. The synthesized filter should be guaranteed stable. 2. The parameters transmitted should preferably correspond fairly closely to perceptual parameters, to permit perceptually efficient use of bandwidth. 3. A minimum computational load should be imposed, at both transmitting and (especially) receiving ends. 4. Preferably the parameters should have a natural ordering, so that an efficiently reduced set of parameters can be obtained by truncation.

Thus is an object of the present invention to provide a method for encoding speech according to the linear predictive coding model, such that the stability of the LPC filter is guaranteed, at minimum bit rate.

It is a further object of the present invention to provide a method for encoding speech parameters in accordance with the linear predictive coding model, such that the encoded parameters correspond closely to perceptual parameters and require minimum bit rate.

It is a further object of the present invention to provide a method for encoding speech for synthesis according to the linear predictive coding model at minimum bit rate, such that a minimium computational load is required to regenerate the encoded speech.

The present invention will be described with reference to the accompanying drawings, wherein:

FIG. 1 shows generally the sequence of steps used in practicing the method of the present invention for encoding speech;

FIG. 2 shows the sequence of steps required to reduce the number of parameters required for good-quality encoding of LPC poles; and

FIG. 3 shows generally the structure of a terminal used to synthesize speech encoded according to the present invention.

The present invention teaches encoding of speech, in the LPC model, by means of poles. Since the poles correspond fairly directly to formants, the poles are a perceptually efficient set of parameters to encode. Moreover, transmission of poles guarantees a stable resynthesized filter. The possibility of pole encoding has been discussed in the prior art, but the present invention teaches a novel method of pole coding which provides major advantages and incorporates a number of novel features.

In the present invention, a bandwidth threshold is used to select those poles which have a narrow bandwidth (i.e., high-Q poles) and all other poles are approximated by a single spectral shaping polynomial of fixed order, preferably of order two. Thus, the variable number of formants which occurs in actual speech is well approximated by a varying number of encoded poles, and great computational efficiency is preserved.

Reflection coefficients k.sub.i have been preferred in the past, since they alone among possible LPC filter parameters both guarantee filter stability and have a natural ordering. A natural ordering of the transmitted parameters permits the use of entropy coding (a coding method where the codeword length varies from parameter to parameter, so that the more frequently occurring parameters are assigned shorter codewords). for lower average bit rates. The only other set of equivalent parameters which guarantees the stability of the filter are the poles of the transfer function H(z). Unfortunately, the poles of H(z) do not have a natural ordering. Besides this lack of natural ordering, another reason why pole encoding in the prior art has not been more extensively considered is that finding the roots of a tenth or higher order polynomial is computationally very expensive. Thus, to obtain the formant structure of the speech spectrum, peak-picking methods have typically been used (i.e., direct comparison of amplitudes in the frequency domain), although this has great difficulties when formants merge or diverge, and does not facilitate adaptation to the variable number of formants.

A sample embodiment of the present invention proceeds as follows. First, a raw speech input is sampled at eight kilohertz and is represented by a tenth order LPC model. (A higher order LPC model can of course be alternatively used.) The all-pole model is now computed, according to equation (3), to produce estimations of the filter coefficients a.sub.i in the inverse filter polynomial ##EQU4##

These filter coefficients a.sub.k are computed as follows. The autocorrelation function R(i) is defined as ##EQU5## (In practice, since the autocorrelation is only computed over a finite interval, a window function may be used to restrict the range of computation of this function to the desired practical limit.)

The result of the foregoing prior art operations is the complete set of P (e.g. ten) filter coefficients a.sub.k. The present invention now proceeds to find the poles of the transfer function H(z), which are the roots of the polynomial A(z). A modification of the Bairstow root-finding method is preferably used to accomplish this.

When a function is known in the complex plane, the Bairstow method may be used to find the roots. (See for example Hildebrand, Introduction to Numerical Analysis, McGraw Hill, 2nd Edition, 1956, pp. 613-617). The present invention introduces four innovations into the conventional Bairstow method, which provide greater efficiency in the context of the present speech problem. The preceding prior art steps have defined the function A(z) as a function of a complex variable z. The next step in the method of the present invention is to find the zeros of this complex function. Five equally spaced points are first defined on the top half of the unit circle (in the complex plane of the independent variable z). The Bairstow root-finding method is performed to 100 iterations on each initial guess. If no convergence is found within 100 iterations, the next starting point on the unit half circle is chosen, and the modified Bairstow method is started again. However, if a zero is found, the function A(z) may now reduced. That is, whenever a root r is found, the function (1-rz.sup.-1) is necessarily a factor of the polynomial. Moreover, since all the filter coefficients a.sub.k are real, all the complex roots of the inverse filter polynomial A(z) will come in conjugate pairs. That is, if a complex root r exists, a quadratic factor 1+(r+r*)z.sup.-1 +.vertline.r.vertline..sup.2 z.sup.-2 may be factored out of the polynomial, where r* represents the complex conjugate of r. Once a root has been found, the reduced polynomial A'(z) (that is, the remainder polynomial after the quadratic factor corresponding to the just-found root has been factored out of the polynomial A(z)) is then calculated, and the modified root-finding method just discussed is begun over again.

Moreover, several other novel features have been introduced in the Bairstow root-finding algorithm method itself, to better adapt it to the needs of the present invention. First, the prior art normally teaches a percentage convergence test, to ascertain whether the successive guesses generated by the Bairstow method are converging on a root. However, in the present invention, since it is known that all roots are within the unit circle (because the filter is guaranteed stable), each quadratic factor corresponding to a desired root may be represented as z.sup.-2 +F.sub.1 z.sup.-1 +F.sub.2 where F.sub.1 equals twice the real part of the root, and F.sub.2 equals the square of the absolute value of the root. Thus, F.sub.1 necessarily has a magnitude less than two, and F.sub.2 necessarily has a magnitude less than 1. In the present invention, the successive estimates of these values are subjected to an absolute convergence test, e.g. a total change of less than one over one million in the two parameters combined. Second, since we know that all roots of interest are within the unit circle, the maximum step size is limited preferably to one. Third, to prevent oscillation, a damping factor is applied: if the successive differences between successive estimates of either F.sub.1 or F.sub.2 change sign, the later difference in successive guesses is damped by (e.g.) 20%. That is, if successive guesses generated by the Bairstow method are F.sub.1, F.sub.1 +a, and F.sub.1 +a-b, where a and b are both positive, the last guess is corrected to F.sub.1 +a-(0.8.times.b).

Repetition of the foregoing steps provides all roots of the polynomial A(z). A further innovative step in the present invention is then applied. In speech coding, the narrow-bandwidth poles correspond to the perceptually important formants. However, since the set of formants is very often less than four, and may be none at all, a variety of wide-bandwidth poles (i.e., roots of the polynomial A(z) which lie close to the origin) will typically also be found. These poles are only important for spectral shaping. A key innovation of the present invention is to approximate all of these wide-bandwidth poles with a single reduced order (preferably second order) spectral shaping polynomial. This is accomplished as follows.

First, a bandwidth threshold is imposed. 300 Hz has been empirically determined as a desirable bandwidth threshold, since formants will typically have a threshold substantially less than this. Alternative constant values for the bandwidth threshold may alternatively be selected, but a threshold in the neighborhood of 200 to 700 Hz is believed to be most desirable. A bandwidth of 300 Hz corresponds to an amplitude value of 0.889. Phase and amplitude of the root values are transformed, to minimize the effect of quantization error, as discussed below.

Thus, the bandwidth limitation is used to segregate the roots of the polynomial A(z) into four or fewer formant factors (1+(r.sub.i +r.sub.i *)z.sup.-1 +.vertline.r.sub.i .vertline..sup.2 z.sup.-2), plus a residual polynomial A'. That is, the polynomial A(z) is now expressed as follows:

where A'(z) is a residual polynomial, having a degree between 2 and 10, which represents all the broad-bandwidth (spectral shaping) poles, together with the real roots if any.

The next cirtical step in the present invention is to efficiently approximate the residual polynomial A'(z) by means of a reduced residual polynomial A"(z). This is done by exploiting the natural ordering of reflection coefficients k.sub.i, as discussed above. First, the residual polynomial A'(z) is transformed into a reflection coefficient representation. This is preferably done, by the following (prior art) recursive procedure. (The parameter i is used here as a recursion parameter, which is initially set equal to q, and gradually decremented down to one.) First, (for each i) k.sub.i is set equal to a.sub.i,i, where a.sub.q,k is defined as the coefficient a.sub.k of the qth order residual polynomial A'(z). Next, a reduced set of coefficients is derived as follows: ##EQU6## The parameter i is then decremented, and the above cycle is repeated, until i=1. The result of this is a complete set of reflection coefficients, k.sub.1, . . . k.sub.q, which represent the residual polynomial A'(z).

The natural ordering of the reflection coefficients k.sub.i is now exploited to obtain a minimal and efficient reduced (second order) residual polynomial A"(z). This is done simply by discarding all the k.sub.i after k.sub.1 and k.sub.2. The a.sub.k s corresponding to the reduced residual polynomial A"(z) are now regenerated by the simple formula a.sub.0 =1,a.sub.1 =k.sub.1 (1+k.sub.2), a.sub.2 =k.sub.2. Thus, all of the residual wide-bandwidth poles are efficiently approximated by a single reduced residual polynomial A"(z).

Thus, efficient coding of speech according to an LPC model is now permitted. In combination with the required coding of the excitation function (typically pitch and gain are encoded), the present invention permits the transfer function H(z) of the LPC filter to be encoded as follows: two bits are used to indicate the number of poles currently separately being transmitted; a phase and amplitude value are encoded for each of the (four or fewer) narrow-bandwidth poles; and first and second reflection coefficients are encoded to represent the reduced residual polynomial.

A further transformation of these parameters may be used to minimize the perceptual impact of quantization error. That is, when these quantities are digital encoded for transmission, the perceptual importance of a least-significant-bit error in any parameter should be approximately the same. To accomplish this, the parameters derived are preferably transformed as follows: The phase (of poles in the complex plane) .theta.: is transformed to Mel-center frequency: ##EQU7## where f.sub.s equals the sampling frequency. The amplitude r.sub.i of each root is transformed to bandwidth ##EQU8## or alternatively to log-amplitude A.sub.i =20 log.sub.10 (1-r.sub.i). The reflection coefficients k.sub.i are preferably encoded as the logarithms of the respective area ratios. Empirical probability distributions of these parameters are optionally used to permit more efficient coding.

Thus, the present invention requires the following apparatus: means for sampling a speech signal; means for defining an LPC inverse filter polynomial corresponding to said speech signal; means for finding the roots of said inverse filter polynomial; means for encoding all of said roots of said inverse filter polynomial which have bandwidth greater than a threshold bandwidth; means for multiplying together roots of said inverse filter polynomial which do not have a bandwidth greater than said threshold bandwidth, to produce a residual polynomial; means for defining reflection coefficients corresponding to said residual polynomial; means for encoding parameters corresponding to a truncated set of said reflection coefficients of said residual polynomial. In the presently preferred embodiment of the invention, the sampling means is embodied in a conventional A/D converter and sample-and-hold circuit, and all the other said means are embodied in a VAX 11/780 computer. A listing of sample programming for a VAX computer is appended.

The present invention is applicable not only to real-time speech communication but also to packet speech communication and to stored sythetic speech. At the receiver, the pole parameters are reconverted to reflection coefficients, permitting LPC synthesis of speech in accordance with these parameters and the pitch and gain. ##SPC1## ##SPC2## ##SPC3## ##SPC4## ##SPC5## ##SPC6## ##SPC7## ##SPC8## ##SPC9##