Linear Prediction Models (Vaseghi - Advanced Digital Signal Processing and Noise Reduction)

Advanced Digital Signal Processing and Noise Reduction, Second Edition.Saeed V. VaseghiCopyright © 2000 John Wiley & Sons LtdISBNs: 0-471-62692-9 (Hardback): 0-470-84162-1 (Electronic)x(m)e(m)u(m)G8x(m–P)a1a2aP–1 ...zz– 1x(m – 2)z–1x(m – 1)LINEAR PREDICTION MODELS8.18.28.38.48.58.68.7Linear Prediction CodingForward, Backward and Lattice PredictorsShort-term and Long-Term Linear PredictorsMAP Estimation of Predictor CoefficientsSub-Band Linear PredictionSignal Restoration Using Linear Prediction ModelsSummaryLinear prediction modelling is used in a diverse area of applications,such as data forecasting, speech coding, video coding, speechrecognition,model-basedspectralanalysis,model-basedinterpolation, signal restoration, and impulse/step event detection.

In thestatistical literature, linear prediction models are often referred to asautoregressive (AR) processes. In this chapter, we introduce the theory oflinear prediction modelling and consider efficient methods for thecomputation of predictor coefficients. We study the forward, backward andlattice predictors, and consider various methods for the formulation andcalculation of predictor coefficients, including the least square error andmaximum a posteriori methods. For the modelling of signals with a quasiperiodic structure, such as voiced speech, an extended linear predictor thatsimultaneously utilizes the short and long-term correlation structures isintroduced.

We study sub-band linear predictors that are particularly usefulfor sub-band processing of noisy signals. Finally, the application of linearprediction in enhancement of noisy speech is considered. Furtherapplications of linear prediction models in this book are in Chapter 11 onthe interpolation of a sequence of lost samples, and in Chapters 12 and 13on the detection and removal of impulsive noise and transient noise pulses.Linear Prediction Models228x(t)PXX(f)ft(a)PXX(f)x(t)tf(b)Figure 8.1 The concentration or spread of power in frequency indicates thepredictable or random character of a signal: (a) a predictable signal;(b) a random signal.8.1 Linear Prediction CodingThe success with which a signal can be predicted from its past samplesdepends on the autocorrelation function, or equivalently the bandwidth andthe power spectrum, of the signal.

As illustrated in Figure 8.1, in the timedomain, a predictable signal has a smooth and correlated fluctuation, and inthe frequency domain, the energy of a predictable signal is concentrated innarrow band/s of frequencies. In contrast, the energy of an unpredictablesignal, such as a white noise, is spread over a wide band of frequencies.For a signal to have a capacity to convey information it must have adegree of randomness. Most signals, such as speech, music and videosignals, are partially predictable and partially random.

These signals can bemodelled as the output of a filter excited by an uncorrelated input. Therandom input models the unpredictable part of the signal, whereas the filtermodels the predictable structure of the signal. The aim of linear prediction isto model the mechanism that introduces the correlation in a signal.Linear prediction models are extensively used in speech processing, inlow bit-rate speech coders, speech enhancement and speech recognition.Speech is generated by inhaling air and then exhaling it through the glottisand the vocal tract. The noise-like air, from the lung, is modulated andshaped by the vibrations of the glottal cords and the resonance of the vocaltract.

Figure 8.2 illustrates a source-filter model of speech. The sourcemodels the lung, and emits a random input excitation signal which is filteredby a pitch filter.Linear Prediction Coding229Pitch periodRandomsourceExcitationVocal tractmodelH(z)Glottal (pitch)modelP(z)SpeechFigure 8.2 A source–filter model of speech production.The pitch filter models the vibrations of the glottal cords, and generates asequence of quasi-periodic excitation pulses for voiced sounds as shown inFigure 8.2.

The pitch filter model is also termed the “long-term predictor”since it models the correlation of each sample with the samples a pitchperiod away. The main source of correlation and power in speech is thevocal tract. The vocal tract is modelled by a linear predictor model, which isalso termed the “short-term predictor”, because it models the correlation ofeach sample with the few preceding samples.

In this section, we study theshort-term linear prediction model. In Section 8.3, the predictor model isextended to include long-term pitch period correlations.A linear predictor model forecasts the amplitude of a signal at time m,x(m), using a linearly weighted combination of P past samples [x(m−1),x(m−2), ..., x(m−P)] asPxˆ (m) = ∑ a k x(m − k )(8.1)k =1where the integer variable m is the discrete time index, xˆ (m) is theprediction of x(m), and ak are the predictor coefficients. A block-diagramimplementation of the predictor of Equation (8.1) is illustrated in Figure 8.3.The prediction error e(m), defined as the difference between the actualsample value x(m) and its predicted value xˆ (m) , is given bye(m) = x(m) − xˆ(m)P= x(m ) − ∑ ak x(m − k)k =1(8.2)Linear Prediction Models230Input x(m)x(m–1)z –1x(m–2)z–1z –1a2a1a=x(m–P)...aP–1Rxx rxxLinear predictor^x(m)Figure 8.3 Block-diagram illustration of a linear predictor.For information-bearing signals, the prediction error e(m) may be regardedas the information, or the innovation, content of the sample x(m).

FromEquation (8.2) a signal generated, or modelled, by a linear predictor can bedescribed by the following feedback equationx (m) =P∑ ak x (m − k ) +e (m)(8.3)k =1Figure 8.4 illustrates a linear predictor model of a signal x(m). In this model,the random input excitation (i.e. the prediction error) is e(m)=Gu(m), whereu(m) is a zero-mean, unit-variance random signal, and G, a gain term, is thesquare root of the variance of e(m):()1/ 2G = E [e 2 (m)](8.4)x(m)e(m)u(m)Gx(m–P)a1a2aPz–1...z –1x(m–2)z–1x(m–1)Figure 8.4 Illustration of a signal generated by a linear predictive model.Linear Prediction Coding231H(f)pole-zerofFigure 8.5 The pole–zero position and frequency response of a linear predictor.where E[·] is an averaging, or expectation, operator. Taking the z-transformof Equation (8.3) shows that the linear prediction model is an all-pole digitalfilter with z-transfer functionH ( z) =X ( z)=U ( z)G(8.5)P1 − ∑ a k z −kk =1In general, a linear predictor of order P has P/2 complex pole pairs, and canmodel up to P/2 resonance of the signal spectrum as illustrated in Figure 8.5.Spectral analysis using linear prediction models is discussed in Chapter 9.8.1.1 Least Mean Square Error PredictorThe “best” predictor coefficients are normally obtained by minimising amean square error criterion defined as2P E[e (m)]=E  x(m) −∑ a k x(m − k )   k =12PPPk =1j =1=E [ x (m)]− 2∑ a k E [ x(m) x(m − k )]+ ∑ a k ∑ a j E [x(m − k ) x(m − j )]2k =1Ta= rxx (0) − 2r xxT+ a R xx a(8.6)Linear Prediction Models232where Rxx =E[xxT] is the autocorrelation matrix of the input vectorxT=[x(m−1), x(m−2), .

. ., x(m−P)], rxx=E[x(m)x] is the autocorrelationvector and aT=[a1, a2, . . ., aP] is the predictor coefficient vector. FromEquation (8.6), the gradient of the mean square prediction error with respectto the predictor coefficient vector a is given by∂T+ 2a T RxxE[e 2 (m)] = − 2rxx∂a(8.7)where the gradient vector is defined as∂  ∂∂∂ =,, ,∂ a  ∂ a1 ∂ a 2∂ aP T(8.8)The least mean square error solution, obtained by setting Equation (8.7) tozero, is given byRxx a = rxx(8.9)From Equation (8.9) the predictor coefficient vector is given by−1a = R xxr xx(8.10)Equation (8.10) may also be written in an expanded form asrxx (1)rxx ( 2) a1   rxx ( 0)  rxx (0)rxx (1) a 2   rxx (1) a  =  r ( 2)rxx (1)rxx (0) 3   xx   a   r ( P − 1) r ( P − 2) r ( P − 3) P   xxxxxx rxx ( P − 1)  − 1 rxx (1)   rxx ( P − 2)   rxx ( 2)  rxx ( P − 3)   rxx (3)    rxx (0)   rxx ( P ) (8.11)An alternative formulation of the least square error problem is as follows.For a signal block of N samples [x(0), ..., x(N−1)], we can write a set of Nlinear prediction error equations asLinear Prediction Coding233 e(0)   x( 0)   x ( −1)   e(1)   x (1)   x ( 0) e( 2)  =  x ( 2)  −  x(1)        e( N − 1)   x( N − 1)   x ( N − 2)    a1  x ( −1)x ( −2)x (1 − P )   a 2 x ( 0)x ( −1)x ( 2 − P )   a3    x ( N − 3) x ( N − 4)x ( N − P − 1)   a P (8.12)Twhere x = [x(−1), ..., x(−P)] is the initial vector.

In a compact vector/matrixnotation Equation (8.12) can be written asx ( −2)x ( −3)x( − P )e = x − Xa(8.13)Using Equation (8.13), the sum of squared prediction errors over a block ofN samples can be expressed ase T e = x T x − 2 x T Xa − a T X T Xa(8.14)The least squared error predictor is obtained by setting the derivative ofEquation (8.14) with respect to the parameter vector a to zero:∂e T e= − 2xT X − aT X T X = 0∂a(8.15)From Equation (8.15), the least square error predictor is given by(a= X T X)−1(X T x )(8.16)A comparison of Equations (8.11) and (8.16) shows that in Equation (8.16)the autocorrelation matrix and vector of Equation (8.11) are replaced by thetime-averaged estimates asrˆxx (m) =1 N −1∑ x ( k ) x ( k − m)N k =0(8.17)Equations (8.11) and ( 8.16) may be solved efficiently by utilising theregular Toeplitz structure of the correlation matrix Rxx.

In a Toeplitz matrix,Linear Prediction Models234all the elements on a left–right diagonal are equal. The correlation matrix isalso cross-diagonal symmetric. Note that altogether there are only P+1unique elements [rxx(0), rxx(1), . . . , rxx(P)] in the correlation matrix and thecross-correlation vector. An efficient method for solution of Equation (8.10)is the Levinson–Durbin algorithm, introduced in Section 8.2.2.8.1.2 The Inverse Filter: Spectral WhiteningThe all-pole linear predictor model, in Figure 8.4, shapes the spectrum ofthe input signal by transforming an uncorrelated excitation signal u(m) to acorrelated output signal x(m). In the frequency domain the input–outputrelation of the all-pole filter of Figure 8.6 is given byX( f )=GU( f )=A( f )E( f )P1− ∑ a k e(8.18)− j2πfkk =1where X(f), E(f) and U(f) are the spectra of x(m), e(m) and u(m) respectively,G is the input gain factor, and A(f) is the frequency response of the inversepredictor.