Levinson Solver (DSP Blockset)

DSP Blockset

Search Help Desk

Levinson Solver

See Also

Solve a linear system of equations using Levinson-Durbin recursion.

Library

Linear Algebra, in Math Functions

Description

The Levinson Solver 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 and with the opposite sign:

The algorithm requires O(n²) flops, and is thus much more efficient for large n than standard Gaussian elimination, which requires O(n³) 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 Output(s) parameter allows you to select between two representations of the solution:

A - The 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 coefficients of an nth-order autoregressive (AR) process (see below).
K - The output, , contains a vector of reflection coefficients, which are useful for realizing a lattice representation of the AR process.
A and K - The block outputs both representation.

When the Special-case handling of zero-input check box is selected (default), an input vector whose r(1) element is zero generates a zero-valued output. When the check box is not selected, an input vector with r(1)=0 generates NaNs in the output. In general, an input vector with r(1)=0 is invalid because it does not construct a positive-definite matrix R; however, it is common for blocks to receive zero-valued inputs at the start of a simulation. The check box allows you to avoid propagating NaNs during this period.

Applications

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 AR process is minimum phase:

The output vector

contains the corresponding reflection coefficients,

(1) to

(n+1), for the lattice realization of this IIR filter. The Yule-Walker AR Estimator block implements this autocorrelation-based method for AR model estimation, while the Yule-Walker Method block extends the method to 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+1), for the lattice realization of this FIR filter. The LPC block in the Signal Operations library implements this autocorrelation-based prediction method.

Dialog Box

Output(s): The representation to output, solution to Ra=b (model coefficients) or reflection coefficients.
Special-case handling of zero input: If selected, output a zero-vector for inputs having r(1)=0. If not selected, output NaN.

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.