# LTI Difference Equation from Impulse response

1. Apr 18, 2012

### paul_harris77

I've been told that to calculate the difference equation of an LTI system, you simply take the sample values of the impulse response as the coefficients of the x[n-k] terms in the difference equation. i.e. if h[n] = {1, 0.5, 0.25, 0.125} for n>=0, then y[n] = x[n] +0.5x[n-1]+0.25x[n-2]+0.125x[n-3]. This makes sense to me since x[n] is an impulse ($\delta$[n]) for h[n].

However, is it true that this difference equation is only valid for x[n] = $\delta$[n] and no other types of input? It would certainly seem so, as if I put in x[n] = {1,1,1,1,0,...0}, take the z-transforms of x[n] and h[n], multiply them, and take then take inverse z-transform, I get:

y[n] = {1, 3/2, 7/4, 15/8, 15/8, 7/8, 3/8, 1/8, 0, 0 ... , 0} which does not correspond to the difference equation above.

Also, surely if this were true for all inputs, you could not have a recursive system since the difference equation would only contain x[n] terms and no y[n-k] terms.

Have I answered my own question?

Any answers would be greatly appreciated!

Many thanks

Paul

2. Apr 18, 2012

### rbj

no, since the system is Linear and Time-Invariant, you can represent x[n] as

$$x[n] = \sum_{i=-\infty}^{+\infty} x \delta[n-i]$$

then the output of the LTI system is

\begin{align} y[n] & = \mathbf{LTI} \{ x[n] \} \\ & = \mathbf{LTI} \left\{ \sum_{i=-\infty}^{+\infty} x \delta[n-i] \right\} \\ & = \sum_{i=-\infty}^{+\infty} x \mathbf{LTI} \{ \delta[n-i] \} \\ & = \sum_{i=-\infty}^{+\infty} x h[n-i] \\ & = \sum_{i=-\infty}^{+\infty} h x[n-i] \\ \end{align}

so it works for any x[n], as long as your system is LTI.

3. Apr 18, 2012

### rbj

now, this is a conflation. you want to get a recursive equations for y[n], but you have stated no recursive equations for h[n]. now the example h[n] that you have shown seems to have a recursive relationship to itself. can you spot it?

perhaps you have, but incorrectly.

4. Apr 18, 2012

### rbj

now that i reread your original post, it occurred to me that you may be referring to a concept call "Truncated IIR" filters, which are certain kinds of FIR filters that are efficiently implemented with IIR filters and a delay line.

is this it?

if so, i would recommend you look up something written by Julius Smith (google all of the words). i can also send you a simple pdf paper that generalizes TIIR filters for truncated first and second order IIRs.

5. Apr 18, 2012

### paul_harris77

Hi rbj

Thanks for your replies. I don't have much experience in DSP (as you can probably tell).

1) Perhaps I should give more context. I was just trying to relate two concepts from my lecture notes and they may or may not be indirectly linked to truncated IIR filters.

I wanted to apply the idea I stated earlier:

to an example h[n] in my notes of an LTI system with an h[n] of:

h[n] = $(\frac{1}{2})^n$ = {1, 1/2, 1/4, ....} for n>=0

Using the idea above I get the difference equation: y[n] = x[n] +0.5x[n-1]+0.25x[n-2]+0.125x[n-3].

Now my notes then show how to get the output y[n] for an input x[n] = {1,1,1,1,0,0...0} using the z-transform. The result is y[n] = {1, 3/2, 7/4, 15/8, 15/8, 7/8, 3/8, 1/8, 0, 0 ... , 0}.

Instead, if I use the difference equation above to obtain the output I get:

y[n] = {1, 1/2, 1/4, 1/8, 0, 0 .. 0} which is different to the y[n] obtained from the z-transform method.

You say:
but this clearly doesn't work in this case. Can you explain why? Am I doing something wrong? The example stated it was an LTI system.

2) Also, I don't understand your $\textbf{LTI{}}$ notation. Does y[n] = $\textbf{LTI}${x[n]} simply mean "an LTI system operating on x[n]"?

3) In reply to your second post, you say I have stated no recursive equations for h[n]. This is true - I merly posted the sample values at time n. So does this mean, if you have only the samples and not the difference equation, you can not obtain a recursive difference equation, only a non-recursive difference equation?

Many thanks

Paul

6. Apr 18, 2012

### rbj

BTW, Paul, a good place to take DSP questions, even noob questions is the USENET newsgroup comp.dsp.

i am trying to understand if your impulse response is h[n] = {1, 0.5, 0.25, 0.125},

$$h[n] = \begin{cases} 2^{-n} & 0 \le n < 4 \\ 0 & \text{otherwise} \end{cases}$$

or an impulse response that is

$$h[n] = \begin{cases} 2^{-n} & 0 \le n \\ 0 & n < 0 \end{cases}$$

the first is an FIR and the latter is an IIR. the IIR must be implemented recursively. there must be some form of feedback to get an IIR.

and, yes LTI{} means the LTI system (with implied impulse response of h[n]) operating on the input inside the {} .

7. Apr 18, 2012

### paul_harris77

Hi rbj

The first h[n] is the correct one i.e. (FIR). Sorry if this caused any confusion.

Thanks!

Paul

8. Apr 18, 2012

### rbj

there is a contradiction going on here.

so now you're saying it's not

h[n] = $(\frac{1}{2})^n$ = {1, 1/2, 1/4, ....} for n>=0

??

are you sure?

because if you're a noob, i doubt that you're trying to learn about Truncated IIR. not yet.

L8r,

r b-j

9. Apr 18, 2012

### paul_harris77

Sorry for the confusion, I should have written it in a clearer form with all the conditions. The h[n] = {1, 1/2, 1/4, ....} for n>=0 was wrong. There should not have been a "...." at the end. The example, even in the hard copy of the notes, specifically states:

h[n] = $(\frac{1}{2})^n$ for 0$\leq$n$\leq$3 and 0 elsewhere.

i.e. h[n] = {1, 1/2, 1/4, 1/8, 0, 0...,0}

and

x[n] = 1 for 0$\leq$n$\leq$4 and 0 elsewhere.

i.e. x[n] = {1, 1, 1, 1, 1, 0, 0 ..., 0}

From h[n], I obtained the difference equation of:

y[n] = x[n] +0.5x[n-1]+0.25x[n-2]+0.125x[n-3]

and then substituted in for x[n] giving:

y[n] = {1, 1/2, 1/4, 1/8, 0, 0 ... , 0} i.e. the same as h[n]

Which, for some reason is different to the y[n] obtained using the z-transform:

y[n] = {1, 3/2, 7/4, 15/8, 15/8, 7/8, 3/8, 1/8, 0, 0 ... , 0}.

This was just a simple example of using the z-transform to obtain the output for a given input. We haven't been into any detail about Truncated IIR, I just assumed this was FIR. I was just looking through my notes for examples to apply the original concept of the impulse response coefficients being the difference equation coefficients and it appears (unless I have done something wrong) that it doesn't work for this example as the z-transform answer does not agree with the difference equation answer. Am I making a n00b mistake?

Thanks :)

Paul

10. Apr 18, 2012

### rbj

okay, all of this makes sense and is consistent.

so here's the bad news, you're talking about, what we generalize as "Truncated IIR" filters, but fortunately your TIIR isn't too complicated. you don't need a "General Theory of TIIR Filters".

but here's the idea:

it is FIR. TIIRs are all FIRs. but they are a specific case of FIR, with specific restrictions, that can be (sometimes very efficiently) implemented as a couple of nearly identical IIRs (which are recursive) separated by a delay line (or a single IIR acting on the difference of the input and a delayed and scaled copy of that input).

your TIIR is the second-most simple case. here is the simplest:

The moving-average or moving-sum filter.

let N be the number of samples you're moving average is over. there are two ways to do it:

first, the simple non-recursive FIR:

$$h[n] = \begin{cases} \frac{1}{N} & 0 \le n < N \\ 0 & \text{otherwise} \end{cases}$$

\begin{align} y[n] & = \sum_{i=-\infty}^{+\infty} x h[n-i] \\ & = \sum_{i=n-N+1}^{n} x\frac{1}{N} \\ & = \frac{1}{N} \sum_{i=0}^{N-1} x[n-i] \\ \end{align}

pretty simple, right. but someone noticed that the summer could be implemented recursively and the sample x[n-N] could be subtracted out each sample. so here is the TIIR version:

let

$$h_{IIR}[n] = \begin{cases} 1 & 0 \le n \\ 0 & \text{otherwise} \end{cases}$$

$$h[n] = \frac{1}{N} ( h_{IIR}[n] - h_{IIR}[n-N] )$$

now, can you figure out how to implement an LTI system that does hIIR[n] and then how to use that to implement h[n]? (think about applying the Z transform to that. then the recursive nature is clear.)

now that we have crossed our i's and dotted our t's, we are communicating.

try to figure out what i just plopped onto you and if you can't, come back for more punishment.

Last edited: Apr 18, 2012
11. Apr 19, 2012

### paul_harris77

Thanks for the reply. I think I understand the jist of what your saying.

I'm not sure but would $h[n]_{iir}$ be:

$h[n]_{iir}= x[n] + h[n-1]$

In which case would:

$h[n]= x[n] + h[n-1]-x[n-N] - h[n-N]$

be correct?

Last edited: Apr 19, 2012
12. Apr 19, 2012

### rbj

close, but any "h" is an impulse response. it's

$$y[n]_{iir} = x[n]_{iir} + y[n-1]_{iir}$$

and

$$x[n]_{iir} = \frac{1}{N} (x[n] - x[n-N])$$

and $y[n] = y[n]_{iir}$ .

hiir is already defined (with no reference to x[n]), but it is true that the IIR impulse response can be expressed recursively as

$$h[n]_{iir}= \delta[n] + h[n-1]_{iir}$$.

now, put together the block diagram of how you use that recursive IIR (it's a digital "integrator") and the difference between x[n] and the delayed x[n-N] to make this moving average filter.

now your problem with the truncated exponential for an impulse response (your original problem) is only slightly harder. really only just a teeny-weeny bit harder.

13. Apr 22, 2012

### paul_harris77

I think I understand what your saying - instead of using two IIR filters and subtracting their outputs (one delayed), you can use one IIR filter and subtract it's inputs.

I can't do a block diagram because I don't have any webspace to host the image at the moment, but I can describe what it would look like:

Input x[n] fed into a subtractor. Tap off x[n], delay by N samples and feed in as second input to subtractor. Output of subtractor is input to the FIR filter. Moving average output is the output of the FIR filter, y[n].

Is this correct?

In which case, for my example, if

$h[n]_{iir} = 2^{-n}$ for n>=0 and zero for n<0

$h[n]_{iir} = 2^{-n}\delta[n]+2^{-1}h[n-1]$

$h[n]_{iir} = \delta[n]+0.5h[n-1]$

therefore:

$y[n]_{iir} = x[n]+0.5y[n-1]$

therefore:

$y[n] = y[n]_{iir} = x[n]+0.5y[n-1]$

with $x[n]_{iir} = x[n] - x[n-4]$

Is this also correct?

Thanks :)

Paul