Difference equations in DSP

Discussion in 'Math' started by jag1972, Mar 14, 2017.

  1. jag1972

    Thread Starter Active Member

    Feb 25, 2010
    Hello All,
    There is a gap in my knowledge with difference equations. I can not relate a difference equation that has been determined by inspection from a signal flow diagram and difference equations that are solved using the complementary function and particular integral method. An example of a difference equation determined from a diagram may look something like this:

    y[n]= 0.5x[n-1]+x[n+2]+4y[n-4]

    This difference equation incudes a shifted and scaled versions of the input and also feedback of the output which is delayed and scaled.

    However whenever I look at examples of difference equations that are to be solved never have the input in them, they just include the output on the right and input on the left

    x[n]= y[n] +0.5y[n-1]

    This makes sense I just don't know how we get to here. I can compare it to continuous time functions for example a differential equation that describes a series RC circuit.

     V = vC + vR

     V= RC \frac{dvC}{dt} + vC

    This is then solved for vC, in the same way the difference equation has y terms on the right and input on the left, the solution is determine for y[n]. But I don't understand what happens to the x[n] terms.
    Would appreciate some help on understanding this.
    Last edited: Mar 14, 2017
  2. MrAl

    AAC Fanatic!

    Jun 17, 2014

    I am not entirely sure what you are asking here, but normally we'd want to see the output on the left such as y[n+1] or y[n]. If the expression is not in that form you can get it into that form by solving for the required output.

    In the flow diagram for a regular system we have blocks that are integrators, while in the sampled system we have blocks that are delays.

    In the equations, we might have y[n+1] on the left and then we might have x[n], x[n-1], y[n], y[n-1] on the right, which simply says that the next output depends on the current value of x, the previous value of x, the current value of y, and the previous value of y. So it would depend on two current values and two past values.

    In the expression:

    if a=0.1 and the initial output is 0 and x[1]=1 and x[2]=1 and x[3]=1 and x[4]=1 and x[5]=1 and x[6]=1 then we have:
    which i think settles to 0.90909090909....if all x[n] are equal to 1.

    If you end up with an expression with x[n+1] in it then you have to have future values of x stored somewhere in the system beforehand.
    Last edited: Mar 14, 2017
  3. jag1972

    Thread Starter Active Member

    Feb 25, 2010

    Thank you so much MrAl, I apologies for not explaining myself properly.

    My question was more basic then that, I have a feeling its because I am a beginner and have not encountered complex difference equations.

    Whenever I have solved difference equations they never include x[n] on the right hand side. From a discrete signal flow diagram the difference equation may look like this.  y[n]= a.x[n-1]+b.y[n-1]

    This would mean that the discrete system is multiplying the input by 'a' and delaying it by unit sample and the output is fed back into system, multiplied by 'b' and delayed by unit sample. I can draw the discrete system for this.
    But when I look at questions that ask me to solve difference equations, the equations never include the input on the right hand side.

     x[n]= a.y[n] + y[n-1]

    This can be solved by using y[n]=CF+PI method. This gives me an equation that models the system behavior. Why is it I have not seen equations to solve that look like the equations that have been derived from signal flow diagrams. Why do they just include the outputs.
    I hope you understand what I mean.
  4. MrAl

    AAC Fanatic!

    Jun 17, 2014

    Could it be that they just want to present problems for your solving exercises, or do you think there is a deeper reason for this?

    Also, when you say you "have not seen" equations of a certain form, what references are you talking about here...one page, two pages, one chapter, one whole book, several books, online pages?
  5. jag1972

    Thread Starter Active Member

    Feb 25, 2010
    MrAl Oh dear, seems like I have made a very basic mistake or I have only been looking at simple examples. If I compare difference equations to a differential equations in continuous time then how is it possible to have more than one input to the system.
    if the difference equation was:

     y[n]= x[n-2] + 0.8x[n] + 4y[n-1]

     x[n-2] + 0.8x[n] = y[n] -  4y[n-1]

    Are you saying this can now be solved.
  6. MrAl

    AAC Fanatic!

    Jun 17, 2014

    If we start with:
    x[n-2] + 0.8x[n] = y[n] - 4y[n-1]

    and solve for y[n] we get simply:
    y[n] = 0.8*x[n] + x[n-2] + 4y[n-1]

    which in words means the current value of y is equal to 0.8 times the current value of x plus the value of x two intervals back plus 4 times the previous value of y. Whether this system is physically realizable or not is a different question but lets look at an example.
    With x={0,1,2,3,4,5} where x[0]=2 and all initial values of y equal to zero and starting at n=0, we get first:
    then for the next interval:

    so you can see that the x[n] are not really separate inputs they are just different values of the input sequence at the different times. We state that the value of x=2 occurs at n=0 and we are starting there, so we we get the other value needed at n-2 by going back two units in the input sequence so at that point x[n-2]=0.

    Note this may not be a stable system because it looks like the values increase forever for all positive values of the sequence. There are other times when the system may not be realizable in real time such as when we need a value such as x[n+1] where we have to look into the future for the new sequence value, but if the system has memory then it may be stored somewhere already and can be retrieved.

    A simple example in real life would be an average calculation that averages the input sequence values two at a time:

    This just takes the previous value of x and adds it to the current value of x and divides by 2, which gives a slightly smoother response than just taking x alone one at a time. If we wanted to average over three values one way is to do this:

    and you can see that all we are doing here is adding the two past values to the current value and then dividing by 3 to get the average of the three values, which gives a smoother response than just averaging 2 values at a time. This ends up looking like a sort of low pass filter.

    To get from one domain to the other, we can use a Z transform and then transform that into a difference equation, which means we can take a regular filter function and convert it into a different equation like that above and that might show the relationship between the two which might be what you wanted to see.
    If you wanted to create a continuous time system from a difference equation you'd have to go the other way i guess.
  7. jag1972

    Thread Starter Active Member

    Feb 25, 2010
    Thank you so much MrAl, you have really explained this well. I have not seen it explained like this, maybe because to other people its obvious, it was not to me. But now it seems obvious (only easy when you know I guess. Thanks again.
  8. jag1972

    Thread Starter Active Member

    Feb 25, 2010
    Just to make sure I have understood I am going to attempt a solution to a difference equation. I have modified the function you wrote to make it easier for me to work out.

    2x[n-2]+x[n] = y[n]-4y[n-1]
    where  x[n] = u[n]

    The first thing to do would be to combine the sum of the current input to a delayed by 2 samples and multiplied by 2. If we assume that n starts at 2 then the input would be:


    CF:  x[n]=0

    0= y[n]-4y[n-1]

    y[n]=A\lambda ^n
    y[n-1]=A\lambda ^{n-1}
    Substitute solution into equation
    0=A\lambda ^n - 4A\lambda ^{n-1}

    0=A\lambda ^n(1 - 4\lambda ^{-1})

    0=1 - 4\lambda ^{-1}
    \lambda =4
    CF= A(4)^n

    PI Assume a solution based on the input.


    Assuming system is causal, n=1

    y[n]= CF+PI
    y[n]= A(4)^n -1

    At this stage need an initial value to determine the constant A.

    Is this right the way I combined the inputs to make one input?
  9. MrAl

    AAC Fanatic!

    Jun 17, 2014
    Hi again,

    I think it would help if you could provide a link to your solution technique so i can take a look. Unfortunately i dont have all my reference material with me anymore since when i moved i put a lot of stuff into storage.

    Alternately you could annotate each step you take a little bit better so we can understand why you did that in the first place. For example, stating that xn=un dosent really say much without some annotation :)

    I think that will help a lot here.
  10. jag1972

    Thread Starter Active Member

    Feb 25, 2010
    Sure, taking the difference equation that you used as an example

    y[n] = x[n] + 2x[n-2] + 4y[n-1]

    I have attempted to solve this difference but the results can be checked using the difference equation as it is. I am assuming  x[n]=u[n]
     u[n] =      1,\ n\geq 0 and  0,\ n<0
    y[n] = x[n] + 2x[n-2] + 4y[n-1]
    Starting at n=0, assume y[-1]=0

    y[0] = u[0] + 2u[-2] + 4y[-1], \ y[0] = 1

    y[1] = u[1] + 2u[-1] + 4y[0], \ y[1] = 5

    y[2] = u[2] + 2u[2] + 4y[1],  \ y[2] = 23

    y[3] = u[3] + 2u[3] + 4y[2],  \ y[3] = 95

    y[4] = u[4] + 2u[4] + 4y[3],  \ y[4] = 383

    y[5] = u[5] + 2u[5] + 4y[4],  \ y[5] = 1535

    y[6] = u[6] + 2u[6] + 4y[5],  \ y[6] = 6143

    y[7] = u[7] + 2u[7] + 4y[6],  \ y[7] = 24575 and so on

    The solution should match this, I have used the method for solving the difference which is similar to differential equations. That being the solution is the equal to the sum of the complementary function (CF) and the particular integral (PI) i.e.  y[n] = CF + PI

    Original difference equation
    y[n] = x[n] + 2x[n-2] + 4y[n-1]

    Separating input and outputs

     x[n] + 2x[n-2] = y[n]+4y[n-1]

    My original post was asking how to combine the inputs, I did not realise that it was us that combine it, as we know what the input is.

     x[n] = u[n]

     u[n]+2u[n-2] = x[n]

    I have found out that in order to get the right answer I have to start with n=2, if I start with n=0 I get the wrong answer.

    if n=0 , then  x[n] = ku[n] where K = 1, \ 0 \leq n \leq1 and K = 3, \  n \geq2

    I will instead start at n=2, this means  x[n] = 3u[n]

     3u[n] = y[n]-4y[n-1]

    First step is to determine the complementary function, the difference equation is made equal to 0 i.e.  x[n] = 0

     0 = y[n]-4y[n-1]

    Assume a solution for  y[n] = A\lambda ^n

    Substitute and solve for \lambda (1 - 4\lambda ^{-1} )

     0 = A\lambda - A4 \lambda ^{n-1}
     0 = A\lambda \ ( 1 - 4 \lambda ^{-1})
     0 =  1 - 4 \lambda ^{-1}
     \lambda = 4
     CF = A(4)^n

    For the particular Integral (PI) a solution is assumed based on the input
     x[n] = 3u[n]
     y[n] = Ku[n]

     3u[n] = ku[n]-4ku[n-1]

    Solve equation to determine value of k, make n =2.

     3 = k-4k
     k = -1

    y[n] = CF + PI

     y[n] = A(4)^n - 1

    Because I am starting at n=2, I have used y[1] = 5 as the initial condition which is needed to determine the constant A

     5 = A(4)^1 - 1

     5 = A4 - 1

     A = \frac{3}{2}

     y[n] = \frac {3}{2}(4)^n - 1

    starting at n =1

     y[n] = \frac {3}{2}(4)^1 - 1  \ y[1] = 5
     y[n] = \frac {3}{2}(4)^2 - 1  \ y[2] = 23
     y[n] = \frac {3}{2}(4)^3 - 1  \ y[3] = 95
     y[n] = \frac {3}{2}(4)^4 - 1  \ y[2] = 383
     y[n] = \frac {3}{2}(4)^5 - 1  \ y[3] = 1535 and so on

    Because the input is 1, when n = 0, n=1 and 3 when is greater or equal to 2. I can not start at n=0. Is this the normal case, I have therefore used initial condition of 1.

    If I use n = 0 into solution I get answer of 0.5, when answer should be 1.
  11. MrAl

    AAC Fanatic!

    Jun 17, 2014
    Hello again,

    I seems you are not trying to unify anything here, you are just looking for an analytical closed form solution.

    I think we are starting with a bad example however, because this particular equation does not converge for x positive. We should start with one that has at least some negative feedback so that we can see stability at some point even with all x>0.

    I approached it in a typical manner, but finding the z transform, then applying a reverse bilinear transformation, and the result was:

    where T is the sample time and t is real time which can be 'n' for the purpose of checking. If we work in scaled time i get a result that follows the same basic shape as the difference equation, but unfortunately this function goes to infinity at t => +inf so i dont think it is a good example to experiment with. It would be better to work with a function that has -A*y(n-1) or something like that on the right with y[n] on the left.

    I have to admit i have not been trying too hard to solve this yet, because i was waiting for you to provide some more input in the form of maybe a link that takes us to your solution method and explains it in detail. That would help explain a lot here. Your annotation helps too however.

    If we have a more well behaved function we'll find a point where it reaches steady state and then we can compare methods better. Unfortunately i cant remember how to apply your method directly or even if it was covered in one of my reference books from the past. That means SOME reference would help here.

    I'll try to go over your notes a little better tomorrow sometime but in the mean time if you can find any reference to your method that would clear this up right away. Also, it may be necessary to start at n=0 to see a comparison to the time function.

    Another shot would be to figure out if your assumed function Lambda*A^n is a good assumption. You could try a curve fit and see how well it fits, such as a least sum of squares fit. If you cant get it to fit very well using several points on the known difference curve, then it cant be a good assumption.

    BTW i get different results than you for the difference equation.
    Code (Text):
    2.   [0]  0 + 2*0 + 4*0=0
    3.   [1]  1 + 2*0 + 4*0=1
    4.   [2]  1 + 2*0 + 4*1=5
    5.   [3]  1 + 2*1 + 4*5=23
    6.   [4]  1 + 2*1 + 4*23=95
    7.   [5]  3 + 4*95=383
    8.   [6]  3 + 4*396=1535
    Of course another approach is to create a series and then try to find the generator function.
    Last edited: Mar 20, 2017
  12. jag1972

    Thread Starter Active Member

    Feb 25, 2010
    Mr Al
    I learned the solution method using this video, forward to 32 minutes

    I don't understand how your difference equations give a different result to mine will go over these today.
  13. MrAl

    AAC Fanatic!

    Jun 17, 2014

    Simple, i made a mistake myself when going over the solution :)
    So our results agree for the difference equation.
    I'm going to look at this some more too and see what i can find out.

    I also got this result:

    but that starts at n=2, and when n=2 y=5 as expected. At n=1 it does not work and that seems typical because not all of the input appears at n=0 or n=1.
    Because of that, the input when n=0 and n=1 could be different for each problem. In other words it's not causal until after all the input has been included.
    Last edited: Mar 20, 2017
  14. MrAl

    AAC Fanatic!

    Jun 17, 2014
    Hi again,

    I forgot to mention that the way i found my solution was to use a recursive strategy not the method shown in the video, which is not very well presented in my opinion. But of course that was a video of an actual classroom, not a video made for instruction for the sake of instruction.

    The recursive solution is actually much simpler. We first find the place where the difference equation starts to yield the same results for each part of the calculation. In this example it was with:

    We make that a function:

    and we apply this recursively. The first recursion is like this:

    and the second recursion:

    or in short:

    we then look at the difference between the constants in Y(Y(Y(y))) and Y(Y(y)) and see how they progressed. We then find a representation for the way they changed. For this problem is was easy because the two constants came to to be powers of 2 and power of 2 minus 1 like so:

    and with y=5 we get another solution at another n, and we can then relate that first constant to n and we get the second constant the same way but minus 1

    Since for this problem the change was with just odd powers of 2, so the exponent was 2*n-1. So we started with 2^(2*n-1) and reduce that later.
  15. jag1972

    Thread Starter Active Member

    Feb 25, 2010
    Thank you so much MrAl, you have helped so much.