Jump to content

Talk:Filter design

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Untitled

[edit]

Wouldn't it be nice to have a frequency domain filter page (or "Filter (frequency domain)") to gather all the low-pass, high-pass, ... stuff on one page, rather than on electronic filter, digital filter, ...?

There's no suitable "filter" article on Wikipedia

[edit]

"Filter" itself is of course a large disambiguation page with many many many links. Where the word "filter" appears in the first sentence, one would like to say [[this other article|filter]], but there's really no suitable value of "this other article". Electronic filter? No—that's only a special case. The filters used in, for example, statistical analysis of time series and some other areas of applied math are mathematical abstractions implemented in computer programs or sometimes only in abstract discussions in scholarly papers—they're not electronic filters, but clearly they SHOULD be included in the topic of "this other article" to which one would link. Michael Hardy 20:07, 19 August 2006 (UTC)[reply]

You have pointed out a relevant issue, and I agree that there should be an article on filters which describes and exemplifies different ways of thinking about filters in the sense that they are used here. About the title, I suggest "Filter (signal processing)" which could be based a lot on LTI system theory but also give a example of non-linear filters (Volterra stuff) and shift-variant filters. The term signal processing does not have to be interpreted in the narrow sense of electronics and digital devices. A signal is the same as a function but with the additional assumption that it carries some specific information. --KYN 07:55, 21 August 2006 (UTC)[reply]

Untitled

[edit]

User Glrx did delete the link to the freeware filter design software QuickFil. I cannot understand this as this is a great tool for the design of passive filters. Could you please explain your reason for deleting the link? Would you prefer to create a list of freeware filter design software? Flo321 (talk) 09:26, 27 April 2011 (UTC)[reply]

There was a recent addition for QuickFil/Omicron Labs that sounded in advertising, self-promotion, and WP:LINKSPAM. It contributed little to the article. See also WP:NOTHOWTO. See also WP:ELNO
Furthermore, the IPuser who started the above message leads back to Omicron Electronics GMBH[1]. Consequently, it looks like User:Flo321 (who currently has a grand total of 5 WP edits and whose first edit was to tout QuickFil) has a WP:COI with respect to QuickFil/Omicron and runs up against WP:ADV. Do you want to own up to those little tidbit? Promote your product elsewhere.
Moreover, I didn't delete just the QuickFil link to Omicron - I deleted 3 links yesterday. WP doesn't want EL sections becoming of directory list of products (whether those products are free or otherwise). The two other links I deleted were already mentioned in dspGuru or Circuit Sage. I didn't see QuickFil in those lists (maybe its there), but that suggests mention of QuickFil here is WP:UNDUE.
Glrx (talk) 14:23, 27 April 2011 (UTC)[reply]
I support those deletions, there is far too much of that kind of thing on Wikipedia already. SpinningSpark 20:55, 27 April 2011 (UTC)[reply]

Do FIR filters never have feedback paths within them?

[edit]

Sorry, User:Kvng, but you are decidedly mistaken.

A moving average filter may be implemented without feedback since any FIR filter can be implemented in the straight-forward manner:

(Eq 1)

where all coefficients are h[n] = 1/N . No feedback. You'll need N multiply-accumulate operations per output sample.

But Kvng, I am sure you know that this is not how moving average filters are commonly done, particularly when N is large. They do it like this:

(Eq 2)

Are you trying to convince us that there is no feedback or recursion in that implementation? What is the y[n-1] term, if that is not feedback or recursion? Looks like there is a digital integrator in there with a pole spot on DC at z=1. Now since the whole thing is FIR and we all know that the input/output characteristics of FIR filters can only have poles at z=0, that means that the pole at z=1 must be canceled with at least one zero at the same location. And it is, with (x[n]-x[n-N]).

"Things should be simple as possible, but no simpler."

While it may be simpler to remember ("No FIR filters have feedback or recursion"), it is a fallacy, an inaccuracy. Encyclopedias should, at the very least, be accurate. 71.169.182.178 (talk) 18:27, 5 December 2012 (UTC)[reply]

I'm not saying you are wrong, but please stop edit warring in the article and resolve the issue here first. SpinningSpark 21:32, 5 December 2012 (UTC)[reply]
I'd like to first clarify what you think I'm mistaken about. Please identify which (if any) of the below statements is true. -—Kvng 16:02, 8 December 2012 (UTC)[reply]
  1. A moving average is not a generic FIR filter
  2. Generic FIR filters use feedback
The term "generic FIR filter" might need a little help in defining. I'll make a stab at it, and if my definition is not congruent to yours, we'll need to start over.
An FIR filter is a filter that, assuming infinite precision (no rounding or quantization) and assuming causality (h[n]=0 for all n<0), there exists a finite integer N such that h[n]=0 for all nN. If that is the case, it's an FIR. The length of the impulse response is finite.
Now, my understanding of "generic" is that it means the broadest sense of inclusivity. Most general or comprehensive. In my opinion it is the lack of anything specific that makes it generic. If that is the case, then strictly speaking, it should not change the meaning of the noun that generic is added to. It's just a note to the reader that whatever this generic thing is, it is not specific to anything other than what the noun is itself. If that is the case, then a "generic FIR filter" is an FIR filter however it is implemented. Whether as the straight-forward summation (which has no feedback and is inherently stable), or as fast-convolution (which also has no feedback and is stable), or as a Truncated IIR filter (which does have feedback and may be stable, but is not inherently stable because internal states might be exploding, but since the system is not completely observable, we can't tell it's exploding inside by looking at the output). Perhaps there are other specific forms of FIR filters, but those are the only three I know about at this time.
So my answer to 1 is that what we usually mean by a "moving average filter" (where the weighting coefficients are all equal) is an FIR filter. There are weighted moving average filters that have unequal coefficients (but they must all add to 1) and even an exponentially-weighted moving average filter that is an IIR. In fact, I would say that any LTI low-pass filter that has DC gain of 1 is a moving-average filter or at least can lay claim to that label.
My answer to 2 is that some, even if relatively few, FIR filters use feedback internally. As far as I know, all of these specific FIR filters come under the class Truncated IIR filters. But as I said originally, if there is feedback, which means at least one pole that lives somewhere other than at z=0, that there must be something in the filter structure that puts in a zero that precisely cancels that pole. That pole is still there internally, but you cannot tell from only the input/output characteristics (unless it's an unstable pole and you have finite-width words for your arithmetic). A Truncated IIR filter cannot be a generic FIR. If they're stable, their impulse response is a causal, decaying exponential or damped sinusoid, until they get truncated by adding a delayed function of the same form that causes all remaining h[n] to go to zero. I guess, in the broadest terms, a Truncated IIR is the sum of truncated exponentials (if you include complex exponents).
So, I guess, if you were to pin me down on it, I would say, as stated, both statements 1 and 2 are false. 2 is more clearly false because it appears to exclude the possibility of an FIR not using feedback, which is clearly a mistaken exclusion. But the negative of 2 is also false. FIR filters may use feedback, but not necessarily. Statement 1 is also false for the reason that it is too specific. A moving average filter may or may not be FIR. But there are certainly examples of moving average filters that are FIR and of those filters, some may have feedback (likely if N is large) and some may not.
But, of course, most FIRs are not Truncated IIR filters, so those FIRs have no feedback and are inherently stable. But my guess is that nearly all moving-average or moving-sum filters that sum up or average a large number of input samples are implemented with feedback. Using fixed-point arithmetic you can do this without any numerical crap getting stuck in the feedback loop (what gets added now is precisely subtracted later). 71.169.182.178 (talk) 23:34, 8 December 2012 (UTC)[reply]
Let me simplify. This is what I mean by a generic FIR filter: Hopefully this clarification allows you give a simple answer to my questions. If you insist that is not the case, I will come back and more carefully review your lengthy answer. -—Kvng 03:25, 15 December 2012 (UTC)[reply]
A quick answer is, if that is what you mean by a "generic FIR filter", then I would say that most moving-average filters are not implemented that way (like Eq 1 above) but are implemented with a recursive structure that Eq 2 above describes. A moving-average filter may be implemented as the generic FIR filter according to your semantic, but need not be, nor would likely be so if N was large. Just because N is large does not take away it's an FIR. But it's an FIR with recursion or feedback inside of it. It's not accurate to say that no FIR filters have feedback. Some do. Given your semantic, these FIR filters with internal feedback aren't "generic FIR filters". My semantic would call them "FIR filters" simply because their impulse response is finite in length (and not because of finite word width or some other non-linear phenomena). I would also call filters that are implemented with that "Overlap Add" or "Overlap Save" method, i would call those "FIR filters". 71.169.183.95 (talk) 06:30, 17 December 2012 (UTC)[reply]
It might be better to describe that circuit as the canonical form rather than generic form. I take it that you are not disputing filters of the type described by 71.169 actually exist? (That is, moving average filters with internal feedback and an FIR response). So it seems this dispute may revolve around terminology rather than technical detail. In such cases we normally look to reliable sources for a solution. There is no shortage of sources stating FIR filters have no feedback, eg [2]. On the other hand, we can easily find sources describing moving average filters using recursion algorithms, and statements that such filters are FIR, eg [3]. However, the sources invariably describe such filters as a special case of recursive filters rather than a variation of the generic FIR. This book states it nicely: Hence, a non-recursive (FIR) filter always has a finite impulse response, while a recursive filter commonly has an infinite impulse response, but may in some cases have a finite impulse response. SpinningSpark 12:30, 15 December 2012 (UTC)[reply]
I'm troubled by this debate. I follow Spinningspark's comments. IIR and FIR are terms intended to describe classes of filters. 71.169 is clearly knowledgeable about filters, but I think it is inappropriate to examine the literal meaning of FIR and claim a TIIR is an FIR in the sense that the IIR/FIR distinction intends. There are also caveats about practical operation to make a TIIR system work. It may have a finite impulse response, but it is distinguishable from the conventional, stable, FIR design. I can view the MA filter with equal tap weights as a numerical optimization rather than a feedback system (if we can agree on setting initial conditions - even a wrong initial value of y[n-1] above causes trouble). Instead of summing all the inputs at each sample time, I just calculate the change in the sum due to the incoming and outgoing sample.
To play devil's advocate, the unit sample response of some IIR filters may decay to zero after a finite number of samples due to imprecision in the arithmetic. If idealness makes a TIIR an FIR, does non-idealness make an IIR filter an FIR? With a two unit sample, the filter may take more samples to decay to zero, so the filter is not linear. We don't look too closely at some characterizations.
To me, the distinction is FIR filters do not use feedback and IIR filters use feedback; using the impulse response characterization is describing an artifact. The TIIR case can be cured with a footnote and appropriate citations.
The whole digital filter section has uncertain direction, and this debate only compounds that confusion. As stated above, I disagree with the opening sentence: "Digital filters are classified into one of two basic forms, according to how they respond to a unit impulse". That statement leads us into this debate. A recursive/nonrecursive view of the FIR/IIR distinction does not present the same ambiguity. Bringing up the MA exception before FIR is fully explained is not helpful. Saying IIR filters have state suggests FIR filters do not, but they do (the last N input samples). There are analog delay line filters, so analog filters need not be IIR. Many FIR filters are not linear phase (and are even used to correct group delay caused by analog systems). Cascading 2nd order biquads was done in analog filters; analog filters also worry about overflow and underflow -- only in the analog domain it's called clipping and dynamic range. There's a lot being said. It's not exactly wrong, but it is jumping around.
Glrx (talk) 02:01, 17 December 2012 (UTC)[reply]
I'm not sure where this is headed. My participation in this dispute was reversing what appeared to be an unhelpful tangent into hybrid filter design inserted by user:71.169.182.178. According to user:71.169.182.178's first post in this thread, that's apparently not what I was reverting. Since then I've just been asking questions to try to understand what the disputed edits are trying to say. -—Kvng 02:54, 17 December 2012 (UTC)[reply]
I fully agree with Glrx that the usual approach in sources is to describe from a non-recursive/recursive split rather than a FIR/IIR split. The material then proceeds reasonably understandably. NR are always FIR - recursive are usually IIR - there are some special cases arrived at through exact choice of poles and zeroes that result in a reursive FIR. SpinningSpark 07:55, 17 December 2012 (UTC)[reply]

Thanks for the responses. I think I understand where user:71.169.182.178 is coming from now.

Here's the original version of the disputed paragraph:

*Finite impulse response, or FIR, filters express each output sample as a weighted sum of the last N input samples, where N is the order of the filter. FIR filters normally do not use feedback and are inherently stable. A moving average filter or CIC filter are examples of a FIR filters. If the FIR coefficients are symmetrical (often the case), then such a filter is linear phase, so it delays signals of all frequencies equally which is important in many applications. It is also straightforward to avoid overflow in an FIR filter. The main disadvantage is that they may require significantly more processing and memory resources than cleverly designed IIR variants. FIR filters are generally easier to design than IIR filters - the Parks-McClellan filter design algorithm (based on the Remez algorithm) is one suitable method for designing quite good filters semi-automatically. (See Methodology.)

user:71.169.182.178 has changed it to add a mention of Truncated IIR. I think that's too tangential for this summary. I'm not opposed to adding it to Finite impulse response if not already there.

user:71.169.182.178 also has changed the description of moving average filter and CIC filter from FIR to TIIR. Sure, as an optimization these can be implemented with recursion. That does not make them IIR. I suppose we can argue whether a TIIR is really FIR but, like I say above, I really think TIIR does not belong in this summary. CIC filter explicitly says it is an optimized FIR filter so calling it TIIR here is inconsistent. Moving average does not mention FIR or other filter design terms but my position is that if it can be implemented with the generic FIR topology it is FIR. The way you implement it (Eq 1 vs. Eq 2) does not change the response characteristic of the filter and the response characteristic is what we're trying to classify here because the section intro says so Digital filters are classified into one of two basic forms, according to how they respond to a unit impulse: -—Kvng 15:10, 20 December 2012 (UTC)[reply]

I never said that TIIR is IIR. In fact, I think I have always said that TIIR is FIR. If you truncate something of infinite length, you get something of finite length. Now, just as there is mention of it in Moving average, there are MA filters with unequal weighting and a simple exponential-weighted MA is IIR. And, here on this talk page, I generalized and pointed out that any LTI low-pass filter that has DC gain equal to 1 (or 0 dB) qualifies as a moving average filter. MA filters are most commonly equal weighted (1/N) FIR filters and are most commonly implemented as a TIIR, and as such, use feedback. CIC filters also, most commonly, use feedback, but they are FIR.
We can walk this back to the beginning of my participation. My main aim is to correct the inaccuracy that "Since they [FIR filters] do not use feedback, they are inherently stable." That statement is not always true. Some (even most, perhaps nearly all) FIR filters do not use feedback or recursion. And it is true that any filters that do not use feedback are inherently stable. But not all FIR filters are that. This FIR filter:
(Eq 3)
is an FIR filter, uses feedback and, if |p|>1, is not stable. This is a counter-example that decidedly refutes that statement that I originally corrected.
We don't need language about TIIR filters (or of fast-convolution filters) in this article, but there should be something about it in the main FIR article (as well as something about fast-convolution; OLA and OLS). But, even in this article, we should not say things that are inaccurate. 70.109.176.104 (talk) 17:37, 20 December 2012 (UTC)[reply]
Can you explain to me why you believe your example above is FIR? Being unstable, it does not conform to the definition or FIR given in Finite impulse response (Once excited it will not return to zero in finite time). -—Kvng 04:10, 21 December 2012 (UTC)[reply]
Because the impulse response is
where u[n] is the unit step function. That's a finite impulse response.
It's an internal state that isn't settling down, but the impulse response is of finite length. The transfer function of this FIR filter has all of its poles at z=0. Looking at it from a state variable POV, there is this pole at z=p, but that pole is canceled by a zero because
so you don't see it in the input/output characteristics. Until, of course, numerical limits are exceeded or there is growth of quantization error when |p|>1. However, if |p|<1, it's stable. Even if p=1 (the moving-sum filter) it's even practically stable with a finite wordsize for the feedback term.
These really are FIR filters. I'm not making this up, but it looks like this term (from Wang and Smith) Truncated IIR filter is not yet an article in Wikipedia. We've known for years about Fast convolution (another red link, how dreadful) and those are FIR filters (they have to be). But, I suppose, if you were going to look at quantization error in the impulse response, there would be something slipping past sample h[N-1], but theoretically, fast convolution is FIR. So also are Truncated IIR filters. They are FIR. But there's funky stuff going on inside when it's unstable. You can't see the funky stuff happening inside by looking at the output because it is not observable. 70.109.176.104 (talk) 06:18, 21 December 2012 (UTC)[reply]
I made a terminology mistake. The example above is not controllable. The only state is the same as the output, y[n], (I guess x[n-1] through x[n-N] are states) and since you're observing directly that state, it's observable. Direct Form I LTI systems are observable even if there is pole-zero cancellation and Direct Form II LTI systems are controllable, even if there is pole-zero cancellation. If there is pole-zero cancellation, the LTI system cannot be both completely observable and completely controllable. So the DF2 counterpart of the above (that is not observable) is:
(Eq 4a)
(Eq 4b)
In this case, states w[n-1] through w[n-N] are not completely observable. They could be going to hell (if p>1) and you wouldn't know it by looking at the output y[n] until numerical limits of the finite word width of w[n] are exceeded.
But the main point remains. This is an FIR filter with impulse response indicated above. And it has recursion or feedback and it is not inherently stable. 70.109.176.104 (talk) 20:43, 22 December 2012 (UTC)[reply]
Sorry. That didn't really answer my question. On closer inspection, your example (eq. 3) is a contrived form of weighted moving average and can be rewritten in generic FIR format. This computationally optimized "feedback" form is derived in Moving_average#Cumulative_moving_average. From a signal processing perspective it has a strange non-linear response but it is stable.
I apologize if I still don't understand your point but I believe your basic contentions are that
  1. FIR filters can be implemented with feedback and
  2. therefore not all FIR filters are stable
I can go along with 1 as long as it is clear that this is done for computational efficiency and there is always an equivalent generic form for the filter (but this sort of discussion belongs in Finite impulse response not it this article). I'm not convinced of 2. Here are some references that support unconditional FIR stability: [4], [5], [6]. -—Kvng 18:15, 25 December 2012 (UTC)[reply]
Book sources also generally support your opposition to statement 2; [7] (the same source I quoted above which also admits of recursive FIRs), [8][9][10][11] but I did find this Recursive FIR filters may be unstable because of imperfect pole/zero annihilation. However, this is purely a practical consideration, if pole-zero cancellation has not been accurate then the filter is probably no longer truly FIR. SpinningSpark 19:28, 25 December 2012 (UTC)[reply]
Well, Merry Christmas, guys. First, Spark, this book reference [12] is inaccurate. FIR filters do have poles. An N tap FIR filter is of order N-1 and has N-1 poles located at z=0. It has to. But we know that those poles are the most stable poles you can get. Second, of course if the pole/zero cancellation ain't perfect, it's really an IIR. But even if the pole/zero cancellation is spot on, from the POV of a state-variable system, it can be unstable and is unstable if the pole (that is perfectly canceled by the zero) is outside the unit circle. This is evident if it's the DF2 version (Eq 4) where the internal IIR filters is driven directly from the input. If p>1, the state w[n] is exploding and even if that pole is perfectly canceled that internal state is still exploding.
Now in the DF1 version (Eq 3) the input first goes though the zeros ( x[n] - x[n-N] ) which, if the pole/zero cancellation is perfect, can return the internal state to exactly zero after N samples. But it's still zero with an unstable feedback. If this was a floating-point filter, there can be quantization errors that result in noise that will eventually grow (if p>1) to be a problem. But for the moving average filter (when p=1 exactly), you can make this pole/zero cancellation be perfect and if implemented in fixed point with your accumulator word wide enough (log2(N) bits wider than the signal word), then there is no quantization error at all and your "critically stable" TIIR filter will be sufficiently stable. But I would not implement it with Eq 4, I would do it the Eq. 3 way.
Kvng, please take a closer look your question: "Can you explain to me why you believe your example above is FIR?"
I answered that directly and immediately. It's FIR because the IR is F. That is the only reason, and that is sufficient. And, if implemented in the Eq 4 manner (a DF2 filter), the internal state is exploding (if p>1) and you cannot see that explosion in the output y[n] until there are numerical issues with the finite-width word (a "practical" consideration). It's still an FIR and it still is unstable.
I am still answering your objections. Again, I am not saying that this issue should be dealt with in this article, maybe it should go to the general FIR article. But we shouldn't put in anything in this article that we know is inaccurate, unless at least we toss in a caveat. 70.109.176.104 (talk) 06:09, 26 December 2012 (UTC)[reply]
Nor do we put things in Wikipedia that are not verified by reliable sources. There are a very large number of RS quite happy to make the statement that FIR are unconditionally stable without qualification. Why should Wikipedia be introducing such complications if they are never met with in real life? Can you point to a RS demonstrating a recursive FIR filter which is unstable but still remains FIR (ie has not transformed into an IIR because of some inaccuracy)? SpinningSpark 16:36, 26 December 2012 (UTC)[reply]
I have done this in the past and I will again:
Wang & Smith; On Fast FIR Filters Implemented as Tail-Canceling IIR Filters
Here are additional references to this concept of TIIR:
Kurosu, et. al.; A technique to truncate IIR filter impulse response and its application to real-time implementation of linear-phase IIR filters
Robert J Marks II; Handbook of Fourier Analysis & Its Applications
Rangarao & Mallik; Digital Signal Processing: A Practitioner's Approach
Walstijn & Smith; Use of Truncated Infinite Impulse Response (TIIR) Filters in Implementing Efficient Digital Waveguide Models of Flared Horns and Piecewise Conical Bores with Unstable One-Pole Filter Elements
70.109.176.104 (talk) 17:54, 26 December 2012 (UTC)[reply]
So, you believe
  1. TIIR is a form FIR and
  2. TIIRs can be unstable
Again, I can agree with 1 but don't believe it belongs in this article at least not until someone writes a TIIR article. I can't accept 2. What definition of stability are you using? What do your refs have to say about TIIR stability? A liberal definition of stability is bounded output given bounded input. TIIRs seem to be unconditionally stable by this definition. -—Kvng 18:20, 26 December 2012 (UTC)[reply]
TIIR is FIR. An infinite sequence that is truncated is no longer infinite. This is not a matter of belief, it is a matter of fact. It can also be a matter of semantics: I would not call a TIIR an "IIR", it's "FIR". So I would not say that, strictly speaking, an IIR filter is ever linear phase as is suggested in the titles of some of these reference papers. They're really FIR. They're truly linear phase (not just an approximation to linear phase by use of all-pass filters), but they're not IIR.
Stability in systems (linear or not) is not only BIBO stability. Stability is not solely a property of the output. The internal states need to be stable for a system to be stable without qualification. This is something that the control systems engineers knew for many decades. This is why concepts of state variable systems, controllability, and observability relate to this. You can have a system that is fully stable in a BIBO sense, but is going to hell inside. That system is hardly "stable" without explicit qualification. A TIIR filter described as in Eq 4 above, is FIR in the input/output sense (and impulse response is a property of the input and output) and is not completely observable due to a pole/zero cancellation. If, using the Eq 4 implementation, the pole p is greater than 1, that TIIR filter, which is FIR, is also unstable but not in a BIBO sense until numerical limits are exceeded. Then the output will show evidence of the instability, but it is due only to nonlinearities of a finite word size. If there was no nonlinearity (which would require an unlimited word width), the output would remain bounded.
So yes, it is a matter of fact, not just my belief, that TIIR filters are FIR and some TIIR filters are unstable. Ergo, not every FIR filter is stable. Ergo, the assertion that FIR filters "are inherently stable", without qualification or caveat, is mistaken. 70.109.176.104 (talk) 19:36, 26 December 2012 (UTC)[reply]
Going back to the references for the moment, the additional sources that 70.109 has provided verify the existence of TIIR filters, but do not discuss their possible instability. At least not on the pages linked or their abstracts. This leaves only the Wang and Smith paper. While that does not exclude its use as a reference in Wikipedia, I don't think we should be giving any great prominence to one relatively obscure source. I am especially concerned about giving undue weight to this issue when so many book sources get along fine without it. I do, however, disagree with Kvng that TIIR filters should not be mentioned until an article is written. It is a fine idea to mention TIIR, perhaps with a redlink to encourage the article to be written.
What I don't really have a handle on here is whether the internal instability issue is a problem likely to be encountered by an incautious designer, or if it is only of theoretical interest occuring only in specially contrived cases. Perhaps someone could enlighten me, if the latter is the case then I think this deserves a footnote at most, if that. SpinningSpark 12:17, 27 December 2012 (UTC)[reply]
Hey Spark, what do you think is meant by an "Unstable One-Pole Filter Element"? 70.109.189.72 (talk) 16:28, 27 December 2012 (UTC)[reply]
Is this a test of my knowledge of filter theory? I guess the answer is this with x>1. What's your point? SpinningSpark 17:12, 27 December 2012 (UTC)[reply]
I am not sure you noticed that phrase in the title of the Walstijn & Smith reference. This refutes the objection: ...the additional sources ... provided verify the existence of TIIR filters, but do not discuss their possible instability. ... This leaves only the Wang and Smith paper. The "Unstable One-Pole Filter Element" is precisely what Eqs 3 or 4 above describe with p>1. 71.161.195.64 (talk) 22:53, 27 December 2012 (UTC)[reply]
Ok, so that is a case of an article title that is tldr, but I still don't see the point, unless you are claiming that a one-pole unstable filter is necessarily FIR. I still don't see a discussion of unstable internal states in that article; are you sure you have linked to the right article? The linked page is an article with a different title. If there is such a discussion, please give a more exact reference/quote to it. SpinningSpark 23:44, 27 December 2012 (UTC)[reply]
I fixed the bad link. You have to go to citeseer and then hit the PDF button. I can't seem to get a direct link to the pdf. Maybe this will do it.
I am stating that the one-pole Truncated IIR filter depicted as Eqs 3 or 4 above is precisely what the authors are writing about when they refer to "Unstable One-Pole Filter Elements" and it is FIR for the very reasons I have spelled out multiple times; namely that the IR is F. Listen, I am starting to question the assumption of good faith. This is appearing that, no matter what the facts are, no matter what the references are, that no matter what, your pre-conceived notion that FIR filters are inherently stable is sacrosanct. I realize that you and Kvng would like to include that inaccuracy back into the article and it is a widely held inaccurate belief, but this is contrary to the very pillars of what Wikipedia is about. You don't have to admit to anything, but can't you just allow proven, cited, and accurate knowledge be included in this encyclopedia instead of resisting it at every turn? Why should the deficit of knowledge (I am refraining from using the "I-word") that you have be propagated to the encyclopedia. When people are introduced to FIRs, they really should know that there are at least 3 or 4 ways to implement them (there may be more, but those are the only methods I am aware of). There is the straight-forward realization (what Kvng has been calling "generic"). There is fast convolution (currently in the Overlap add and Overlap save articles). And there is TIIR. All are FIR. All but TIIR are inherently stable. But not all FIRs are inherently stable. My only objection is stating that falsehood without qualification or caveat. It appears that the position that you and Kvng insist on is that this inaccuracy is put in the article with no qualification. Why do you want to do that?
I am through jumping through hoops for you. I have more than defended this and have more than satisfied all requirements of editing Wikipedia regarding this. Perhaps you guys haven't heard of TIIR filters before and realized that they're a subcategory of FIR. But encyclopedias are devices for learning things not for propagating gaps in knowledge. I think it's time to accept reality and let go of a long-held belief. If not that, at least allow the accurate facts to be published in the encyclopedia. Sheesh! 71.161.195.64 (talk) 01:16, 28 December 2012 (UTC)[reply]
Please don't have a go at me, I did not revert you and I am not preventing you contributing to the article. I have only asked for sources that classify TIIR filters in the way you say they are classified. But anyway, thanks for the new link, I can now see the Walstjin and Smith paper. I may take a closer look in the morning when I'm fresh. But one thing strikes me right away, they are not concerned with avoiding accidentally introduced instability, but rather are deliberately creating unstable filters for their application. SpinningSpark 02:16, 28 December 2012 (UTC)[reply]
Who said anything about having "a go at" anyone else? I am saying that I'm tired. I'm tired of the crap. I have shown you and everyone watching exactly how a TIIR is 1. FIR and 2. not always stable. It's proven. It's cited. It should be over. I want it to be over. I just don't want this article to say something that is false without at least some qualification. That's all.
Your observation about what these guys are using unstable TIIRs for is correct. It's deliberate. They want the phase characteristics of the "reverse" impulse response. They (at least Wang & Smith) show where this internal instability causes floating-point roundoff error to be a problem. They deal with the problem by ping-ponging and clearing out all of the states in the unstable TIIR that is not in use. 71.161.195.64 (talk) 03:14, 28 December 2012 (UTC)[reply]
I think we need a separate discussion on the issue of accumulating rounding errors. I am more interested at the moment in whether or not an ideal FIR filter can be unstable. Last night I was almost convinced that the Walstijn & Smith paper had such a filter because of the growing exponential output impulse response. This actually meets Kvng's BIBO definition of instability - although I don't really hold with that def. So can this filter even be constructed in the form of what Kvng is calling a generic FIR filter (and I would call a transversal filter)? Last night I thought it couldn't, but on reflection, of course it can. All that is needed is that the coefficients of the transversal filter "tapoffs" are set to increasing values corresponding to a growing exponential. We are all agreed, I think, that transversal filters are unconditionally stable. Thus the Walstijn & Smith filter, if constructed in transversal form, would be unconditionally stable despite having a growing exponential output. It would only continue to grow until the last delay line tap was reached and then fall instantly to zero - that's what FIR does. The actual construction used by Walstijn & Smith is different of course. They used two unstable IIRs delay summed to form a TIIR. If left to its own devices this filter would eventually break because the internal unstable IIR would exceed some limit. However, at this point it is no longer behaving as an FIR. The instability has not really come from the FIR design, but rather it has come from including an unstable IIR building block within it. SpinningSpark 12:59, 28 December 2012 (UTC)[reply]
No one said that the impulse response of a TIIR cannot also be implemented as a transversal filter. In fact, there are restrictions going the other direction, not every FIR implemented as a transversal filter can be alternately implemented as a TIIR. Only FIR filters that have taps that are geometrically or exponentially related can be implemented as a single TIIR. But if you're willing to live with that restriction (and you would be if you would choose a similar IIR to accomplish your filtering task), then a TIIR can implement a very long FIR with much less computation than would an identical transversal filter. Just as a moving average can implement the filter with much less expense than doing the same thing with the transversal structure. That's the whole point of using TIIR filters. If you want, I can give you an audio example (parametric EQ, but with linear phase). 70.109.182.120 (talk) 06:55, 29 December 2012 (UTC)[reply]
I still see an open terminology issue. When someone says "FIR filter", does he mean "any filter with a finite impulse response" or does he mean "a non-recursive filter" (Kvng's diagram)? 71.161 apparently adopts the former. My sense is the latter. If the latter definition is used, then noticing that a recursive filter can have a finite impulse response is an interesting but unintended aspect of the FIR/IIR distinction. This issue is not a math issue but rather one of definition.
If we used recursive/non-recursive terminology in the article, then we could sidestep the whole TIIR issue. I think we all agree that the Equation 1/canonical architecture is stable. Unfortunately, the common digital filter terms are IIR and FIR, and this article probably should mention them. Consequently, I'd make the recursive/non-recursive topology the dominant distinction, mention that they are labeled IIR and FIR, and put the MA IIR/TIIR comment in a footnote.
"Digital filters are classified into one of two basic forms, according to how they respond to a unit impulse whether they use feedback (recursive filter) or not (non-recursive filter)"
Even if the common usage of "FIR filter" means "any filter with a finite impulse response", MA IIR/TIIR are uncommon, so the impact to this article should be limited. 71.161 purpose is to avoid misleading statements. I mostly agree (a prof taught me that good teaching requires some lies that are patched up later), but I think statements such as "A moving average filter or CIC filter are examples of FIR filters that are normally recursive (that use feedback)" can mislead the other way. Is it a recursive filter or a summation loop optimization? Frankly, the article should be giving good examples of the filters rather than counter examples. (Other details in the paragraph, such as Parks-McClellan and Remez algorithm, are getting too far afield.)
The TIIR discussion keeps including many caveats. That level of discussion does not belong in this article.
I have some trouble with Equation 2. Although the particular solution is a finite impulse response, the homogeneous solution is not identically zero as it is in Equation 1. Initial conditions must be imposed; ICs are not part of the traditional FIR/IIR discussion.
Glrx (talk) 00:32, 29 December 2012 (UTC)[reply]
Initial state values are not an issue of discussion for either FIR or IIR filters? That seems to be a very odd thing to say. Whether it's FIR or IIR, when we bang a filter (in the digital case with a Kronecker delta) to see what comes out as an impulse response, in either the FIR or IIR case, we specify that all states are zero at the time of the discrete impulse. If they were not zero, something other than h[n] would come out. 70.109.182.120 (talk) 07:05, 29 December 2012 (UTC)[reply]
Yes, I think I pointed out a million words ago that a common textbook approach is to start from the non-recursive / recursive split. Then go on to say non-recursive are FIR, but old fashioned analog types (IIR) need recursive. A more advanced treatment will go on from that and discuss building FIR from IIR components and TIIR. I agree we need to keep it simple in an overview article, but I also agree with 71.161 that we should avoid saying anything that is actually wrong; we are not teaching here, and don't have the luxury of waiting till year three to correct the simplifications of year one. Not wishing to put words in anyone's mouth, I think Kvng's point might be that all FIR can be implemented with transversal topology and any instability arising in other topologies is not fundamentally due to it being FIR. I am not sure whether or not that is true, I suspect it is, but we should stay away from that in the article in the absence of sources. SpinningSpark 01:34, 29 December 2012 (UTC)[reply]

As someone new to this debate (but has designed FIR filters) I would sum up the discussion as follows: LouScheffer (talk) 19:20, 29 December 2012 (UTC)[reply]

  • Mathematically, FIR filters can be described (equivalently) as a convolution over input samples, or a polynomial in z-1. In either case they have zeros but no poles, are unconditionally stable, BIBO, etc.
  • It is always possible to implement an FIR filter as a weighted sum of input signals, with no feedback. This particular implementation has some very nice properties: it is unconditionally stable, has no limit cycles, can easily be scaled so it never overflows, is guaranteed to be BIBO, is insensitive to rounding errors, etc.
  • FIR filters can also be implemented with internal states and recursion, but in this case the nice properties are not guaranteed - it may have limit cycles, have non bounded internal variables even for bounded input, may suffer from unlimited propagation of overflow or rounding errors, etc. On the other hand, it may also be perfectly well behaved - for example a straightforward implementation of a moving average filter over integer samples. More analysis is required to see if desirable properties hold.
Good summary and all your points are quite relevant to the Filter design topic. Can we use this summary to improve the article? -—Kvng 20:45, 29 December 2012 (UTC)[reply]
It's false that FIR filters have no poles. Even those FIRs that aren't TIIR have poles; they're all at z=0. 70.109.182.120 (talk) 00:32, 30 December 2012 (UTC)[reply]
You are certainly correct that the transfer function has its poles at z=0. They are normally ignored since they contribute no amplitude variation (they are equidistant from the unit circle) and at most linear phase. You could say instead "they can have zeros anywhere in the Z plane but all poles are at z=0". LouScheffer (talk) 05:09, 31 December 2012 (UTC)[reply]
Yes that would be more accurate. As least for the "conventional" or "generic" or "transversal" FIR filter. Again, since you're just joining the discussion, there are these things we call Truncated IIR filters (TIIR), where there can be a pole not at z=0, but it would have to be canceled by a zero at the same location for it to be TIIR (I just remembered taking a grad school course in digital controls and these were also called "dead-beat systems") and then FIR. 70.109.182.120 (talk) 06:44, 31 December 2012 (UTC)[reply]

Filter order vs number of coefficients

[edit]

> "For example, the order of a filter is more or less proportional to the number of operations. This means that by choosing a low order filter, the computation time can be reduced."

That's not really true and there's no source for it in the article. A comb filter, for example, may only require a single operation but have a very high order (in the thousands). This is because all the other coefficients are zero. This is the sort of thing that keeps making people believe that the number of coefficients is the order of the filter, but then people don't count the zero coefficients because they're not typically written down.

long_march (talk) 15:40, 8 May 2020 (UTC)[reply]

Digital filter design

[edit]

This article is about the process of designing a signal processing filter. Should the article be renamed Digital filter design? There is some discussion of analog filter design in Analogue filter. There is not so much here. ~Kvng (talk) 15:04, 28 January 2021 (UTC)[reply]

I think the correct thing to do is to expand it, or at least template it as needing expansion in the analog section. I don't agree that the majority of the article is about digital filters. The majority is a general discussion without reference to implementation. SpinningSpark 15:32, 30 July 2021 (UTC)[reply]