# Linear prediction

Linear prediction

Linear prediction is a mathematical operation where future values of a discrete-time signal are estimated as a linear function of previous samples.

In digital signal processing, linear prediction is often called linear predictive coding (LPC) and can thus be viewed as a subset of filter theory. In system analysis (a subfield of mathematics), linear prediction can be viewed as a part of mathematical modelling or optimization.

The prediction model

The most common representation is

:$widehat\left\{x\right\}\left(n\right) = -sum_\left\{i=1\right\}^p a_i x\left(n-i\right),$

where $widehat\left\{x\right\}\left(n\right)$ is the predicted signal value, $x\left(n-i\right)$ the previous observed values, and $a_i$ the predictor coefficients. The error generated by this estimate is

:$e\left(n\right) = x\left(n\right) - widehat\left\{x\right\}\left(n\right),$

where $x\left(n\right)$ is the true signal value.

These equations are valid for all types of (one-dimensional) linear prediction. The differences are found in the way the parameters $a_i$ are chosen.

For multi-dimensional signals the error metric is often defined as

:$e\left(n\right) = |x\left(n\right) - widehat\left\{x\right\}\left(n\right)|,$

where $|.|$ is a suitable chosen vector norm.

Estimating the parameters

The most common choice in optimization of parameters $a_i$ is the root mean square criterion which is also called the autocorrelation criterion. In this method we minimize the expected value of the squared error E [e2(n)] , which yields the equation

:$sum_\left\{i=1\right\}^p a_i R\left(i-j\right) = -R\left(j\right),$

for 1 &le; "j" &le; "p", where "R" is the autocorrelation of signal "x""n", defined as

:$R\left(i\right) = E\left\{x\left(n\right)x\left(n-i\right)\right\},$

where "E" is the expected value. In the multi-dimensional case this corresponds to minimizing the L2 norm.

The above equations are called the normal equations or Yule-Walker equations. In matrix form the equations can be equivalently written as

:$Ra = -r,,$

where the autocorrelation matrix "R" is a symmetric, Toeplitz matrix with elements "r""i","j" = "R"("i" − "j"), vector "r" is the autocorrelation vector "r""j" = "R"("j"), and vector "a" is the parameter vector.

Another, more general, approach is to minimize

:$e\left(n\right) = x\left(n\right) - widehat\left\{x\right\}\left(n\right) = x\left(n\right) + sum_\left\{i=1\right\}^p a_i x\left(n-i\right) = sum_\left\{i=0\right\}^p a_i x\left(n-i\right)$

where we usually constrain the parameters $a_i$ with $a_0=1$ to avoid the trivial solution. This constraint yields the same predictor as above but the normal equations are then

:$Ra = \left[1, 0, ... , 0\right] ^\left\{mathrm\left\{T$

where the index "i" ranges from 0 to "p", and "R" is a ("p" + 1) &times; ("p" + 1) matrix.

Optimisation of the parameters is a wide topic and a large number of other approaches have been proposed.

Still, the autocorrelation method is the most common and it is used, for example, for speech coding in the GSM standard.

Solution of the matrix equation "Ra" = "r" is computationally a relatively expensive process. The Gauss algorithm for matrix inversion is probably the oldest solution but this approach does not efficiently use the symmetry of "R" and "r". A faster algorithm is the Levinson recursion proposed by Norman Levinson in 1947, which recursively calculates the solution. Later, Delsarte et al. proposed an improvement to this algorithm called the split Levinson recursion which requires about half the number of multiplications and divisions. It uses a special symmetrical property of parameter vectors on subsequent recursion levels.

References

Original

* G. U. Yule. On a method of investigating periodicities in disturbed series, with special reference to wolfer’s sunspot numbers. Phil. Trans. Roy. Soc., 226-A:267–298, 1927.

Overview

* J. Makhoul. Linear prediction: A tutorial review. Proceedings of the IEEE, 63 (5):561–580, April 1975.
* M. H. Hayes. Statistical Digital Signal Processing and Modeling. J. Wiley & Sons, Inc., New York, 1996.

* [http://labrosa.ee.columbia.edu/matlab/rastamat/ PLP and RASTA (and MFCC, and inversion) in Matlab]

* Forecasting
* Prediction interval
* Deconvolution

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Linear prediction — Lineare Vorhersage (engl. linear prediction) ist ein mathematisches Verfahren der Zeitreihenanalyse, welches zukünftige Werte eines Signals beziehungsweise einer diskreten Zeitreihe als eine lineare Funktion der Werte der Vergangenheit der… …   Deutsch Wikipedia

• linear prediction coding — tiesinis numatomasis kodavimas statusas T sritis radioelektronika atitikmenys: angl. linear prediction coding vok. lineare Vorhersagekodierung, f rus. кодирование с линейным предсказанием, n pranc. codage par prédiction linéaire, m …   Radioelektronikos terminų žodynas

• Code-excited linear prediction — (CELP) is a speech coding algorithm originally proposed by M.R. Schroeder and B.S. Atal in 1985. At the time, it provided significantly better quality than existing low bit rate algorithms, such as residual excited linear prediction and linear… …   Wikipedia

• Code excited linear prediction — (CELP) is a speech coding algorithm originally proposed by M.R. Schroeder and B.S. Atal in 1985. At the time, it provided significantly better quality than existing low bit rate algorithms, such as RELP and LPC vocoders (e.g. FS 1015). Along with …   Wikipedia

• Vector sum excited linear prediction — (VSELP) is a speech coding method used in the IS 54 standard. This codec was used in early TDMA cell phones in the United States. It was also used in the first version of RealAudio for audio over the Internet. The IS 54 VSELP standard was… …   Wikipedia

• Code-Excited Linear Prediction — Prinzipaufbau des CELP Decoders Code( book) Excited Linear Prediction (CELP) ist ein hybrides Verfahren zur Audiodatenkompression, das die Vorteile der Signalformkodierung mittels Vektorquantisierung und der parametrischen Verfahren vereint. Das… …   Deutsch Wikipedia

• Algebraic code excited linear prediction — (ACELP) is a speech encoding algorithm where a limited set of pulses is distributed as excitation to linear prediction filter.The ACELP method is widely employed in current speech coding standards such as AMR, EFR, AMR WB and ITU T G series… …   Wikipedia

• Residual-excited linear prediction — (RELP) is an obsolete speech coding algorithm. It was originally proposed in the 1970s and can be seen as an ancestor of Code Excited Linear Prediction (CELP). Unlike CELP however, RELP directly transmits the residual signal. To achieve lower… …   Wikipedia

• Algebraic Code Excited Linear Prediction — Der Algebraic Code Excited Linear Prediction, abgekürzt ACELP, stellt einen patentierten Vocoder der Firma VoiceAge Corporation dar, welcher bei der verlustbehafteten Kompression von Sprachsignalen im Telekommunikationsbereich Anwendung findet.… …   Deutsch Wikipedia

• Code-book Excited Linear Prediction — Code( book) Excited Linear Prediction (CELP) ist ein hybrides Audiokompressionsverfahren, das die Vorteile der Signalformkodierung mittels Vektorquantisierung und der parametrischen Verfahren vereint. Das Ergebnis ist eine gute Sprachqualität,… …   Deutsch Wikipedia