20
$\begingroup$

I am looking to design a set of FIR filters to implement a low pass filter. I am also trying to reduce the latency of the signal through the filter so I am wondering what the minimum number of taps I can use might be.

I know that more taps can lead to a sharper cutoff of the frequency and better stop band rejection etc. However what I'm interested in is more fundamental - if I want to implement a low pass filter with cutoff at $\frac{f_s}{100}$ say does that mean that I need at least 100 taps in order to attenuate the lower frequency signals? Or can I get away with less taps and if so is there some theoretical lower limit?

$\endgroup$
23
$\begingroup$

Citing Bellanger's classic Digital Processing of Signals – Theory and Practice, the point is not where your cut-off frequency is, but how much attenuation you need, how much ripple in the signal you want to preserve you can tolerate and, most importantly, how narrow your transition from pass- to stopband (transition width) needs to be.

I assume you want a linear phase filter (though you specify minimum latency, I don't think a minimum phase filter is a good idea, in general, unless you know damn well what you're going to be doing with your signal afterwards). In that case, the filter order (which is the number of taps) is

$$N\approx \frac 23 \log_{10} \left[\frac1{10 \delta_1\delta_2}\right]\,\frac{f_s}{\Delta f}$$

with

$$\begin{align} f_s &\text{ the sampling rate}\\ \Delta f& \text{ the transition width,}\\ & \text{ ie. the difference between end of pass band and start of stop band}\\ \delta_1 &\text{ the ripple in passband,}\\ &\text{ ie. "how much of the original amplitude can you afford to vary"}\\ \delta_2 &\text{ the suppresion in the stop band}. \end{align}$$

Let's plug in some numbers! You specified a cut-off frequency of $\frac{f_s}{100}$, so I'll just go ahead and claim your transition width will not be more than half of that, so $\Delta f=\frac{f_s}{200}$.

Coming from SDR / RF technology, 60 dB of suppression is typically fully sufficient – hardware, without crazy costs, won't be better at keeping unwanted signals out of your input, so meh, let's not waste CPU on having a fantastic filter that's better than what your hardware can do. Hence, $\delta_2 = -60\text{ dB} = 10^{-3}$.

Let's say you can live with a amplitude variation of 0.1% in the passband (if you can live with more, also consider making the suppression requirement less strict). That's $\delta_1 = 10^{-4}$.

So, plugging this in:

$$\begin{align} N_\text{Tommy's filter} &\approx \frac 23 \log_{10} \left[\frac1{10 \delta_1\delta_2}\right]\,\frac{f_s}{\Delta f}\\ &= \frac 23 \log_{10} \left[\frac1{10 \cdot 10^{-4}\cdot10^{-3}}\right]\,\frac{f_s}{\frac{f_s}{200}}\\ &= \frac 23 \log_{10} \left[\frac1{10 \cdot 10^{-7}}\right]\,200\\ &= \frac 23 \log_{10} \left[\frac1{10^{-6}}\right]\,200\\ &= \frac 23 \left(\log_{10} 10^6\right) \,200\\ &= \frac 23 \cdot 6 \cdot 200\\ &= 800\text{ .} \end{align}$$

So with your 200 taps, you're far off, iff you use an extremely narrow pass band in your filter like I assumed you would.

Note that this doesn't have to be a problem – first of all, a 800-taps filter is scary, but frankly, only at first sight:

  • As I tested in this answer over at StackOverflow: CPU's nowadays are fast, if you use someone's CPU-optimized FIR implementation. For example, I used GNU Radio's FFT-FIR implementation with exactly the filter specification outline above. I got a performance of 141 million samples per second – that might or might not be enough for you. So here's our question-specific test case (which took me seconds to produce): GNU Radio based FFT FIR filteringrate results: rate_avg = 1.40982e+08
  • Decimation: If you are only going to keep a fraction of the input bandwidth, the output of your filter will be drastically oversampled. Introducing a decimation of $M$ means that your filter doesn't give you every output sample, but every $M$th one only – which normally would lead to lots and lots of aliasing, but since you're eradicating all signal that could alias, you can savely do so. Clever filter implementations (polyphase decimators) can reduce the computational effort by M, this way. In your case, you could easily decimate by $M=50$, and then, your computer would only have to calculate $\frac{1200}{50}= 24$ multiplications/accumulations per input sample – much much easier. The filters in GNU Radio generally do have that capability. And this way, even out of the FFT FIR (which doesn't lend itself very well to a polyphasing decimator implementation), I can squeeze another factor of 2 in performance. Can't do much more. That's pretty close to RAM bandwidth, in my experience, on my system. For
  • Latency: Don't care about it. Really, don't, unless you need to. You're doing this with typical audio sampling rates? Remember, $96\,\frac{\text{kS}}{\text{s}}\overset{\text{ridiculously}}{\ll}141\,\frac{\text{MS}}{\text{s}}$ mentioned above. So the time spent computing the filter output will only be relevant for MS/s live signal streaming. For DSP with offline data: well, add a delay to whatever signal you have in parallel to your filter to compensate. (If your filter is linear phase, it's delay will be half the filter length.) This might be relevant in a hardware implementation of the FIR filter.
  • Hardware implementation: So maybe your PC's or embedded device's CPU and OS really don't allow you to fulfill your latency constraints, and so you're looking into FPGA-implemented FIRs. The first thing you'll notice is that for hardware, there's different design paradigma – a "I suppress everything but $\frac1{100}$ of my input rate" filter needs a large bit width for the fixed point numbers you'd handle in Hardware (as oppposed to the floating point numbers on a CPU). So that's the first reason why you'd typically split that filter into multiple, cascaded, smaller, decimating FIR filters. Another reason is that you can, with every cascade "step", let your multipliers (typically, "DSP slices") run at a lower rate, and hence, multiplex them (number of DSP slices is usually very limited), using one multiplier for multiple taps. Yet another reason is that especially half-band filters, i.e. lowpasses that suppress half the input band and deliver half the input rate, are very efficiently implementable in hardware (as they have half the taps being zero, something that is hard to exploit in a CPU/SIMD implementation).
$\endgroup$
  • 3
    $\begingroup$ Lake DSP were doing 256,000 tap FIR filters in real time in the mid to early 1990s. 1200 taps? Phfffft! ;-) $\endgroup$ – Peter K. May 28 '16 at 4:55
  • 2
    $\begingroup$ @PeterK. That's the spirit! Deep respect for that 256kT FIR – the numerical accuracy they've built that with must have been as breathtaking as the sheer size of the design. Being too young to technologically enjoy them myself, the early 90s must have been an interesting time. Talked to an engineer a while back that did DFT ICs back in those days; the need for application-specific DSP ASICs just seemed to be high as people realized what was possible DSP-wise with computing platforms to actually handle the resulting streams of data, but no "multi-purpose" accellerators around (unlike today). $\endgroup$ – Marcus Müller May 28 '16 at 7:19
  • $\begingroup$ @PeterK., yeah but them aussies are always pulling our leg. $\endgroup$ – robert bristow-johnson Jun 1 '16 at 4:03
  • $\begingroup$ @robertbristow-johnson oy matey, what an insider joke is going on here :D ? $\endgroup$ – Marcus Müller Jun 1 '16 at 10:35
  • 2
    $\begingroup$ @MarcusMüller, although there appeared to be an increased popularity of ASICs back then compared to now (and i think it's because everyone that was an ASIC spec/designer then now just uses FPGAs) there were "multi-purpose" DSPs back in the early 90s. that LakeDSP thingie was made outa 6 DSP56001. $\endgroup$ – robert bristow-johnson Jun 1 '16 at 17:27
13
$\begingroup$

For a quick and very practical estimate, I like fred harris' rule-of-thumb:

$$ N_{taps} = \frac{Atten}{22*B_T}$$

where:

Atten is the desired attenuation in dB,

$B_T$ is the normalized transition band $B_T=\frac{F_{stop}- F_{pass}}{F_s}$,

$F_{stop}$ and $F_{pass}$ are the stop band and pass band frequencies in Hz and

$F_s$ is the sampling frequency in Hz.

This comes out very close to what you would get for a linear phase filter with a passband ripple of 0.1 dB. I use this rule of thumb often to get a first cut idea of the number of taps needed, and then modify through iteration in the filter design process.

Also to note: this rule-of-thumb provides great insight into what really drives the number of taps: stop band attenuation and the steepness of the transition band (and passband ripple, but typically- at least for filters I have had to design for wireless comm applications - the attenuation requirement would dominate over ripple). So your question in stating a cutoff at Fs/100 is missing how quickly you need to transition to a stop band.

Example: 60 dB attenuation, $F_s$=100KHz, $F_{pass}$ = 1KHz, $F_{stop}$=3KHz

$N_{taps} = \frac{60}{22*2/100}=137$ taps (rounding up)

Playing around with these numbers can also demonstrate the significance in processing reduction by using decimation approaches.

$\endgroup$
6
$\begingroup$

Adding to the accepted answer, a few additional references. I won't write the formulas which can be involved. Those formulae mostly yield rule-of-thumbs or approximations to start from. You can fiddle around these numbers for your actual design.

One of the origin for Bellanger's design is: On computational complexity in digital filters, 1981, Proc. Eur. Conf. Circuit Theory Design, M. Bellanger. It is quite difficult to obtain, but it is doable. Interestingly, it also specify formulae to evaluate the number of bits per coefficient, which should be considered in finite-arithmetic implementation. A more accessible version in French is: Evaluation de la complexité des filtres numériques, 1982.

Several other formulae are gathered in Finite impulse response filter design, Handbook for digital signal processing, 1993, T. Samamaki.

More recently, you can read Accurate estimation of minimum filter length for optimum FIR digital filters, 2000, K. Ichige et al.

Last, the paper Efficient design of FIR filters with minimum filter orders using l0-norm optimization, 2014 claims a design where the order is gradually decreased.

$\endgroup$
4
$\begingroup$

I don't think there really is some definitive minimum number of taps. It it pretty common to generate FIR filters by convex optimization, e.g. $$ \text{minimize} \ \text{max}\left(\left| H(\omega) \right|\right) \text{for all } \omega \text{ in the stopband} $$ $$ \text{subject to} \frac{1}{\delta} \leq \left| H(\omega) \right| \leq \delta \text{ for all } \omega \text{ in the passband} $$

The main practical problems I can think of would be the number of frequency samples used when doing the optimization, as inter-frequency sample behavior can cause undesired effects. How good the fit can become, depends of course on the number of taps. I guess you could say that the minimum number of taps is when the problem becomes infeasible. So one solution would be to solve the feasibility problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.