# DSP Riddle: Infinitely Narrow Notch Filter

Started by May 19, 2006
```Tim Wescott wrote:
> Jerry Avins wrote:
>
>> Tim Wescott wrote:
>>
>>> Randy Yates wrote:
>>>
>>>
>>>> Tim,
>>>>
>>>> Which of Andor's requirements implied a finite-time filter?
>>>> --Randy
>>>>
>>>
>>> Well, reality kind of imposes that limitation.
>>>
>>> All of the discussion except for my suggestion of a Kalman filter got
>>> all snarled up in the zero times infinity problems inherent in an
>>> infinitely narrow notch filter -- at least if it's a linear time
>>> invariant (or shift invariant) filter.  Not only does the Kalman
>>> sidestep that problem, but it does so in a way that's physically
>>> realizable.
>>
>>
>>
>> I doubt it. You'd have to show that if it zeroed out 60.0000 Hz, it
>> would pass 60.0001 without attenuation or phase shift. Fat chance!
>>
>> Jerry
>
>
> Give it 10000 seconds.

Is that 10,000 seconds before the one begins to pass, or before the

Jerry
--
Engineering is the art of making what you want from things you can get.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```
```Randy Yates wrote:

> Tim,
>
> What does reality have to do with this problem? As far as
> I can tell, it's posed as a theory question.
>
> I don't mean to demean your Kalman filter solution - it
> seems like a good "practical" approach from what I
> know about them (which isn't much).
>
> --Randy

A voice coach once said, "Vibrato should not exceed ze minor sird!" What
are the limits on vibrato here?

Jerry
--
Engineering is the art of making what you want from things you can get.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```
```> >Consider the linear transformation H which transforms
> > an input sequence x[n] into an output sequence y[n]
> > using the following transformation rule:
> >
> > y[n] = x[n] + c0 x[n-1] + x[n-2] - c0 y[n-1] - y[n-2]  (1)
> >
> > with c0 = - 2 cos(w0).
>
> >I will show the proposed properties of the system H directly:
> >
> >1. H(w) = 1, for w =/= w0, and 0 <= (w, w0) <= pi (thanks Randy).
>
> [snip, because unimportant]
>
> > 2. H(w0) = 0.
> > We look at the response of the system to the input sequence
> > x[n] = exp(j w0 n). For simplicity, we use an intermediate
> > variable u[n], and rewrite (1) as:
> >
> > u[n] = x[n] + c0 x[n-1] + x[n-2],    (1.a)
> > y[n] = - c0 y[n-1] - y[n-2] + u[n].    (1.b)
> >
> > Computing u[n], we get:
> > u[n] = exp(j w0 n) + c0 exp(j w0 (n-1) ) + exp(j w0 (n-2))
> > = exp(j w0 (n-1)) ( exp(j w0) + c0 + exp(-j w0) )
> > = exp(j w0 (n-1)) ( 2 cos(w0) + c0) = 0
> >
> > where in the last step we used c0 = -2 cos(w0). Since
> > u[n] = 0 for all n, so is y[n] (which follows from equation (1.b)).
>
> That last comment in brackes is not correct. If u[n] = 0, then by
> equation (1.b) we have
>
> y[n] - 2 cow(w0) y[n-1] + y[n-2] = 0,
>
> which does _not_ imply y[n] = 0 for all n.

Now I'm completely confused :-).  My initial idea was the following:
First filter the signal with an FIR which has a zero at w0. Then filter
the output with the inverse filter - for all sinusoids with frequency
not equal to w0, the filter would return the input. For a sinusoid with
frequency w0, the output of the FIR would be equal to zero, and so
would therefore also be the output of the inverse IIR. Here is a block
diagramm:

x[n] ---> H1(z) ----> u[n] ----> 1/H2(z) ----> y[n]

A real notch filter, like r b-j's, has

H1(z) = 1 - 2 cos(w0) z^-1 + z^-2

and

H2(z) = 1 - 2 a cos(w0) z^-1 + a^2 z^-2

with 0 < a < 1. If the filter is excited with a sinusoid at w0, ie.
x[n] = exp(i w0 n), then u[n] and therefore (why?) y[n] are equal to
zero. However, if a = 1, clearly u[n] is still equal to zero. What
about y[n]? An instable filter excited with zero should still yield
zero output, no?

Regards,
Andor

```
```Andor wrote:

>> If u[n] = 0, then by equation (1.b) we have
>>
>> y[n] - 2 cow(w0) y[n-1] + y[n-2] = 0,
>>
>> which does _not_ imply y[n] = 0 for all n.
>
> Now I'm completely confused :-).  My initial idea was the
> following: First filter the signal with an FIR which has a zero
> at w0. Then filter the output with the inverse filter - for all
> sinusoids with frequency not equal to w0, the filter would
> return the input. For a sinusoid with frequency w0, the output
> of the FIR would be equal to zero, and so would therefore also
> be the output of the inverse IIR. Here is a block diagramm:
>
> x[n] ---> H1(z) ----> u[n] ----> 1/H2(z) ----> y[n]
>
> A real notch filter, like r b-j's, has
>
> H1(z) = 1 - 2 cos(w0) z^-1 + z^-2
>
> and
>
> H2(z) = 1 - 2 a cos(w0) z^-1 + a^2 z^-2
>
> with 0 < a < 1. If the filter is excited with a sinusoid at w0,
> ie. x[n] = exp(i w0 n), then u[n] and therefore (why?) y[n] are
> equal to zero. However, if a = 1, clearly u[n] is still equal to
> zero. What about y[n]? An instable filter excited with zero
> should still yield zero output, no?

As you observed before, the output is *indeterminate* as
long as no initial conditions are imposed. But it's easy
to see that y[n] = 0 for n >= 0 under the reduced equation
y[n] = -c y[n-1] - y[n-2] exactly when y[-1] = y[-2] = 0.

Martin

--
Quidquid latine scriptum sit, altum viditur.
```
```Martin Eisenberg wrote:
> Andor wrote:
>
> >> If u[n] = 0, then by equation (1.b) we have
> >>
> >> y[n] - 2 cow(w0) y[n-1] + y[n-2] = 0,
> >>
> >> which does _not_ imply y[n] = 0 for all n.
> >
> > Now I'm completely confused :-).  My initial idea was the
> > following: First filter the signal with an FIR which has a zero
> > at w0. Then filter the output with the inverse filter - for all
> > sinusoids with frequency not equal to w0, the filter would
> > return the input. For a sinusoid with frequency w0, the output
> > of the FIR would be equal to zero, and so would therefore also
> > be the output of the inverse IIR. Here is a block diagramm:
> >
> > x[n] ---> H1(z) ----> u[n] ----> 1/H2(z) ----> y[n]
> >
> > A real notch filter, like r b-j's, has
> >
> > H1(z) = 1 - 2 cos(w0) z^-1 + z^-2
> >
> > and
> >
> > H2(z) = 1 - 2 a cos(w0) z^-1 + a^2 z^-2
> >
> > with 0 < a < 1. If the filter is excited with a sinusoid at w0,
> > ie. x[n] = exp(i w0 n), then u[n] and therefore (why?) y[n] are
> > equal to zero. However, if a = 1, clearly u[n] is still equal to
> > zero. What about y[n]? An instable filter excited with zero
> > should still yield zero output, no?
>
> As you observed before, the output is *indeterminate* as
> long as no initial conditions are imposed.

But this is also the case for 0 < a < 1. u[n] is equal to zero, and
therefore y[n] is not determined. However, everybody agrees that y[n]
is equal to zero for the standard notch filter, if excited by a
sinusoid at the notch frequency.

```
```Andor wrote:
> > >Consider the linear transformation H which transforms
> > > an input sequence x[n] into an output sequence y[n]
> > > using the following transformation rule:
> > >
> > > y[n] = x[n] + c0 x[n-1] + x[n-2] - c0 y[n-1] - y[n-2]  (1)
> > >
> > > with c0 = - 2 cos(w0).
> >
> > >I will show the proposed properties of the system H directly:
> > >
> > >1. H(w) = 1, for w =/= w0, and 0 <= (w, w0) <= pi (thanks Randy).
> >
> > [snip, because unimportant]
> >
> > > 2. H(w0) = 0.
> > > We look at the response of the system to the input sequence
> > > x[n] = exp(j w0 n). For simplicity, we use an intermediate
> > > variable u[n], and rewrite (1) as:
> > >
> > > u[n] = x[n] + c0 x[n-1] + x[n-2],    (1.a)
> > > y[n] = - c0 y[n-1] - y[n-2] + u[n].    (1.b)
> > >
> > > Computing u[n], we get:
> > > u[n] = exp(j w0 n) + c0 exp(j w0 (n-1) ) + exp(j w0 (n-2))
> > > = exp(j w0 (n-1)) ( exp(j w0) + c0 + exp(-j w0) )
> > > = exp(j w0 (n-1)) ( 2 cos(w0) + c0) = 0
> > >
> > > where in the last step we used c0 = -2 cos(w0). Since
> > > u[n] = 0 for all n, so is y[n] (which follows from equation (1.b)).
> >
> > That last comment in brackes is not correct. If u[n] = 0, then by
> > equation (1.b) we have
> >
> > y[n] - 2 cow(w0) y[n-1] + y[n-2] = 0,
> >
> > which does _not_ imply y[n] = 0 for all n.
>
> Now I'm completely confused :-).  My initial idea was the following:
> First filter the signal with an FIR which has a zero at w0. Then filter
> the output with the inverse filter - for all sinusoids with frequency
> not equal to w0, the filter would return the input. For a sinusoid with
> frequency w0, the output of the FIR would be equal to zero, and so
> would therefore also be the output of the inverse IIR. Here is a block
> diagramm:
>
> x[n] ---> H1(z) ----> u[n] ----> 1/H2(z) ----> y[n]
>
> A real notch filter, like r b-j's, has
>
> H1(z) = 1 - 2 cos(w0) z^-1 + z^-2
>
> and
>
> H2(z) = 1 - 2 a cos(w0) z^-1 + a^2 z^-2
>
> with 0 < a < 1. If the filter is excited with a sinusoid at w0, ie.
> x[n] = exp(i w0 n), then u[n] and therefore (why?) y[n] are equal to
> zero. However, if a = 1, clearly u[n] is still equal to zero. What
> about y[n]? An instable filter excited with zero should still yield
> zero output, no?

Here is another way to look at it: Let h2 be the impulse response of
H2(z) (which is a harnonic oscillation for the case a = 1). Then

y[n] = (h2 * u)[n] = 0

because u[n] = 0 for all n. Does this prove the existence of the
infinitely narrow notch after all?

```
```Andor wrote:
> Martin Eisenberg wrote:
>> Andor wrote:
>>
>> >> If u[n] = 0, then by equation (1.b) we have
>> >>
>> >> y[n] - 2 cow(w0) y[n-1] + y[n-2] = 0,
>> >>
>> >> which does _not_ imply y[n] = 0 for all n.
>> >
>> > Now I'm completely confused :-).  My initial idea was the
>> > following: First filter the signal with an FIR which has a
>> > zero at w0. Then filter the output with the inverse filter -
>> > for all sinusoids with frequency not equal to w0, the filter
>> > would return the input. For a sinusoid with frequency w0, the
>> > output of the FIR would be equal to zero, and so would
>> > therefore also be the output of the inverse IIR. Here is a
>> > block diagramm:
>> >
>> > x[n] ---> H1(z) ----> u[n] ----> 1/H2(z) ----> y[n]
>> >
>> > A real notch filter, like r b-j's, has
>> >
>> > H1(z) = 1 - 2 cos(w0) z^-1 + z^-2
>> >
>> > and
>> >
>> > H2(z) = 1 - 2 a cos(w0) z^-1 + a^2 z^-2
>> >
>> > with 0 < a < 1. If the filter is excited with a sinusoid at
>> > w0, ie. x[n] = exp(i w0 n), then u[n] and therefore (why?)
>> > y[n] are equal to zero. However, if a = 1, clearly u[n] is
>> > still equal to zero. What about y[n]? An instable filter
>> > excited with zero should still yield zero output, no?
>>
>> As you observed before, the output is *indeterminate* as
>> long as no initial conditions are imposed.
>
> But this is also the case for 0 < a < 1.

Note that I did not refer to any particular coefficient value.

> u[n] is equal to zero, and therefore y[n] is not determined.

y[n] is not determined without IC's whatever u[n] is.

> However, everybody agrees that y[n] is equal to zero for the
> standard notch filter, if excited by a sinusoid at the notch
> frequency.

The standard notch filter output decays to zero independent of the
IC's, but it's not generally identically zero. True, the steady-state
response to an actual infinite sinusoid is identically zero, but zero
IC's at some finite starting time may be taken just to summarize the
infinite history in that state of affairs. In other words, upon
observing that a sine goes in and zeros come out we're unable to
distinguish whether the filter has been running forever or has been
kicked off with zero states a second ago. Not sure if that's germane

Martin

--
And from personal experience 'Save fat to fry the
Japs' and other such posters hung in the halls of
my elementary school -&#2013266070; and they were still around
several years after the war.       --Ken Greenwald
```
```Andor wrote:

>>>Consider the linear transformation H which transforms
>>>an input sequence x[n] into an output sequence y[n]
>>>using the following transformation rule:
>>>
>>>y[n] = x[n] + c0 x[n-1] + x[n-2] - c0 y[n-1] - y[n-2]  (1)
>>>
>>>with c0 = - 2 cos(w0).
>>
>>>I will show the proposed properties of the system H directly:
>>>
>>>1. H(w) = 1, for w =/= w0, and 0 <= (w, w0) <= pi (thanks Randy).
>>
>>[snip, because unimportant]
>>
>>
>>>2. H(w0) = 0.
>>>We look at the response of the system to the input sequence
>>>x[n] = exp(j w0 n). For simplicity, we use an intermediate
>>>variable u[n], and rewrite (1) as:
>>>
>>>u[n] = x[n] + c0 x[n-1] + x[n-2],    (1.a)
>>>y[n] = - c0 y[n-1] - y[n-2] + u[n].    (1.b)
>>>
>>>Computing u[n], we get:
>>>u[n] = exp(j w0 n) + c0 exp(j w0 (n-1) ) + exp(j w0 (n-2))
>>>= exp(j w0 (n-1)) ( exp(j w0) + c0 + exp(-j w0) )
>>>= exp(j w0 (n-1)) ( 2 cos(w0) + c0) = 0
>>>
>>>where in the last step we used c0 = -2 cos(w0). Since
>>>u[n] = 0 for all n, so is y[n] (which follows from equation (1.b)).
>>
>>That last comment in brackes is not correct. If u[n] = 0, then by
>>equation (1.b) we have
>>
>>y[n] - 2 cow(w0) y[n-1] + y[n-2] = 0,
>>
>>which does _not_ imply y[n] = 0 for all n.
>
>
> Now I'm completely confused :-).  My initial idea was the following:
> First filter the signal with an FIR which has a zero at w0. Then filter
> the output with the inverse filter - for all sinusoids with frequency
> not equal to w0, the filter would return the input. For a sinusoid with
> frequency w0, the output of the FIR would be equal to zero, and so
> would therefore also be the output of the inverse IIR. Here is a block
> diagramm:
>
> x[n] ---> H1(z) ----> u[n] ----> 1/H2(z) ----> y[n]
>
> A real notch filter, like r b-j's, has
>
> H1(z) = 1 - 2 cos(w0) z^-1 + z^-2
>
> and
>
> H2(z) = 1 - 2 a cos(w0) z^-1 + a^2 z^-2
>
> with 0 < a < 1. If the filter is excited with a sinusoid at w0, ie.
> x[n] = exp(i w0 n), then u[n] and therefore (why?) y[n] are equal to
> zero. However, if a = 1, clearly u[n] is still equal to zero. What
> about y[n]? An instable filter excited with zero should still yield
> zero output, no?
>
> Regards,
> Andor
>
Yes but.

A metastable filter excited with zero will have an output who's
characteristic does not change -- your filter, as constructed, will
ignore any pure tone at the design frequency, but it will freely
_generate_ a pure tone at that design frequency, with an arbitrary
amplitude and phase.

You can try to get around that by saying that the filter states and the
input are zero at n < 0 -- but then your tone is no longer pure, and
your filter will have a nonzero output from n = 0 until the end of time.

You can't get around _that_ problem and still have an infinitely narrow,
time invariant notch filter.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

"Applied Control Theory for Embedded Systems" came out in April.
See details at http://www.wescottdesign.com/actfes/actfes.html
```
```Tim Wescott wrote:
> Yes but.

[buts snipped]

> You can't get around _that_ problem and still have an infinitely narrow,
> time invariant notch filter.

Agreed (I have already touched on the subject of the generated tone of
the filter in another of my posts). However, the solution to those
problems was not part of the riddle - it only called for a filter of
finite order and with a specified frequency response. For the records,
here is my official solution to the riddle:

Solution to the Riddle (V2.0)
-----------------------------

Construction of an infinitely narrow notch using two second-order
sub-systems in series.

Consider the two linear, causal systems H1(z) and H2(z) defined by
their impulse response

h1 = 1, h1 = -2 cos(w0), h1 = 1,
h1[n] = 0 for all other n,

and

h2[n] = 1/sin(w0) sin(w0 n + w0), n >= 0,
h2[n] = 0, n < 0.

A z-transform of h2 and h1 shows that H2(z) = 1/H1(z). Define the
system H(z) as

H(z) = H1(z) H2(z)

as depcited in Fig.1.

.----------------------------------.
|                                  |
|  .-------.            .-------.  |
x[n] o--|--| H1(z) |--o u[n] o--| H2(z) |--|--o y[n]
|  '-------'            '-------'  |
|                                  |
'-------------- H(z) --------------'

Fig.1. Structure of the notch filter H(z).

To find the frequency response of this system, we calculate the
response to the complex sinusoid x_w[n] := exp(i w n). Some
"obfuscating maths" shows:

1. y_w[n] = x_w[n] for w =/= w0.
2. u_w0[n] = 0 and therefore y_w0[n] = (u_w0 * h2)[n] = 0,

These are just the required infinitely narrow notch properties

1. H( exp(i w) ) = 1, for w =/= w0,
2. H( exp(i w0) ) = 0.

It is interesting to note that the unit impulse response of H(z) is the
unit impulse.

Regards,
Andor

```
```Martin Eisenberg wrote:
> Andor wrote:
>
>>Martin Eisenberg wrote:
>>
>>>Andor wrote:
>>>
>>>
>>>>>If u[n] = 0, then by equation (1.b) we have
>>>>>
>>>>>y[n] - 2 cow(w0) y[n-1] + y[n-2] = 0,
>>>>>
>>>>>which does _not_ imply y[n] = 0 for all n.
>>>>
>>>>Now I'm completely confused :-).  My initial idea was the
>>>>following: First filter the signal with an FIR which has a
>>>>zero at w0. Then filter the output with the inverse filter -
>>>>for all sinusoids with frequency not equal to w0, the filter
>>>>would return the input. For a sinusoid with frequency w0, the
>>>>output of the FIR would be equal to zero, and so would
>>>>therefore also be the output of the inverse IIR. Here is a
>>>>block diagramm:
>>>>
>>>>x[n] ---> H1(z) ----> u[n] ----> 1/H2(z) ----> y[n]
>>>>
>>>>A real notch filter, like r b-j's, has
>>>>
>>>>H1(z) = 1 - 2 cos(w0) z^-1 + z^-2
>>>>
>>>>and
>>>>
>>>>H2(z) = 1 - 2 a cos(w0) z^-1 + a^2 z^-2
>>>>
>>>>with 0 < a < 1. If the filter is excited with a sinusoid at
>>>>w0, ie. x[n] = exp(i w0 n), then u[n] and therefore (why?)
>>>>y[n] are equal to zero. However, if a = 1, clearly u[n] is
>>>>still equal to zero. What about y[n]? An instable filter
>>>>excited with zero should still yield zero output, no?
>>>
>>>As you observed before, the output is *indeterminate* as
>>>long as no initial conditions are imposed.
>>
>>But this is also the case for 0 < a < 1.
>
>
> Note that I did not refer to any particular coefficient value.
>
>
>>u[n] is equal to zero, and therefore y[n] is not determined.
>
>
> y[n] is not determined without IC's whatever u[n] is.
>
>
>>However, everybody agrees that y[n] is equal to zero for the
>>standard notch filter, if excited by a sinusoid at the notch
>>frequency.
>
>
> The standard notch filter output decays to zero independent of the
> IC's, but it's not generally identically zero. True, the steady-state
> response to an actual infinite sinusoid is identically zero, but zero
> IC's at some finite starting time may be taken just to summarize the
> infinite history in that state of affairs. In other words, upon
> observing that a sine goes in and zeros come out we're unable to
> distinguish whether the filter has been running forever or has been
> kicked off with zero states a second ago. Not sure if that's germane