Part I: Levinson Durbin's Recursion Algorithm

This is an algorithm to solve any problems of the type

R_x a_p = b

Where R_x is a Toeplitz matrix

These types of equation arise in finding a Least squares approximation to a signal using

Autocorrelation method or in stochastically modeling the signal as an AR process (Yule Walker

Equations). The matrix becomes Toeplitz in all pole modeling of the signal

In part III we model BlackboxA using AR model

In part IV we model BlackboxB using Autocorrelation method

Levinson Durbin’s Algorithm:

1. Initialization : e(0) =r(0) , a(0,0) =1

2. For j=0, 1, … (p-1)

a) g ( j ) = r(j+1) + å_i^j₌₁ a(j,I) *r(j-i+1)

b) G(j+1) = -g ( j ) /e( j )

c) For i=1, 2,… j

a(j+1,I) = a(j+1,I) + G(j+1) * a^*(j,j-i+1)

d) a(j+1,j+1) =G(j+1)

e) e(j+1) = e( j ) * [ 1-abs( G(j+1) )² ]

3. b(0) = sqrt( e(p) )

Part II : Verifying the Levinson Durbin Recursion

• To generate x(n): Filter a White noise signal with Q(z) by first calculating the coefficients of the denominator polynomial and then filtering white noise through it

• The signal x(n) is modeled as an AR process of order p. So take the autocorrelation of

• x(n)(assumed ergodic) and apply Levinson-Durbin recursion on it

• On applying Levinson Durbin recursion we get the All-pole parameters of Q(z) as follows:

a(0) = 1

a(1) =-0.25

a(2) = -0.125

b(0) = 2

• The error obtained is equal to the variance of the White noise and the G(2+1)th coefficient comes out to be zero. Thus the error remains constant after that

Part III : Modeling a signal as an Auto Regressive Process

Assumptions

1. WSS :
• The process is zero mean
• If we take the expected value of x(n).x(n-k) over N different realizations of the process

we get similar values scaled by a different constant every time

2. Ergodic:

· For every N step( N=10000) realization the Time autocorrelations come out to be the same but for a scaling factor Thus we can say the Time autocorrelations converge to the same limiting value(the actual autocorrelation) as N tends to infinity

Modeling of x[n]

· Since x(n)=BlackBoxA is ergodic, take one realization of it and calculate the autocorrelation.

· We want to model it assuming it is generated by passing White noise through an All-pole filter

· Use that Autocorrelation in the Levinson Durbin's recursion to generate the parameters of the all-pole filter.

· Keep increasing p till error becomes constant.

· Set b as the square root of the error.

Observations:

• The autocorrelation of x(n) is plotted in graph 3.1.
• The error becomes almost constant after p=5 (plotted in graph 3.2)
• The coefficients are as follows

a( 0 ) = 1

a( 1 ) = -0.9173 + j 0.0381

a( 2 ) = 0.0213 + j 0.2315

a( 3) = 0.0842 + j 0.0918

a( 4 ) = 0.0377 - j 0.0727

a(5) = 0.0078 - j 0.0985

Part IVa: Modeling of x[n] as the impulse response of a causal and stable All-pole filter using Autocorrelation Method

Observations:

• Obtain the deterministic Autocorrelation of x(n) and pass it into the Levinson Durbin recursion algorithm
• Keep increasing p , the error reduces but does not stabilize
• Increasing N actually increases the error
• The reduction in error with p for different N is plotted in Graph 4.1

Conclusion:

This proves that the signal cannot be modeled as a All-pole filter.

Part IV b : Non-Linear Modeling of x[n]

Assumptions:

• X(n) is Stationary and Ergodic

Derivation:

Let xhat(n) = b(0) n=0

= f( xhat(n-1) ) otherwise

Let f(x) be a polynomial function of x(n-1)

We write xhat( n ) = a0 + a1 x(n-1) + a2 x(n-1) ^2 + ...

Error Eps = å _n [ x(n)-xhat(n) ] ²

To minimize the error differentiate w.r.t. to a0, a1, a2,.. and set to zero

Since E[x(n)³] and onwards is much lower (negligible) compared to E[x(n)²] we assume coefficients

upto a0, a1, a2 only

Differentiating w r t a0, a1, a2 we get

E[x(n)] - a0 - a1*E[x(n-1)] - a2*E[x(n-1)²] = 0

E[x(n)*x(n-1)] - a0*E[x(n-1)] - a1*E[x(n-1)²] - a2*E[x(n-1)³] = 0

E[x(n)*x(n-1)²] - a0*E[x(n-1)²] - a1*E[x(n-1)³] - a2*E[x(n-1)⁴] = 0

From calculating these expectations assuming a Stationary and ergodic signal

we get

E[x(n-1)²] = 0.5

E[x(n)*x(n-1)²] = -0.25

E[x(n)] = E[x(n-1)] = 0

E[ x(n)*x(n-1) ] = 0 (negligible)

E[x(n-1)³] = 0

Solving we get,

a0 = 0.5

a2 = -1

a1 = 0

i.e.

x(n) = k (0.5 - x(n-1)*x(n-1)

If we try to match the energy content of the 2 signals we get k = 2

Therefore x(n) = 1-2*[x(n-1)²]

This model is exact - We get zero error. The first sample is random

Observation:

• x(n) versus x(n-1) is plotted in Graph 4.2

Conclusion:

• Thus the signal can be modeled exactly as

xhat(0)=x(0)

xhat(n) = 1-2*[x(n-1)²]

• The entire signal can be represented by 3 parameters – x(0) , 1, -2

• The model is unstable and thus cannot be used directly in the presence of noise

Part IV c : Modeling x(n) in the presence on Noise

Given

y[n] = x[n] + w[n]

Where

w[n]: White Gaussian Noise with variance= 10^-4

Observations for utilizing same Encode as in Part IV a :

• Running the Encoder designed in part b gives very high Error values, this is because since the noise gets squared , so it is always positive and the error keeps on increasing (plotted in Graph 4.3)

• The signal x(n) is always less than 1 so x(n-1)² is also less than 1. But due to noise if it goes above 1, the parabola goes on increasing from then onwards

Conclusions

• The model is unstable. One high value of noise can send y(n) greater than 1 and then the model fails

• The performance of a Non-linear estimator degrades very badly in the presence of noise.
• The maximum mismatch between y(n) and yhat(n) is at the peaks as shown in Graph 4.4

Methods for reducing the Mean Squared Error

1. METHOD I: One method that was tried was

yhat(n) = 1 – yp²

Where

yp = Mean( yhat(n-1),.. yhat(n-k) )

• This reduced the Mean squared error slightly but does not really help because the noise is squared and so does not get cancelled

2. METHOD II: This method utilises
• Keep estimating (need not transmit these symbols) till the error till the value of y(n) is less than 1.
• If value of y(n) is greater than 1 transmit the symbols as it is without prediction based on previous value.
• When the value of y(n) goes below 1 start prediction again.
• Thus what is required to be transmitted is

1. y(0)
2. (Number of symbols not transmitted , next Non-predicted symbol )

Observation:

This only prevented the signal from going out of bound but the reduction in error was not too high

3. METHOD III :WORKS VERY WELL

· Since x(n) is basically a parabola, so we want to transmit only those values of x(n) whin define the peak of the parabola.

· So transmit actual value of y(n) whenever there is a sign change i.e

Sign ( y(n)-y(n-1) ) is not equal to Sign ( y(n+1)-y(n) )

· Otherwise do not transmit anything

· Whenever y(n) is transmitted the symbol is preceded by the number of previous samples not transmitted

Observation

· A compression factor of only about 2 is obtained

· Mean Square Error reduces to 0.0097 which is very low.(Plotted in Graph 4.5)

· The signal yhat(n) now follows y(n) almost exactly because the peaks have been forcibly set (Graph 4.6)

Improvements

The algorithm can be improved further by transmitting only the error when it exceeds certain threshold

The Nth peak can also be Differentially encoded with respect to the (N-2)th peak

Levinson Durbin Recursion and its Aplications

Submitted by

Namrata Vaswani