Transform Vector Quantization for Adaptive Predictive Coding

The present invention relates to digital signal transmission systems, and more specifically to digital signal transmission systems using adaptive predictive coding techniques.

Adaptive predictive coding (APC) methods are widely used for high quality coding of speech signals. The details are discussed in U.S. patent application Ser. No. 07/603,104 by the present inventor and commonly assigned to COMSAT and which issued as U.S. Pat. No. 5,206,884 on Apr. 27, 1993. That application is herein incorporated by reference.

The concept of prediction filtering followed by residual quantization forms the basis for a wide range of coding techniques at various bit rates and quality for voice signals. The most direct implementation of this concept is found in adaptive predictive coding (APC) (B. S. Atal, "Predictive Coding of Speech at Low Bit Rates," IEEE Transactions on Communications, Vol. Com-30, No 4, April 1982). In APC, signal correlations are significantly reduced by adaptive short and long term prediction filters. The residual signal is then quantized by an adaptive quantizer, inside a quantization noise feedback loop. The adaptation ensures that the parameters of the predictors and the quantizer match the characteristics of the quasistationary input signal, so that the efficiency of these operations is maximized. In forward block adaptation, the signal is processed in blocks and parameters are determined for each block based on the uncoded signal. This form of adaptation requires the transmission of the prediction and quantization parameters along with the transmission of the residual. Backward sample adaptation is also possible, leading to analysis by synthesis schemes such as the low delay code excited linear prediction (LD-CELP). The proposed invention is relevant to the forward adaptive schemes.

The size of the block is highly dependent on signal characteristics and in particular on the quasistationary behavior of the signal. For telephony voice signals, sampling rates are generally in the range 6.4-8 kHz. At these sampling rates, block sizes are in the range 160-256 sample/block. For generality, block size will be denoted by N in the following discussion.

Prediction is usually carried out in two states: a short delay predictor that removes adjacent sample correlations followed by a long delay predictor that removes correlations at longer delays. For voice signals, the short delay predictor removes the resonances due to the vocal cavity formants and the long delay predictor removes the periodicity introduced by the pitch periodic glottal excitation during voiced sounds. The short term prediction filter is defined by its transfer function S(z): ##EQU1## where M is the order of short term prediction, usually 8-16, and {a.sub.m, 1.ltoreq.m.ltoreq.M} are the linear prediction coding (LPC) coefficients. Similarly, the long term prediction filter transfer function L(z) is given by: ##EQU2## where p is the delay value (for voice signals usually equalling the pitch period, limited to 20<p<120 at 6.4-8 kHz sampling rates), and {c.sub.m,p-1.ltoreq.m.ltoreq.p+1} are the long term prediction parameters. For each input signal block of N samples, these parameters (i.e., {a.sub.m }, {c.sub.m } and p) are determined by well known methods, (L. R. Rabiner and R. W. Schafer, "Digital Processing of Speech Signals," Prentice-Hall, Inc., Englewood Cliffs, N.J. (1978)), quantized for transmission and used for performing the prediction filtering operations. For telephony voice, about 64 bits are needed for adequate quantization of the parameters for each block of the input signal.

Let {x(i), 0.ltoreq.i<N} denote the current block of N samples. The prediction residual r(i) is obtained by

The residual signal has to be quantized at a low bit rate, typically at 1-2 bit/sample. For example, for encoding voice sampled at 6.4 kHz at 16 kbit/s rate, 2 bits are available for the quantization of each sample of the residual signal. Quantization has to be carried out such that the quantization resultant impairment in the reconstructed version of the input signal is minimized (N. S. Jayant and P. Noll, "Digital Coding of Waveforms," Prentice-Hall, Inc., Englewood Cliffs, N.J. (1984)). For voice and audio signals, it is also important to minimize the impairment as perceived by the human ear. In order to realize this goal, the auditory masking properties of the human ear must be taken into account during residual quantization.

In APC, the residual is quantized inside a feedback loop which filters the quantization noise through a noise shaping filter 1 and sums the result using adder 2 with the residual to form the quantizer 3 input. The scheme is shown in FIG. 1. It should be noted that time domain samples are quantized directly. The power spectrum of the reconstruction noise is controlled by the transfer function of the feedback filter. The desired spectral shaping is achieved by using a feedback filter with the transfer function F(z) given by:

where .beta. is limited by 0.ltoreq..beta..ltoreq.1 and is usually 0.7.

There are two main disadvantages to the above scheme. First, due to the noise feedback, the variance of the quantizer input signal is higher than the variance of the residual. This is especially true due to the low rate quantization. As a result, the performance of the quantizer, referenced to the residual variance, will be reduced. Secondly, and more significantly, the feedback loop may become unstable if the power gain through the feedback filter becomes large. This can occur during signals of large spectral dynamic range such as sinusoids and resonant voiced sounds. Controlling the stability by limiting the power gain usually results in a loss in the overall performance of the codec.

It is an object of the present invention to obtain quantization of a residual signal without the disadvantages discussed above with respect to the prior art.

This invention pertains to a method and apparatus for quantizing a residual signal that is encountered in predictive coding techniques. These techniques are commonly applied to voice and audio signals to reduce the bit rate required for transmission while maintaining a certain level of quality. In particular, the proposed technique is applicable to transmission of signals at the rate of 1-2 bit/sample while maintaining subjective transparent quality.

In predictive coding, reduction in transmission bit rate is accomplished by the removal of signal redundancies by prediction filtering. The prediction filtering operation results in a residual signal whose information content is highly nonredundant and has to be quantized by a low rate quantizer and transmitted to the receiver. The residual quantization is crucial since it determines to a large extent the quality that is attainable by the technique at a given bit rate.

Existing approaches to residual quantization at the above transmission rates are usually implemented in the time domain. This invention proposes the Transform Domain Vector Quantization (TVQ), a novel approach to implementing the residual quantization. Here, the residual is first transformed from the time domain to a transform domain by an orthogonal transform such as the discrete cosine transform (DCT). The resulting transform coefficients are grouped into vectors. This grouping is performed in an adaptive manner, based on the spectral power distribution of the input signal. The bits available for the transmission of the residual signal are divided equally among the vectors. Each of these vectors is quantized by a vector quantizer. A weighting function that takes into account the auditory noise masking properties of the human ear as well as the synthesis filter response characteristics is used to select the optimum code vector to represent each transform coefficient vector.

At the receiver, the adaptive vector formation is reconstructed and the transform coefficients are decoded. These are then inverse transformed to yield a (quantized) residual signal. This signal is used at the input to the synthesis filters to regenerate the input signal.

The proposed invention addresses the residual quantization aspect of predictive coding. In TVQ, the residual signal is transformed into a transform domain. In the transform domain, quantization and spectral shaping are implemented as open loop operations. Consequently, the problem of instability does not arise. For the same reason, increase in the variance of the residual is also not encountered. In addition, the transform domain operation is a block quantization scheme that is easily amendable to variable bit rate operation. Variations in sampling rate and bandwidth are also easily implemented.

FIG. 1 shows a prior art Noise Feedback Time Domain Quantization System;

FIG. 2 shows an encoder according to the present invention; and

FIG. 3 shows a decoder according to the present invention.

The proposed technique addresses the residual coding aspect of predictive coders. It is independent of the prediction analysis and filtering methods used in the coder, though prediction parameters are used for quantization and noise spectral shaping. Hence, in the following description, the prediction analysis and filtering will not be discussed further.

FIGS. 2 and 3 are block diagrams of the encoder and decoder that illustrate the TVQ method for the case of 8 kHz sampling rate, N=128 samples/block, and residual quantization with a total of 192 bits (equivalently 1.5 bit/transform coefficient). The prediction and quantization parameters are transmitted using 64 bits, resulting in a bit rate of 256 bits/block or 16 kbit/s. Clearly, by varying the sampling rate, the number of bits used for residual quantization (and parameter quantization to a more limited extent), other bit rate/bandwidth combinations can be obtained with corresponding variations in quality.

FIG. 2 shows the encoder of the present invention. Short term predictor circuit 21 and long term predictor circuit 22 are well known (and described in the above-referenced U.S. Pat. No. 5,206,884 and will thus not be described here further.

Transform Domain Vector Quantization circuit 23 includes DCT circuit 24, adaptive vector formation and normalization circuit 25, input signal power spectrum estimation circuit 26, codebook circuit 27 and quantizer 28. Multiplexer 29 is also shown.

In FIG. 3, for the decoder, analogous reference numerals (31-39) are used for analogous (to numerals 21-29 of FIG. 2) circuit elements.

The TVQ method can in general employ a broad class of orthogonal transforms. However, sinusoidal transforms such as the discrete cosine transform (DCT) and discrete fourier transform (DFT) have the advantage that the masking properties of the ear can be easily interpreted in the transform domain. For the sake of clarity and illustration, the DCT will be used in the following description. However, it should not be overlooked that a wide class of transforms can be substituted in place of the DCT without any major changes to the basic concept.

It is desirable to use a block size N that is an integer power of 2, to permit use of fast transform algorithms such as the fast fourier transform (FFT) and the fast cosine transform (FCT).

Let {r(i) ,0.ltoreq.i<N} be the residual samples being encoded. Domain transformation results in a set of transform coefficients {R(k), 0.ltoreq.k<N}. If DCT is used, transform coefficients are obtained by: ##EQU3## where,

DCT circuit 24 receives the time domain residual signal and transforms it into the frequency domain according to the above equations.

The set of N transform coefficients are grouped into L vectors, each of dimension D, such that N=LD by circuit 25. The dimension D and the number L of the vectors are design parameters that are determined apriori based on considerations such as computational complexity and storage requirements of the coder. For residual quantization at 1.5 bit/transform coefficient, which corresponds to the rates of interest here, a vector dimension of D=8 leads to a 12 bit codebook, which is of reasonable complexity. In this case, the N transform coefficients are grouped into N/8 vectors of dimension 8.

The grouping of transform coefficients into vectors is not arbitrary, but must satisfy an important requirements that depends upon the power spectral density of the input signal, as modeled by the short and long term prediction parameters. Let V be a vector of transform coefficients given by ##EQU4## where,

Let H(k) denote the synthesis filter frequency response at the frequency 2.pi.k/N. H(k) is expressed in terms of the short term predictor parameters {a.sub.i, 1.ltoreq.i.ltoreq.M} and long term predictor parameters p and {c.sub.i, p-1.ltoreq.i.ltoreq.p+1} as ##EQU5## Then each vector V=[R(i.sub.1)R(i.sub.2) . . . R(i.sub.D)].sup.T must satisfy the condition ##EQU6## In other words, the average log magnitude synthesis response for each vector must equal the average log magnitude synthesis response for all the transform coefficients. This condition ensures that all vectors have the same entropy, and hence can be quantized using the same number of bits. In general, the grouping is nonunique. Further, it is possible to generate extreme examples where such a grouping is not possible at all. However, for practical signals, a satisfactory grouping can always be obtained. Input signal power estimation circuit 26 supplies an estimate of the input signal power to the circuit 25 so that the above equations may be carried out by circuit 25. Circuit 26 produces an estimate of the input signal power from the long term and short term parameters in a well known fashion (as described in U.S. Pat. No. 5,206,884.

The formation of the vectors that meet the above requirements is performed by an adaptive grouping algorithm. A grouping that exactly meets the above condition usually requires a large amount of computation. As a result, in practice, a vector formation that approximately satisfies the above condition is used.

There are a number of approaches to constructing the adaptive grouping algorithm. Here, an approach based on progressive binary grouping is proposed that is suitable when the dimension D is an integer power of 2.

The algorithm initially forms groups of two transform coefficients such that the average log magnitude synthesis response for each pair is as close as possible to the overall average. This is accomplished by selecting each (ungrouped) transform coefficient and grouping it with the transform coefficient among the remaining (ungrouped) transform coefficients that makes the average of the pair closest to the overall average. In this manner, the N transform coefficients are grouped into ##EQU7## transform coefficient subgroups.

In the next pass, the subgroups are paired to form larger subgroups by using the same criterion as above. Each subgroup is treated as a unit and the transform coefficients that compose the subgroup are not separated. This process is repeated until groups of the desired dimension are obtained. In other words, to obtain vectors of dimension D, the algorithm also generates subvectors of dimension ##EQU8##

The adaptive vector formation can be recovered exactly at the decoder in the absence of channel impairments. This is since the algorithm uses quantized short term and long term parameters that are also available at the decoder.

The total available number of bits for the quantization of the residual signal is divided equally among the vectors. For example, if 192 bits are available for quantization of 128 transform coefficients divided into 8 dimensional vectors, each vector is quantized using a 12 bit codebook stored in codebook circuit 27. The codebooks are populated by random variates of a suitable distribution. If DCT is used, the codebook is populated by univariate, zero means Gaussian random variables. The transform coefficients are normalized to unit variance and the normalization constant is log quantized using 7 bits and transmitted to the decoder.

Each vector is quantized by quantizer circuit 28 by an exhaustive search in the codebook. The optimum codevector is determined by a total weighted squared error criterion. The weighting is determined by the long and short term predictor parameters and a noise masking parameter .beta.. The weighting coefficient for transform coefficient R(k) is w(k) which is given by ##EQU9## The noise masking parameter .beta. is usually between 0.7 and 0.9. Corresponding to the normalized transform coefficient vector V defined earlier, the weighting vector W is defined as ##EQU10## Then the weighted error measure E.sub.n between the transform coefficient vector V and the n.sup.th codevector U.sub.n is computed by

where * represents complex conjugation and T represents transposition. For real transforms such as the DCT the above expression simplifies to

Each transform coefficient vector is quantized to the codevector that results in the smallest error measure. The index of each codevector is sent to multiplexer 29 to be transmitted to the decoder, along with the bits encoding the short and long term parameters and the variance normalization factor.

A vector quantization technique is also disclosed in Ser. No. 07/732,024 involving the same inventor and assignee and is herein incorporated by reference.

At the decoder, as shown in FIG. 3, the predictor parameters are decoded and are used to determine the vector formation by circuit 35 by the same procedure as used at the encoder. Then the transform coefficient vectors are decoded by table look-up operations by circuit 38 in the codevector table in circuit 37. The transform coefficients are inverse transformed by circuit 34 to obtain the decoded version of the residual signal. Let {R'(k), 0.ltoreq.k<N} denote the decoded transform coefficients. The inverse transform, in the case of the DCT is given by ##EQU11## where,

and {r'(i),0.ltoreq.i<N} denotes the decoded version of the residual signal. This signal acts as the excitation to the cascade of long and short term synthesis filters (32 and 31, respectively) to generate the decoded version of the input signal. The transfer functions of the long and short term synthesis filters respectively are given by ##EQU12##

In summary, the following are important features of the invention:

1. The prediction residual is quantized in a transform domain.

2. The choice of the transform is not as crucial as in other frequency domain coders such as transform coders. Transforms based on the discrete cosine transform and discrete fourier transform may be used with equally good results.

3. The prediction residual is quantized by vector quantization, where the vectors are formed adaptively, depending on the spectral power distribution of the input signal.

Although specific examples of the invention have been set forth above, the invention is not to be so limited. The proper and intended scope of the invention is defined by the claims.