5.3 - Filter stability

Welcome to module 5.3.

Filters are processing devices, processing machines and like for all machines,

we want to make sure that it don't blow up in our face.

Well, off course, this is the digital domain so nothing is going to literally blow up,

but we are interested in the concept of stability.

Namely, we want to make sure that if the input to a filter is a nice, well-behaved sequence,

the output will be nice and well-behaved as well.

It turns out that stability is related to the structure of the impulse response,

so lets see under which conditions we can sleep with both eyes closed.

Welcome to module 5.3 of Digital Signal Processing

in which we will talk about filter stability.

And before we tackle the stability problem,

we will also draw our first classification of filters,

based on their properties in the time domain.

According to the shape of their impulse response,

we can already label a filter as belonging to one of the following categories.

You have Finite Impulse Response filters, or FIRs, for short.

Infinite Impulse Response, or IIR,

Causal filters

and non causal filters.

FIR filters have an impulse response with a finite support.

Because of that, and because of how the convolution sum is computed,

only a finite number of samples are involved in the computation of each output sample.

A typical example of FIR filter,

is the moving average filter that we've seen before

where only M samples are non-zero.

IIR filters, on the other hand, have an infinite support for their inputs response.

So, potentially, an infinite number of samples are involved

n the computation of each output sample.

However, perhaps surprisingly, in many cases

we can still compute each output sample in a finite amount of time.

One notable exception is the class of Ideal Filters, which we will study shortly.

For instance, the leaky integrator has an infinite support impulse response,

but due to its algorithmic nature, we can compute each output sample

with only three operations.

A filter is said to be causal if its impulse response is 0 for n < 0.

Now if you remember how the convolution sample is computed

-- the convolution involves a time reversal of the impulse response

before multiplication with the input --

That means that only past values of the input

are involved in the computation of the output.

So, for instance, if your impulse response is like this and this is 0,

when you compute the convolution sum you time-reverse it,

and so you will only affect values in the past.

Causal filter, because of their dependency only on the past, can work "on line",

they can work in real time.

A [non?]causal filter, on the other hand, is a filter for which the impulse response

has some nonzero tabs for positive values of the index.

In other words, non-causal filters will need samples from the future

in order to be able to compute their current output value.

As such, they can of course, not work in real time, but there are applications in which

the future is indeed available to a processing system

in particular when you do what is called batch processing

namely processing for which all the data is available in advance.

A typical case in point is image processing

in which the whole picture is available for processing before you start.

The Moving Average filter is again, a causal filter.

We have developed it in a causal fashion,

and indeed, its impulse response is non-zero,

only for positive or null values of the index.

We could develop a non-causal moving average

if we center the impulse response in zero.

And indeed if we do so, we would eliminate the delay that you've seen

when computing longer and longer averages,

because we would compensate the delay by looking at future samples.

We could apply this to a set of data

that we've already stored in computer memory for instance.

Let's talk now about stability.

Stability is important because it guarantees that a system

will not behave unexpectedly if the input to the system is well-behaved.

In signal processing, a well-behaved input is a bounded input,

namely, a signal for which we know the maximum excursion.

We want a system to behave well when the input is bounded.

And the concept of bounded input bounded output stability

or BIBO stability for short, formalizes this

by requiring that a system produces a bounded output, when the input is bounded.

So, a well-behaved output for a well-behaved input.

The fundamental stability theorem for Later (?) filters states that,

a filter is BIBO stable if and only if its impulse response is absolutely summable.

So we're going to prove this.

And we're going to prove both the necessary and sufficient condition.

So we start with the sufficient condition,

and we say that our hypotheses are that our input is bounded,

and that the impulse response of the filter is absolutely summable.

And what we want to prove is that, in this case, the output will be bounded.

Now the proof is very simple.

We start by considering the magnitude of the output of the filter,

which is just the magnitude of the convolution sum written here as

the sum for k that goes to minus infinity to plus infinity of h[k]x[n-k].

Notice here that we use the commutative property of the convolution

and we actually time-reverse and delay the input

rather than the impulse response.

Now the magnitude of the sum is maximized

by the sum of the magnitude of its terms,

and this in turn is maximized by the following expression.

Where we have replaced the magnitude of the input by it's upper bound M,

and we are left therefore with M that multiplies

the sum from minus infinity to plus infinity of the magnitude of the impulse response,

but we know that the impulse response is absolutely summable,

and therefore, the output will be bounded by the product nl (?), which is finite.

As for the necessary part, we'll proceed as follows.

The hypotheses now are that both input and output are bounded,

and we want to prove that in this case, h[n] must be absolutely summable.

The proof will proceed by contradiction, and it is a little bit tricky

but not difficult at all.

So assume by contradiction that the impulse response

is not absolutely summable.

Therefore the sum of its magnitude is plus infinity

at which point we can build an artificial input as follows.

x[n] will be equal to +1 if h[- n] is positive,

and minus 1 if if h[- n] is negative.

Well clearly x[n] built as such is a bounded signal

because it's between +1 and -1.

However if we try to compute the response of the system defined by h[n] in 0,

we have that the output y[0] is the convolution between our artificial input x[n]

and the impulse response computed in 0.

So we write out the convolution sum explicitly.

So it's a sum for k that goes from minus infinity to plus infinity of h[k]x[-k],

because remember n=0 here in this convolution

and of course, by definition

this will be the sum of the magnitude of h[k]

because we built a signal like so

and because of our initial assumption this will be plus infinity.

So, we have proven that h[n] must be absolutely summable,

because if it were not

I could find a bounded input that would make the system explode.

So, the good news is that FIR filters are always stable,

because their impulse response only contains a finite number of non-zero values,

and therefore, the sum of their absolute values will always be finite.

When it comes to IIR filters, on the other hand,

we have to explicitly check for stability.

And for the time being the only way we know how to do so,

is by going through the sum of the absolute values of the impulse response.

And if we do the exercise with our friend, the Leaky Integrator,

we get the sum for n that goes from zero to infinity

of magnitude of λ to the power of n,

multiplied by a leading factor of 1-λ in magnitude.

This is just a geometric sum, and we know that it's equal to

the limit for n that goes to infinity

of 1 minus magnitude of λ to the n plus 1 divided by 1-λ.

-- Always multiply by this factor that doesn't really bother us --

This limit converges only if λ is less than one in magnitude.

And therefore, stability of the Leaky Integrator

is guaranteed only for λ less than one in magnitude.

Later on in this module, we will study indirect methods for filter stability

that will allow us to determine whether a filter is stable or not,

without going through the impulse response explicitly.