# Levinson-Durbin

Solve linear system of equations using Levinson-Durbin recursion

Libraries:
DSP System Toolbox / Estimation / Linear Prediction / Linear System Solvers
DSP System Toolbox / Math Functions / Matrices and Linear Algebra / Linear System Solvers

## Description

The Levinson-Durbin block solves the nth-order system of linear equations

Ra = b

in the cases where:

• R is a Hermitian, positive-definite, Toeplitz matrix.

• b is identical to the first column of R shifted by one element and with the opposite sign.

## Ports

### Input

expand all

Specify the input to the block, ```r = ``````[r(1) r(2) ... r(n+1)]``` as a vector or a matrix. If the input is a matrix, the block treats each column as an independent channel and solves it separately. Each channel of the input contains lags 0 through n of an autocorrelation sequence, which appear in the matrix R.

If the input is fixed point, it must be a signed integer or a signed fixed point value with a power-of-two slope and zero bias.

Data Types: `single` | `double` | `int8` | `int16` | `int32` | `fixed point`
Complex Number Support: Yes

### Output

expand all

Model coefficients A, returned as a vector or a matrix. A has the same dimension as the input.

For each channel, port A outputs `A = ````[1 a(2) a(3) ... a(n+1)]```, the solution to the Levinson-Durbin equation. You can also view the elements of each output channel as the coefficients of an nth-order autoregressive (AR) process.

#### Dependencies

To enable this port, set Output(s) to `A and K` or `A`.

Data Types: `single` | `double` | `int8` | `int16` | `int32` | `fixed point`
Complex Number Support: Yes

Reflection coefficients K, returned as a vector or a matrix. K has the same dimension as the input, less one element.

For each channel, port K outputs ```K = ``````[k(1) k(2) ... k(n)]```, which contains n reflection coefficients.

A scalar input channel causes an error when you select `K`. You can use reflection coefficients to realize a lattice representation of the AR process. For more details, see Applications.

#### Dependencies

To enable this port, set Output(s) to `A and K` or `K`.

Data Types: `single` | `double` | `int8` | `int16` | `int32` | `fixed point`
Complex Number Support: Yes

Output prediction error power P, returned as vector of length equal to the number of input channels. Each element in the vector is the prediction error power for each channel.

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.

#### Dependencies

To enable this port, select the Output prediction error power (P) check box.

Data Types: `single` | `double` | `int8` | `int16` | `int32` | `fixed point`

## Parameters

expand all

### Main Tab

Specify the solution representation of Ra = b to output:

• Polynomial coefficients (`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. You can also view the elements of each output channel as the coefficients of an nth-order autoregressive (AR) process.

• Reflection coefficients (`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`. You can use reflection coefficients to realize a lattice representation of the AR process described later in this page.

• Both model coefficients and reflection coefficients (`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```.

When the input is a scalar or row vector, you must set this parameter to `A`.

Select this parameter to output the prediction error power for each channel at port P.

When you select this check box and the first element of the input, `r(1)`, is zero, the block outputs the following vectors, as appropriate:

• `A = [1 zeros(1,n)]`

• `K = [zeros(1,n)]`

• `P = 0`

When you clear this check box, the block outputs a vector of `NaN`s for each channel whose `r`(1) element is zero. In general, an input with r(1) = `0` is invalid because it does not construct a positive-definite matrix R. Often, however, blocks receive zero-valued inputs at the start of a simulation. The check box allows you to avoid propagating `NaN`s during this period.

### Data Types Tab

Note

Floating-point inheritance takes precedence over the data type settings defined on this pane. When inputs are floating point, the block ignores these settings, and all internal data types are floating point.

Specify the rounding mode for fixed-point operations as one of the following:

• `Floor`

• `Ceiling`

• `Convergent`

• `Nearest`

• `Round`

• `Simplest`

• `Zero`

For more details, see rounding mode.

When you select this parameter, the block saturates the result of its fixed-point operation. When you clear this parameter, the block wraps the result of its fixed-point operation. For details on `saturate` and `wrap`, see overflow mode for fixed-point operations.

Specify the product output data type as ```Inherit: Same as input``` or a numeric type. See Fixed-Point Data Types and Multiplication Data Types for illustrations depicting the use of the product output data type in this block. You can set it to:

• A rule that inherits a data type, for example, `Inherit: Same as input`

• An expression that evaluates to a valid data type, for example, `fixdt(1,16,0)`

Click the button to display the Data Type Assistant, which helps you set the Product output parameter.

Specify the accumulator data type as ```Inherit: Same as input```, ```Inherit: Same as product output```, or a numeric type. See Fixed-Point Data Types for illustrations depicting the use of the accumulator data type in this block. You can set it to:

• A rule that inherits a data type, for example, `Inherit: Same as input`

• A rule that inherits a data type, for example, ```Inherit: Same as product output```

• An expression that evaluates to a valid data type, for example, `fixdt(1,16,0)`

Click the button to display the Data Type Assistant, which helps you set the Accumulator parameter.

Specify the polynomial coefficients (A) data type as a numeric type. See Fixed-Point Data Types for illustrations depicting the use of the A data type in this block. You can set it to an expression that evaluates to a valid data type, for example, `fixdt(1,16,10)`.

Click the button to display the Data Type Assistant, which helps you set the A parameter.

Specify the reflection coefficients (K) data type as a numeric type. See Fixed-Point Data Types for illustrations depicting the use of the K data type in this block. You can set it to an expression that evaluates to a valid data type, for example, `fixdt(1,16,10)`.

Click the button to display the Data Type Assistant, which helps you set the K parameter.

Specify the prediction error power (P) data type as `Inherit: Same as input` or a numeric type. See Fixed-Point Data Types for illustrations depicting the use of the P data type in this block. You can set it to:

• A rule that inherits a data type, for example, `Inherit: Same as input`

• An expression that evaluates to a valid data type, for example, `fixdt(1,16,0)`

Click the button to display the Data Type Assistant, which helps you set the P parameter.

Specify the minimum values that the polynomial coefficients, reflection coefficients, or prediction error power should have. The default value is `[]` (unspecified). Simulink® uses this value to perform:

Specify the maximum values that the polynomial coefficients, reflection coefficients, or prediction error power should have. The default value is `[]` (unspecified). Simulink uses this value to perform:

Select this parameter to prevent the fixed-point tools from overriding the data types you specify in the block dialog box.

## Block Characteristics

 Data Types `double` | `fixed point` | `integer` | `single` Direct Feedthrough `no` Multidimensional Signals `no` Variable-Size Signals `no` Zero-Crossing Detection `no`

expand all

## Algorithms

The algorithm requires O(n2) operations for each input channel. This implementation is therefore much more efficient for large n than standard Gaussian elimination, which requires O(n3) operations per channel.

## References

[1] Golub, G. H. and C. F. Van Loan. Sect. 4.7 in Matrix Computations. 3rd ed. Baltimore, MD: Johns Hopkins University Press, 1996.

[2] Ljung, L. System Identification: Theory for the User. Englewood Cliffs, NJ: Prentice Hall, 1987. Pgs. 278–280.

[3] Kay, Steven M. Modern Spectral Estimation: Theory and Application. Englewood Cliffs, NJ: Prentice Hall, 1988.

## Version History

Introduced before R2006a