Engee documentation

Levinson-Durbin

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

levinson durbin

Description

Block Levinson-Durbin solves a system of linear equations of n-th order

in the cases when:

  • - Hermite positive-definite matrix Heatsheet.

  • - coincides with the first column of R shifted by one element and having opposite sign:

The input of the block can be a vector or a matrix. If the input is a matrix, the block treats each column as an independent signal and solves it separately. Each input signal contains lags of the autocorrelation sequence from 0 to n, which appear in the matrix R.

The block can output polynomial coefficients A, reflection coefficients K and prediction error power P in various combinations. The Output(s) parameters allows the A and K outputs to be enabled by selecting one of the following settings:

  • A - for each signal, the A port outputs - the solution to the Levinson-Durbin equation. A has the same dimensionality as the input. The elements of each output signal can also be viewed as coefficients of an nth order autoregressive (AR) process.

  • K - For each signal, the K port outputs , which contains n reflection coefficients and has the same dimensionality as the input, minus one element. A scalar input signal causes an error when K is selected. The reflection coefficients can be used to implement the lattice representation of the AR process described later on this page.

  • A and K - the block outputs both choices to the corresponding ports. A scalar input signal causes an error when A and K is selected.

Select the Output prediction error power (P) checkbox to output the prediction error power for each signal, P. For each signal, P represents the output power of a FIR filter with taps A and input autocorrelation described by r, where A represents the prediction error filter and r is the input of the block. In this case, A is the separating filter. P has one element for each input signal.

When the checkbox If the value of lag 0 is zero, A=[1 zeros], K=[zeros], P=0 is checked (by default), the input signal whose element r(1) is zero generates an output with zero value. When unchecked, the input signal generates NaN at the output. In general, the input is invalid because it does not construct the positive-definite matrix R. However, blocks often receive inputs with a zero value at the beginning of the simulation. The checkbox avoids the propagation of NaN during this period.

Application

One application of the Levinson-Durbin formula implemented in this block is the Yule-Walker AR problem, which involves modelling an unknown system as an autoregressive process. Such a process can be modelled as the output of an all-pole IIR filter with white Gaussian noise at the input. In the Yule-Walker problem, usage of the autocorrelation sequence of the signal to obtain the optimal estimate leads to the equation of the above form, which is most efficiently solved using Levinson-Durbin recursion. In this case, the input of the block is the autocorrelation sequence and r(1) is the zero lag value. The output signal at port A of the block contains the coefficients of the autoregressive process that optimally models the system. The coefficients are ordered by decreasing power of z, and the AR process itself has a minimum phase. The prediction error determines the gain for the unknown system:

The output signal at the K-port of the block contains the corresponding reflection coefficients for the lattice implementation of this IIR filter.

Another common application of the Levinson-Durbin algorithm is linear predictive coding, the goal of which is to find the coefficients of a moving average (MA) process (or FIR filter) that predicts the next signal value from the current signal sample and a finite number of past samples. In this case, the input of the block is an autocorrelation sequence of the signal, where r(1) is the value of zero lag, and the output on the A port of the block contains the coefficients of the predictive MA process (in decreasing degree z).

These coefficients solve the following optimisation problem:

The output to port K of the block contains the corresponding reflection coefficients, , for the lattice implementation of this FIR filter.

Algorithm

The algorithm requires operations for each input signal. Therefore, this implementation is much more efficient at large n than standard Gaussian elimination, which requires operations for each signal.

Ports

Input

Port_1 - input signal
scalar | vector | matrix

Input signal.

Data types: Float16, Float32, Float64, Int8, Int16, Int32, Int64, UInt8, UInt16, UInt32, UInt64, Bool

Output

K - solution of the linear system of equations
scalar | vector | matrix

Output signal; solution of a linear system of equations. The output signal has the same size as the input signal.

Data types: Float16, Float32, Float64, Int8, Int16, Int32, Int64, UInt8, UInt16, UInt32, UInt64, Bool

Parameters

Output(s) - type of output data
K (by default) | A | A and K

Specify which representation of the solution should be output: model coefficients (A), reflection coefficients (K), or both (A and K). If the input is a scalar or a vector of strings, this parameters should be set to A.

Output prediction error power (P) - output prediction error power (P)
Off (by default) | On

Select to output prediction error power to the P port.

If the value of lag 0 is zero, A=[1 zeros], K=[zeros], P=0 - reaction to the zero first element of the input
disabled (by default) | enabled.

If the checkbox is checked and the first element of input r(1) is zero, the block outputs the following vectors, respectively:

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

  • K = [zeros(1,n)]

  • P = 0

If this checkbox is unchecked, for each signal whose element r(1) is equal to zero, the block outputs the vector NaN.