Encyclopedia > Linear prediction

Article Content

Linear prediction

Linear prediction is a mathematical operation where future values of a digital signal is 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 most common representation is

$x'(n) = \sum_{i=1}^p a_i x(n-i)$

where $x'(n)$ is the estimated signal value, $x(n)$ the previous values, and $a_i$ the predictor coefficients. The error generated by this estimate is

$e(n) = x(n) - x'(n)$

where $x(n)$ is the true signal value and $x'(n)$ the estimated 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 is often defined as

$e(n) = ||x(n) - x'(n)||$

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

The most common choice in optimisation of parameters $a_i$ is the root mean square criterion which is also called the autocorrelation criterion. In this method we minimise the expected value of the squared error $E\{e^2(n)\}$, which yields the equation

$\sum_{i=1}^p a_i R(i-j) = -R(j)$, for $1 <= j <= p$,

where $R$ is the autocorrelation of signal $x(n)$ defined as $R(i) = E\{x(n)x(n-i)\}$ In the multi-dimensional case this corresponds to minimising the L 2 norm.

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

$R*a = 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 of $a_i$.

Another more general approach is to minimise

$e(n) = \sum_{i=0}^p a_i x(n-i)$

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

$R*a = [1, 0, ... , 0]^T$

where vector $a_i$ ranges from 0 to $p$ and the size of $R$ is $p+1$ times $p+1$.

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 $R*a = 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 N. 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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Canadian Charter of Rights and Freedoms ... the Canadian Charter contains a provision, called the notwithstanding clause, by which some guarantees can be overridden through a legislative enactment ...