Scribd
Upload
228 views38 pages

Linear Prediction in Adaptive Filtering

The document discusses linear prediction techniques for forward and backward prediction of signals. It introduces forward and backward linear prediction, describes how to calculate the predictor filter coefficients using the Wiener-Hopf equations and autocorrelation of the signal. It then presents the Levinson-Durbin algorithm, a recursive method to efficiently solve the Wiener-Hopf equations and update the prediction error filter coefficients as the predictor order increases. The properties and applications of the prediction error filters are also covered.

Uploaded by

Syed Abdullah Hasan Chishti
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
228 views38 pages

Linear Prediction in Adaptive Filtering

The document discusses linear prediction techniques for forward and backward prediction of signals. It introduces forward and backward linear prediction, describes how to calculate the predictor filter coefficients using the Wiener-Hopf equations and autocorrelation of the signal. It then presents the Levinson-Durbin algorithm, a recursive method to efficiently solve the Wiener-Hopf equations and update the prediction error filter coefficients as the predictor order increases. The properties and applications of the prediction error filters are also covered.

Uploaded by

Syed Abdullah Hasan Chishti
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 38

Adaptive Filtering

Lecture 5
Linear Prediction

Dr. Tahir Zaidi


Linear Prediction
Problem:
Forward Prediction
Observing

Predict

Backward Prediction
Observing

Predict

Adaptive Signal Processing 2


Forward Linear Prediction
Problem:
Forward Prediction
Observing the past

Predict the future

i.e. find the predictor filter taps wf,1, wf,2,...,wf,M

Adaptive Signal Processing 3


Forward Linear Prediction

Use Wiener filter theory to calculate wf,k


Desired signal

Then forward prediction error is (for predictor order M)

Let minimum mean-square prediction error be

Adaptive Signal Processing 4


One-step predictor

Prediction-error
filter

Week 4 ELE 774 - Adaptive Signal Processing 5


Forward Linear Prediction
A structure similar to Wiener filter, same approach can be used.
For the input vector

with the autocorrelation

Find the filter taps

where the cross-correlation bw. the filter input and the desired
response is

Adaptive Signal Processing 6


Forward Linear Prediction
Solving the Wiener-Hopf equations, we obtain

and the minimum forward-prediction error power becomes

In summary,

Adaptive Signal Processing 7


Relation Between Linear
Prediction and AR Modelling

Note that the Wiener-Hopf equations for a linear


predictor is mathematically identical with the Yule-Walker
equations for the model of an AR process.

If AR model order M is known, model parameters can be


found by using a forward linear predictor of order M.

If the process is not AR, predictor provides an (AR)


model approximation of order M of the process.

Adaptive Signal Processing 8


Forward Prediction-Error Filter
We wrote that

Let

Then

Adaptive Signal Processing 9


Augmented Wiener-Hopf Eqn.s
for Forward Prediction
Let us combine the forward prediction filter and forward prediction-
error power equations in a single matrix expression, i.e.
and

Define the forward prediction-error filter vector

Augmented Wiener-Hopf Eqn.s


of a forward prediction-error filter
Then
of order M.

or

Adaptive Signal Processing 10


Example Forward Predictor
(order M=1)
For a forward predictor of order M=1

Then

where

But a1,0=1, then

Adaptive Signal Processing 11


Backward Linear Prediction
Problem:
Forward Prediction
Observing the future

Predict the past

i.e. find the predictor filter taps wb,1, wb,2,...,wb,M

Adaptive Signal Processing 12


Backward Linear Prediction
Desired signal

Then backward prediction error is (for predictor order M)

Let minimum-mean square prediction error be

Adaptive Signal Processing 13


Backward Linear Prediction
Problem:
For the input vector

with the autocorrelation

Find the filter taps

where the cross-correlation bw. the filter input and the desired
response is

Adaptive Signal Processing 14


Backward Linear Prediction
Solving the Wiener-Hopf equations, we obtain

and the minimum forward-prediction error power becomes

In summary,

Adaptive Signal Processing 15


Relations bw. Forward and Backward
Predictors
Compare the Wiener-Hopf eqn.s for both cases (R and r are same)
?

order
reversal

complex
conjugate

Adaptive Signal Processing 16


Backward Prediction-Error Filter
We wrote that

Let

Then

but we found that

Then

Adaptive Signal Processing 17


Backward Prediction-Error Filter

forward prediction-error filter

backward prediction-error filter

For stationary inputs, we may change a forward prediction-error filter


into the corresponding backward prediction-error filter by reversing
the order of the sequence and taking the complex conjugation of
them.
Adaptive Signal Processing 18
Augmented Wiener-Hopf Eqn.s for Backward
Prediction
Let us combine the backward prediction filter and backward prediction-error
power equations in a single matrix expression, i.e.
and

With the definition

Augmented Wiener-Hopf Eqn.s


Then
of a backward prediction-error filter
of order M.
or

Adaptive Signal Processing 19


Levinson-Durbin Algorithm
Solve the following Wiener-Hopf eqn.s to find the
predictor coef.s

One-shot solution can have high computation


complexity.
Instead, use an (order)-recursive algorithm
Levinson-Durbin Algorithm.
Start with a first-order (m=1) predictor and at each iteration
increase the order of the predictor by one up to (m=M).
Huge savings in computational complexity and storage.

Adaptive Signal Processing 20


Levinson-Durbin Algorithm
Let the forward prediction error filter of order m be represented by
the (m+1)x1

and its order reversed and complex conjugated version (backward


prediction error filter) be

The forward-prediction error filter can be order-updated by

The backward-prediction error filter can be order-updated by

where the constant m is called the reflection coefficient.

Adaptive Signal Processing 21


Levinson-Durbin Recursion
How to calculate am and m?
Start with the relation bw. correlation matrix Rm+1 and the forward-
error prediction filter am.
indicates order

indicates dim. of matrix/vector


We have seen how to partition the correlation matrix

Adaptive Signal Processing 22


Levinson-Durbin Recursion
Multiply the order-update eqn. by Rm+1 from the left

1 2
Term 1:

but we know that (augmented Wiener-Hopf eqn.s)

Then

Adaptive Signal Processing 23


Levinson-Durbin Recursion
Term 2:

but we know that (augmented Wiener-Hopf eqn.s)

Then

Adaptive Signal Processing 24


Levinson-Durbin Recursion

Then we have
from the first line

As iterations increase
from the last line Pm decreases

Adaptive Signal Processing 25


Levinson-Durbin Recursion Interpretations

final value of the prediction error power

m: reflection coef.s due to the analogy with the reflection coef.s


corresponding to the boundary bw. two sections in transmission lines

The parameter m represents the crosscorrelation bw. the forward


prediction error and the delayed backward prediction error

Since f0(n)= b0(n)= u(n)

Adaptive Signal Processing 26


Application of Levinson-Durbin Algorithm
Find the forward prediction error filter coef.s am,k, given the
autocorrelation sequence {r(0), r(1), r(2)}
m=0

m=1

m=M=2

Adaptive Signal Processing 27


Properties of the prediction error filters
Property 1: There is a one-to-one correspondence bw. the two sets
of quantities {P0, 1, 2, ... ,M} and {r(0), r(1), ..., r(M)}.
If one set is known the other can directly be computed by:

Adaptive Signal Processing 28


Properties of the prediction error filters

Property 2a: Transfer function of a forward prediction error filter

Utilizing Levinson-Durbin recursion

but we also have

Then

Adaptive Signal Processing 29


Properties of the prediction error filters

Property 2b: Transfer function of a backward prediction error filter

Utilizing Levinson-Durbin recursion

Given the reflection coef.s m and the transfer functions of the


forward and backward prediction-error filters of order m-1, we can
uniquely calculate the corresponding transfer functions for the
forward and backward prediction error filters of order m.

Adaptive Signal Processing 30


Properties of the prediction error filters

Property 3: Both the forward and backward prediction error filters have the
same magnitude response

Property 4: Forward prediction-error filter is minimum-phase.


causal and has stable inverse.
Property 5: Backward prediction-error filter is maximum-phase.
non-causal and has unstable inverse.

Adaptive Signal Processing 31


Properties of the prediction error filters
u(n)

Property 6: Forward
prediction-error filter is a analysis
whitening filter. filter
We have seen that a
forward prediction-error
filter can estimate an AR
model (analysis filter).

synthesis
filter

Adaptive Signal Processing 32


Properties of the prediction error filters

Property 7: Backward prediction errors are orthogonal to each


other.

( are white)
Proof: Comes from principle of orthogonality, i.e.:

Adaptive Signal Processing 33


Lattice Predictors
A very efficient structure to implement the forward/backward predictors.
Rewrite the prediction error filter coef.s

The input signal to the predictors {u(n), u(n-1),...,u(n-M)} can be stacked


into a vector

Then the output of the predictors are

(forward) (backward)
Adaptive Signal Processing 34
Lattice Predictors

Forward prediction-error filter

First term

Second term

Combine both terms

Adaptive Signal Processing 35


Lattice Predictors
Similarly, Backward prediction-error filter

First term

Second term

Combine both terms

Adaptive Signal Processing 36


Lattice Predictors
Forward and backward prediction-error filters

in matrix form

and

Last two equations define the m-th


stage of the lattice predictor

Adaptive Signal Processing 37


Lattice Predictors
For m=0 we have , hence for M stages

Adaptive Signal Processing 38

You might also like