Solve a linear system of equations using Levinson-Durbin recursion.
Library
Signal Operations, in General DSP
Description
The Levinson-Durbin block solves the nth-order system of linear equations
for the particular case where R is a symmetric, positive-definite Toeplitz matrix and b is identical to the first column of R shifted by one element:
The algorithm requires O(n2) flops, and is thus much more efficient for large n than the MATLAB \ operator, which requires O(n3) flops. The input to the block is the vector r = [r(1) r(2) ... r(n+1)], whose elements appear in the matrix R above.
The block's top output, a = [1 a(1) a(2) ... a(n+1)], is the solution to the Levinson-Durbin equation. The elements of this vector can also be viewed as the denominator coefficients of an nth-order autoregressive (AR) process (see below). The bottom output, 
, contains a vector of reflection coefficients, which are useful for realizing lattice filters.
One application of the Levinson-Durbin formulation above is in the Yule-Walker AR problem, which concerns modeling an unknown system as an autoregressive process (or all-pole IIR filter) with assumed white Gaussian noise input. In the Yule-Walker problem, the use of the signal's autocorrelation sequence to obtain an optimal estimate leads to an equation of the type shown above, which is most efficiently solved by Levinson-Durbin recursion. In this case, the input vector r represents the autocorrelation sequence, with r(1) being the zero-lag value. The output vector a then contains the coefficients of the autoregressive process that optimally models the system. The coefficients are ordered in descending powers of z, and the autoregressive process is minimum phase:
The output vector contains the corresponding reflection coefficients, (1) to (n), for the lattice realization of this IIR filter. The Yule-Walker AR block implements this autocorrelation-based method for spectral estimation.
Another common application of the Levinson-Durbin algorithm is in linear predictive coding, which is concerned with finding the coefficients of a moving average (MA) process (or FIR filter) that predicts the next value of a signal from the current signal sample and a finite number of past samples. In this case, the input vector r represents the signal's autocorrelation sequence, with r(1) being the zero-lag value, and output vector a contains the coefficients of the predictive MA process (in descending powers of z):
Again, the output vector contains the corresponding reflection coefficients, (1) to (n), for the lattice realization of this FIR filter. The LPC block implements this autocorrelation-based prediction method for the DSP Blockset.
|
Real
|
Complex
|
Scalar
|
Vector
|
Matrix
|
Sample Time
|
Scalar Expansion
|
Input
|
|
|
|
|
|
inherited from input
| n/a
|
Output
|
|
|
|
|
|
Dialog Box
References
Golub, G. H., and C. F. Van Loan. Sect. 4.7 in Matrix Computations. 3rd ed. Baltimore, MD: Johns Hopkins University Press, 1996.
Ljung, L. System Identification: Theory for the User. Englewood Cliffs, NJ: Prentice Hall, 1987. Pgs. 278-280.
See Also
Complex Levinson-Durbin
LPC
Yule-Walker AR
[ Previous | Help Desk | Next ]