# Can I optimize band-pass FFT filter with skipping values instead of zeroing them when decimating?

I currently use very simple band-pass filter: FFT->Keeping needed, zeroing not needed->iFFT->decimation with skipping

This works perfectly for my needs (I apply envelope after filter so no problem with slight deformation of real signal) but can I optimize it with decimation in the middle?
For example, I have pack of 4096 samples for my 1kHz signal, and I want to keep 0.5..2Hz range:

1. I FFT 4096 samples and get 4096 complex with resolution of 1000/4096/2 ~ 0.5Hz
2. I zero first sample, keep 3 samples, zero all other samples
3. iFFT 4096 samples, getting 4096 samples
4. I take 4 samples (with indices 0, 1000, 2000, 3000, 4000)
5. Envelope them with simple detector

Result is totally fine for my needs, but when I need 100 frequency zones I have to iFFT 4096 complex 100 times - can I somehow reduce sampling rate not in step 4 but in step 2 to save processing time and ram with cheaper/faster iFFT?
I tried iFFT on reduced to 4 complex samples array but result was total failure

• What 100 frequency zones do you need? Jun 22, 2021 at 23:51

Zeroing bins as a method of filtering is not recommended unless only those distinct frequencies need to be rejected. This is the frequency sampling approach to filter design and results in very large errors for any frequencies that may exist in between those bins that were zeroed compared to optimized methods for filter design.

If there is any interest in "optimizing" and being faster/cheaper then consider other filter design approaches which are just as simple and provide much better performance for a given number of coefficients. My favored approach is to use the least squares algorithm (firls in Matlab/Octave and Python scipy.signal) for optimum filter design (in the least squared sense) or if there is any concern with peak error instead of best overall rms error, then consider the Parks-Mclellan (firpm in Octave and Python scipy.signal) for optimum design in the peak error sense.

If computational cheapness is needed for determining the filter coefficients themselves, then consider using a Kaiser window for the window design method of filter design. For a comparison on these approaches please see: FIR Filter Design: Window vs Parks McClellan and Least Squares

Not zeroing bins is further detailed in:

Why is it a bad idea to filter by zeroing out FFT bins?

For a .5 Hz to 2 Hz bandpass filter with a signal sampled at 1 KHz sampling rate, my suggestion for optimized performance is to decimate to from 1 KHz to 10 Hz and then use a least square filter for the bandpass. The length of the filter is driven by the fractional transition band between the bandpass frequencies and bandstop frequencies. With a ratio of 10 Hz sampling this should be fairly wide resulting in a highly efficient structure overall with less processing than even one of the FFTs.

As a quick example of the dramatic efficiency difference (and I suspect that a series of 6 half-band filters for decimating from 1 KHz to doing the final selection filter at 15.575 Hz, or even a CIC filter with a 3 tap droop compensator would be even more efficient than this, but this was quick to do and demonstrates the dramatic efficiency improvement over a 4096 FFT and IFFT operation) I propose the following as shown below. The OP's FFT processing could still be done if desired instead of the shaping filter with a considerable improvement in efficiency: Each filter is a linear phase filter and therefore requires half the multipliers for the given number of taps. The above will provide over 55 dB of rejection from 2.3 Hz to 1 KHz, and from DC to 0.2 Hz with the desired passband of 0.5 Hz to 2 Hz, and only requires $$31+31+51 = 113$$ total multipliers!

Even better performance can be achieved if desired with a modest increase in multipliers. For 4096 input samples there will be 409 output samples at the 10 Hz rate after the overall decimation by 100 with the filter delay of 51 samples (so ~350 samples will represent the settled desired output).

This is compared to $$2N \log_2( N) = 2(4096)12 = 98,304$$ multipliers for one radix-2 FFT (and two are required in the OP's initial approach!). Another approach for the IDFT computation of a small number of samples as the OP desires is the the Goertzel algorithm but even that would take $$2N+4$$ multipliers per output sample so for the five output samples desired by the OP would require $$40,980$$ multipliers.

If an FFT is desired instead of the shaping filter and continuing with the OP's initial strategy, then this would still require approximately 3,550 multipliers for each FFT.

The optimized filter designs using multiband decimation filters are shown below for the 10:1 filter (100 Hz to 10 Hz is shown, but the 1KHz to 100 Hz would be the identical filter). Note that rejection is concentrated to be only at the alias frequency locations that matter (rejection is maximized at the locations that would alias to the desired 0.5 to 2 Hz band): And the final shaping filter with the given number of taps used has the following frequency response: This has room for further optimization but shows quickly what can be done with proper decimation and filtering approaches rather than filtering through the frequency sampling method of zeroing FFT bins. The same decimation operations could have been done and then FFT's performed on the 10 Hz signal which would also have provided a dramatic improvement; reducing 98,304 multipliers to 3550 for each of the two FFT operations, but the FIR approach was shown to provide what would be better performance with only 113 total multipliers! For filtering applications the least squares is an optimized algorithm that significantly outperforms FFT sampling approaches (except for the cases when we truly only care about the frequencies that are on the FFT bin centers).

If there is a need for multiple different bands each with similar bandwidth but at a different similar frequency, then polyphase filter approaches combined with IFFT blocks can make for very efficient channelizer topologies. For more details on that see this write-up from fred harris titled "Filter Banks for Software Defined Radios":

https://s3.amazonaws.com/embeddedrelated/user/124841/fbmc_book_ch_6_text_5_61615.pdf

• Thanks! I understand downsides of zeroing, but envelope filter and adaptive gain works like a charm fixing most of them (I don't need to keep signal form, just looking for pikes in time-domain). I compared results with Chebyshev and Butterworth filters and they seem 90-95% identical on real signal. FFT also has a nice benefit of good semi-hardware accelerated realization in CMSIS, that makes it fast enough, just looking for optimization ways :-) Jun 22, 2021 at 19:18
• I wouldn't recommend Chebyshev and Butterworth filters for digital design either (that was in the 60's before they came up with optimum filter design directly in digital rather than mapping from the analog). So if you want optimized ways, please look closer at my suggestions and then see if you can do better. Avoid all that extra processing with envelope filters and adaptive gain! This is all worked out for you already and simple to use/ implement. Jun 22, 2021 at 19:26