| Signal Processing Blockset™ | |
Math Functions / Matrices and Linear Algebra / Linear System Solvers
dspsolvers
The Levinson-Durbin block solves the nth-order system of linear equations
Ra = b
for the particular case where R is a Hermitian, positive-definite, Toeplitz matrix and b is identical to the first column of R shifted by one element and with the opposite sign.
The input to the block, r = [r(1) r(2) ... r(n+1)], can be a 1-D or 2-D row or column vector or a sample- or frame-based matrix. If the input is a matrix, each column is treated as an independent channel and is solved separately. Each channel of the input contains lags 0 through n of an autocorrelation sequence, which appear in the matrix R.
The block can output the polynomial coefficients, A, the reflection coefficients, K, and the prediction error power, P, in various combinations. The Output(s) parameter allows you to enable the A and K outputs by selecting one of the following settings:
A — For each channel, port A outputs A=[1 a(2) a(3) ... a(n+1)], the solution to the Levinson-Durbin equation. A has the same dimension as the input. The elements of each output channel can also be viewed as the coefficients of an nth-order autoregressive (AR) process (see below).
K — For each channel, port K outputs K=[k(1) k(2) ... k(n)], which contains n reflection coefficients, and has the same dimension as the input, less one element. A scalar input channel causes an error when you select K. Reflection coefficients are useful for realizing a lattice representation of the AR process described below.
A and K — The block outputs both representations at their respective ports. A scalar input channel causes an error when you select A and K.
A and K are matrices if the input is a matrix. Otherwise, A and K are 1-D vectors.
The prediction error power for each channel, P, is output when you select the Output prediction error power (P) check box. For each channel, P represents the power of the output of an FIR filter with taps A and input autocorrelation described by r, where A represents a prediction error filter and r is the input to the block. In this case, A is a whitening filter. P has one element per input channel.
When you select the If the value of lag 0 is zero, A=[1 zeros], K=[zeros], P=0 check box (default), an input channel whose r(1) element is zero generates a zero-valued output. When you do not select this check box, an input with r(1) = 0 generates NaNs in the output. In general, an input 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.
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. Such a process would be modeled
as the output of an all-pole IIR filter with 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 Ra = b equation
of the type shown above, which is most efficiently solved by Levinson-Durbin
recursion. In this case, the input to the block represents the autocorrelation
sequence, with r(1) being the zero-lag value. The
output at the block's A port 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 prediction error, G,
defines the gain for the unknown system, where
.
The output at the block's K port contains the corresponding reflection coefficients, [k(1) k(2) ... k(n)], 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 to the block represents the signal's autocorrelation sequence, with r(1) being the zero-lag value, and the output at the block's A port contains the coefficients of the predictive MA process (in descending powers of z).
These coefficients solve the optimization problem below.
Again, the output at the block's K port contains the corresponding reflection coefficients, [k(1) k(2) ... k(n)], for the lattice realization of this FIR filter. The Autocorrelation LPC block in the Linear Prediction library implements this autocorrelation-based prediction method.
The diagrams in this section show the data types used within the Levinson-Durbin block for fixed-point signals.
After initialization, n updates are performed. At the (j+1) update,
The diagram below displays the fixed-point data types used in this calculation:
The reflection coefficients K are then updated according to
The prediction error power P is then updated according to
The diagram below displays the fixed-point data types used in this calculation:
The polynomial coefficients A are then updated according to
The diagram below displays the fixed-point data types used in this calculation:
The algorithm requires O(n2) operations for each input channel, and is therefore much more efficient for large n than standard Gaussian elimination, which requires O(n3) operations per channel.
The Main pane of the Levinson-Durbin block dialog appears as follows.
Specify the solution representation of Ra = b to output: model coefficients (A), reflection coefficients (K), or both (A and K). For scalar and frame-based row vector inputs, this parameter must be set to A.
Select to output the prediction error at port P.
Set to output a zero-vector for inputs having r(1) = 0. Otherwise, the block outputs NaNs for these inputs.
The Fixed-point pane of the Levinson-Durbin block dialog appears as follows.
Select the rounding mode for fixed-point operations.
Select the overflow mode for fixed-point operations.
Use this parameter to designate how you would like to specify the word and fraction lengths of the polynomial coefficients (A). See Fixed-Point Data Types for illustrations depicting the use of the polynomial coefficients data type in this block.
When you select Binary point scaling, you can enter the word length and fraction length of A, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of A. This block requires power-of-two slope and a bias of zero.
Use this parameter to designate how you would like to specify the word and fraction lengths of the reflection coefficients (K). See Fixed-Point Data Types for illustrations depicting the use of the reflection coefficients data type in this block.
When you select Binary point scaling, you can enter the word length and fraction length of K, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of K. This block requires power-of-two slope and a bias of zero.
Use this parameter to designate how you would like to specify the word and fraction lengths of the prediction error power (P). See Fixed-Point Data Types for illustrations depicting the use of the prediction error power data type in this block.
When you select Same as input, these characteristics match those of the input to the block.
When you select Binary point scaling, you can enter the word length and fraction length of P, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of P. This block requires power-of-two slope and a bias of zero.
Use this parameter to designate how you would like to specify the product output word and fraction lengths. See Fixed-Point Data Types for illustrations depicting the use of the product output data type in this block.
When you select Same as input, these characteristics match those of the input to the block.
When you select Binary point scaling, you can enter the word length and fraction length of the product output, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the product output. This block requires power-of-two slope and a bias of zero.
Use this parameter to designate how you would like to specify the accumulator word and fraction lengths. See Fixed-Point Data Types for illustrations depicting the use of the accumulator data type in this block.
When you select Same as product output, these characteristics match those of the product output.
When you select Same as input, these characteristics match those of the input to the block.
When you select Binary point scaling, you can enter the word length and fraction length of the accumulator, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the accumulator. This block requires power-of-two slope and a bias of zero.
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.
Kay, Steven M., Modern Spectral Estimation: Theory and Application. Englewood Cliffs, NJ: Prentice Hall, 1988.
Double-precision floating point
Single-precision floating point
Fixed point (signed only)
8-, 16-, and 32-bit signed integers
| Cholesky Solver | Signal Processing Blockset |
| LDL Solver | Signal Processing Blockset |
| Autocorrelation LPC | Signal Processing Blockset |
| LU Solver | Signal Processing Blockset |
| QR Solver | Signal Processing Blockset |
| Yule-Walker AR Estimator | Signal Processing Blockset |
| Yule-Walker Method | Signal Processing Blockset |
| levinson | Signal Processing Toolbox |
See Linear System Solvers for related information.
| Least Squares Polynomial Fit | LMS Adaptive Filter (Obsolete) | |
| © 1984-2009- The MathWorks, Inc. - Site Help - Patents - Trademarks - Privacy Policy - Preventing Piracy - RSS |