20

I'm quite a novice in signal processing and I know this question may be too broad. But I would still like to hear hints from experts.

I was taught to use butter (to design Butterworth filter aka the maximally flat magnitude filter) and filtfilt (Zero-phase digital filtering) functions for bandpass filtering of EEG (electroencephalogram) signals in MATLAB offline (i.e. after the completion of recording). This way you can avoid inevitable "delay" caused by the digital filter (i.e. zero phase filtering).

Then, someone asked me why we cannot use fft (Fast Fourier transform) to get the frequency-domain representation of the signal, and then set the power of unwanted frequencies to zero, followed by ifft (Inverse fast Fourier transform) to recover the filtered data in the time domain for the same purpose. This manipulation in frequency domain sounded simpler and reasonable to me, and I couldn't really answer why.

What are the advantages and disadvantages of using the simple fft/ifft method for bandpass filtering? Why do people prefer to use FIR or IIR digital filters?

For example, is the fft/ifft method more prone to spectral leakage or ripples compared to the established digital filters? Does the method also suffer from phase delay? Is there a way to visualize the impulse response for this filtering method for comparison?

auspicious99
  • 326
  • 5
  • 17
Kouichi C. Nakamura
  • 323
  • 1
  • 2
  • 8
  • Related (but not necessarily duplicate) question: http://electronics.stackexchange.com/questions/100348/why-use-a-filter/100351#100351 – helloworld922 May 10 '14 at 00:29
  • Using an FFT to filter a signal is absolutely valid, but there are a few things to look out for. See this similar question/answer for more info: http://stackoverflow.com/a/2949227/565542 – sbell May 10 '14 at 00:57
  • 6
    Questions like this might be more appropriate for the [Signal Processing](http://dsp.stackexchange.com) site. – Jason R May 10 '14 at 13:00
  • 2
    I think that [The Scientist and Engineer's Guide to Digital Signal Processing By Steven W. Smith](http://www.dspguide.com/) has an answer. I think that he says that sample in - sample out is much more efficient with a digital filter. But, there is a minimal width of the window (64 samples or more, I do not remember exactly) when it is more appropriate to involeve the FFT conversion where you can have a brick filter in the freq domain. Efficiency is not the only issue. The brick filter implies that you need to use samples from the future, which is impossible in real time. – Val May 10 '14 at 15:18
  • Thanks, I was looking for something like the Signal Processing site, but couldn't find it. – Kouichi C. Nakamura May 10 '14 at 20:52

3 Answers3

15

The main reason that frequency-domain processing isn't done directly is the latency involved. In order to do, say, an FFT on a signal, you have to first record the entire time-domain signal, beginning to end, before you can convert it to frequency domain. Then you can do your processing, convert it back to time domain and play the result. Even if the two conversions and the signal processing in the middle are effectively instantaneous, you don't get the first result sample until the last input sample has been recorded. But you can get "ideal" frequency-domain results if you're willing to put up with this. For example, a 3-minute song recorded at 44100 samples/second would require you to do 8 million point transforms, but that's not a big deal on a modern CPU.

You might be tempted to break the time-domain signal into smaller, fixed-size blocks of data and process them individually, reducing the latency to the length of a block. However, this doesn't work because of "edge effects" — the samples at either end of a given block won't line up properly with the corresponding samples of the adjacent blocks, creating objectionable artifacts in the results.

This happens because of assumptions that are implicit in the process that converts between time domain and frequency domain (and vice-versa). For example, the FFT and IFFT "assume" that the data is cyclic; in other words, that blocks of identical time-domain data come before and after the block being processed. Since this is in general not true, you get the artifacts.

Time-domain processing may have its issues, but the fact that you can control the latency and it doesn't produce periodic artifacts make it a clear winner in most real-time signal-processing applications.

(This is an expanded version of my previous answer.)

Community
  • 1
Dave Tweed
  • 168,369
  • 17
  • 228
  • 393
  • 1
    Thanks a lot for the detailed answer in plain words. Now I can see that in my question I should have mentioned that my job is mainly for offline analysis rather than online or real-time processing. I'll edit the question. Your point is quite clear: Because FFT requires the whole duration of data, you've got wait until recording has done. – Kouichi C. Nakamura May 10 '14 at 03:06
  • 1
    OK, fair enough. Let me just point out one more thing about frequency-domain filtering that may or may not be an issue for you: The filters will not be *causal* in the time domain. In other words, their impulse responses extend into both positive and negative time. This can have some surprising effects if you're not aware of it. – Dave Tweed May 10 '14 at 04:19
  • Thanks. I looked up "Causal filter" on Wikipedia. By definition, the FFT boxcar doesn't care about time, so I can see it is non-causal. That nature does explain why you can't use it for real time filtering. – Kouichi C. Nakamura May 10 '14 at 08:20
  • 3
    @DaveTweed: Your assertion about requiring an 8-million-point FFT in order to filter a 3-minute song sampled at 44.1 kHz is incorrect. FFT-based convolution algorithms are in fact heavily used in practice. Methods such as [overlap-save](http://en.wikipedia.org/wiki/Overlap%E2%80%93save_method) and [overlap-add](http://en.wikipedia.org/wiki/Overlap%E2%80%93add_method) are used so that more modest FFT sizes (and therefore processing latency) are required. These techniques do exactly what your second paragraph suggests: use smaller blocks while handling the "edge effects" that occur between them. – Jason R May 10 '14 at 13:01
  • @JasonR: I'm aware of those methods, and they don't make my assertion incorrect. They represent a compromise between time-domain and frequency-domain processing, and while they can minimize the edge effects, they cannot eliminate them altogether. The OP and I are discussing *pure* frequency-domain techniques in a more theoretical sense. – Dave Tweed May 10 '14 at 13:59
  • 2
    @DaveTweed: I disagree. Fast convolution methods like overlap-save and overlap-add are equivalent (up to numerical precision) to direct linear convolution (i.e. implementing the filter in the time domain). There is no performance compromise in boundary conditions of any kind versus time-domain processing, and their bounded latency still makes them useful for many real-time applications. I maintain that the assertion that frequency-domain filtering requires one big FFT across the entire input signal is untrue, and I'm not sure what you mean by "pure" frequency-domain processing in this context. – Jason R May 10 '14 at 15:01
2

You certainly can use "boxcar" ideal filters in the frequency domain. Duality says this is equivalent to convolving with a sinc function of infinite length. To reduce artifacts associated with making the length finite, the sinc function is often multiplied by a window. You may have heard of Hamming, Hanning (actually von Hann), raised cosine, and other windowing techniques. The convolution may be computationally simpler than the fft/ifft aproach, but the answers are the same.

Every method will have plusses and minuses. The Butterworth is IIR, and the boxcars are FIR. The Butterworths are probably flatter in the pass band, but probably with less steep rolloff, depending on order of the IIR and width of the FIR. filtfilt would be harder to implement in real time.

Scott Seidman
  • 29,274
  • 4
  • 44
  • 109
  • 1
    For a really clear explanation of windowing and block filtering, look at the book, *Digital Filters* by R. W. Hamming. Available from Dover, so very nicely priced. (Incidentally, Scott, I think this is the Hamming the window is named for and von Hann is the one who got his name butchered in naming his window) – The Photon May 10 '14 at 04:39
  • Also, I'm pretty sure a boxcar implemented with FFTs is, by definition, perfectly flat in the pass band. When we say the Butterworth filter is "maximally flat" I believe we're talking about it in the context of causal filters only (and Wiki says that even so it's possible to make an inverse Chebychev filter that is more flat than a Butterworth). – The Photon May 10 '14 at 04:44
  • 1
    Agreed for ideal infinite length,but not so sure after truncation and windowing – Scott Seidman May 10 '14 at 11:13
  • @ThePhoton Thanks for the Hamming/von Hann correction. Couldn't quite visualize my bookshelf correctly from home. – Scott Seidman May 10 '14 at 11:15
  • @The Photon; Thanks for Hamming's _Digital Filters_ book. I looked at it and it seemed written especially for elementary learners. I bought it with a hope. :) – Kouichi C. Nakamura May 10 '14 at 20:59
1

Related questions

Why is it a bad idea to filter by zeroing out FFT bins? https://dsp.stackexchange.com/questions/6220/why-is-it-a-bad-idea-to-filter-by-zeroing-out-fft-bins

Removing values from FFT result same as filtering? https://dsp.stackexchange.com/questions/11487/removing-values-from-fft-result-same-as-filtering?noredirect=1&lq=1

Why do we use window in time domain rather than do FFT modify the spectrum and than inverse FFT https://dsp.stackexchange.com/questions/8911/why-do-we-use-window-in-time-domain-rather-than-do-fft-modify-the-spectrum-and-t?noredirect=1&lq=1

Kouichi C. Nakamura
  • 323
  • 1
  • 2
  • 8