# Why are recursives methods useful for FIR filter design?

As I understand it, FIR filtering is a linear process. That mean for me that the whole filtering process will have a fully predictable behavior. So, could someone explain why a universal deterministic and optimal filter design method to obtain the desired response doesn't exist and why recursive approach seems to be of great interest in practice ?

EDIT: just to clarify, my question is about an "optimal" method, that is one which compute the shortest filter response while staying the closest to the design criteria.

Sure, FIR filters are "simple" linear objects. But a typical FIR filter design task looks like this:

Find a set of numbers (the filter coefficients) such that the magnitude of their Discrete Fourier Transform is as close as possible to a target response. "As close as possible" being defined as "by minimizing the $L_\infty$ norm of the difference between ideal and actual response over some frequency ranges".

This is a non-linear, sometimes non-convex optimization problem and there is no universal, trivial procedure to solve those.

We have to use procedures like the Parks-McClellan algorithm because the real-world engineering constraints we want to impose when designing FIR filters do not translate into simple linear or quadratic constraints. For example, a least-square error criterion (L2 norm often leads to more tractable procedures than other norms...) would not be an acceptable choice for engineering applications, because it could allow solutions that are close to the required response on average, but with an outlier value.

• Thanks ! greggo's answer below is also a nice complement to yours ! – user9020 Jul 4 '14 at 22:05
• Just to avoid confusion: the Parks-McClellan algorithm minimizes the $L_{\infty}$-norm, not the $L_0$-norm. – Matt L. Jul 5 '14 at 9:17
• Oops, you're right, fixed! – pichenettes Jul 5 '14 at 11:12
• Well, you can formulate do FIR filter design using linear programming, although you need to grid the specification ranges leaving a bit uncertainty. Also, there are clearly engineering applications where $L_2$ criteria are used, e.g., minimizing the energy, which in many cases (e.g., following standards) are much more relevant than $L_\infty$. Still, I guess your main points are correct. – Oscar Jul 7 '14 at 8:59

The question seems a bit vague - there are plenty of other situations where the system (or its model) is considered to be completely deterministic, but you have tradeoffs, or a complex 'quality metric' which makes good design a challenge.

One observation that may help: The frequency response of an FIR filter is continuous in all of its derivatives (since it can be written as a sum of continuous functions via fourier transform). So, if the filter's response is completely (mathematically) flat for any finite part (however small) of the spectrum, then it must be completely flat throughout the spectrum, and is therefore not very useful.

So, you clearly can't have an FIR filter with a perfect passband or stopband. You can get very close with a large enough filter, though. Designing the filter is a tradeoff amongst all the imperfect, feasible filters; balancing whatever design criteria you have (this applies equally to IIR filters).

• Interesting mathematical perspective ! I never thought of the mathematical infeasibility of a signal with a (borned) flat spectral part. – user9020 Jul 4 '14 at 21:40

IIR filters are also linear (and time-invariant). what that means is that the mapping from input samples $x[n]$ to output samples $y[n]$ satisfies the superposition (and time-shifting) properties:

if $$y[n] \triangleq \mbox{LTI} \{ x[n] \}$$

then $$y_1[n] + y_2[n] = \mbox{LTI} \{ x_1[n] + x_2[n] \}$$

and $$y[n-D] = \mbox{LTI} \{ x[n-D] \}$$

and, as a result, the convolution summation:

$$y[n] = \mbox{LTI} \{ x[n] \} = \sum_{k=-\infty}^{+\infty} h[k] x[n-k]$$

for some impulse response $h[n]$ (which are the coefficients for the FIR) that is dependent only on the filter, not the input. that's what linear and time-invariant means.

but in both cases, FIR or IIR, the mapping of the specifications of the filter to those coefficients $h[n]$ is the "filter design" process. why would that be linear? there is no reason for that.

so, perhaps one method might be you make a guess at what the coefficients are, see what you get regarding the coefficients, and then somehow tweek or adjust your guess to be a better guess in the next recursion. now algorithms like the Parks-McClellan (based on the Remez exchange algorithm) are more complicated than "guess and tweek", but that is what they are doing.

you can get very good results with the "windowing method" (if you use a good window function, like the Kaiser) and that is not recursive.

• "why would that be linear? there is no reason for that" That is – user9020 Jul 4 '14 at 21:10
• Sorry my comment got cut... That is precisely the meaning of my question (especially the "optimal" part since deterministics methods does exists) – user9020 Jul 4 '14 at 21:43
• well, you imply a premise that appears to be that "the FIR is linear" which leads to "predictable behavior" which means that the mapping of the specifications of the filter to the coefficients would be what? linear? predictable? i might say the latter since the windowing method is essentially that the coefficients are the inverse DFT of the specified spectrum. then we get into windowing because doing the inverse DFT to get $h[n]$ inherently requires a window, at least a rectangular window. using a good window can make for a pretty good non-recursive design, nothing says it's optimal. – robert bristow-johnson Jul 5 '14 at 4:33