Forums

DSP Riddle: Infinitely Narrow Notch Filter

Started by Andor 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 other begins to fade? :-) Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
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. �����������������������������������������������������������������������
> >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 to your concern, though. 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 Posting from Google? See http://cfaj.freeshell.org/google/ "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[0] = 1, h1[1] = -2 cos(w0), h1[2] = 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 > to your concern, though.
Once again, math obscures underlying simplicity. It's evident that the inverse of a filter with a real zero can't be stable: it has a real pole. You don't need an input to excite such a filter. It's called an oscillator. 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;