reasons why digital LP filter can't be done with FFT / IFFT

Question

reasons why digital LP filter can't be done with FFT / IFFT

electricpete (Electrical)

(OP)

27 Jan 08 03:10

Any textbook on digital filtering has a rich variety of ways to design a digital LP filter (or HP or BP).

I remember a long time ago in school wondering why we couldn't just take the FFT, set the undesired frequency bins to 0, and then take the inverse FFT (let's call it FFT/set-to-0/IFFT).  I remember asking the prof that and he gave me a number of good reasons that wasn't a good idea, but I can't remember them all.

The only one I can really remember is that a sharp cutoff in the frequency domain (resulting from FFT/set-to-0/IFFT)consititues multiplying by square wave in the frequency domain and therefore convolution by sinc function in the time domain.  And that convoluion gives you undesirable ripples in the time domain.

I am not sure exactly what kind of undesirable ripples those are, but I have tended to associate them with the Gibb's effect ripple that occurs when you truncate the fourier series for a square wave.

That explanation made me happy until recently I started playing around with actually filtering a square wave using an adjustable Kaiser filter.  It seems to me that the overshoot at the corner of the square wave is the same magnitude whether I use an extremely sharp cutoff or an extremely gradual cutoff (although the other ripples reduced as a made the cutoff more gradual).  Can that be right?    And if we are stuck with the same overshoot either way, why not just use the sharp cutoff associated with FFT/set-to-zero/IFFT?  Or are the other smaller adjacent ripples more important than that overshoot?

Any other good explanations what is wrong with the simplistic approach:  FFT / set-to-zero / IFFT ?

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

Skogsgurra (Electrical) · Answer 1 · 2008-01-27 05:22:19

A very simplistic approach could be this:

A square wave has a "body" (the not so interesting parts in the middle, that makes up most of its energy). This body is mostly low-frequency components, but its "flatness" is a result of higher order harmonics interacting to make it a smooth straight line.

By setting high-frequency components to zero, this smoothing isn't there any more - and you get the ripple.

Setting all bins, except fundamental, to zero will produce a pure sine. All but 1st and 3rd produces a rather distorted sine. And so on.

A simple first order LP filter doesn't do that. It reduces the higher order components gradually (a=1/n) and thus keeps the wave-form smooth and without any ripple.

I guess that an approach where you do not set the bins to zero, but to a value dependent on their order (n, that is) would produce an acceptable LP filter. And that is perhaps also how some filters are designed?

One problem with FFT is that it doesn't conserve phase information. So, when you do the IFFT, you may get something that isn't at all what you expected.

Gunnar Englund
www.gke.org
--------------------------------------
100 % recycled posting: Electrons, ideas, finger-tips have been used over and over again...

logbook (Electrical) · Answer 2 · 2008-01-27 07:16:05

>One problem with FFT is that it doesn't conserve phase information. So, when you do the IFFT, you may get something that isn't at all what you expected.
NOT TRUE! If you retain the complex data (rather than just the magnitude) you can do an FFT/IFFT and get exactly the same response.

I have used an FFT, removed a repeating interference pattern by nulling those bins, then IFFT'd very successfully as an image processing technique to remove systematic noise. The only difficulty was the speed. It took several hundred milliseconds to do the required FFT/iFFT pairs.

Skogsgurra (Electrical) · Answer 3 · 2008-01-27 08:50:55

Yes, of course. Didn't think of that. Haven't used FFT like that for many years. Just magnitude.

Gunnar Englund
www.gke.org
--------------------------------------
100 % recycled posting: Electrons, ideas, finger-tips have been used over and over again...

electricpete (Electrical) · Answer 4 · 2008-01-27 11:09:09

"I guess that an approach where you do not set the bins to zero, but to a value dependent on their order (n, that is) would produce an acceptable LP filter. And that is perhaps also how some filters are designed?"

That is similar to the simplistic FFT/set-to-zero/IFFT and would make some sense to me but is not practiced as far as I can tell (and I'm sure there's a good reason). Actually, all of the digital filtering in the textbooks is done in the time domain. FIR convolution with a digital filter or IIR recursive relationship.

logbook mentioned time, I can see there is a time advantage for many of the time-domain digital filters. Also they are of course well suited for processing a continuouns stream where the FFT has to break it into chunks.

I imagine if I wanted to recover the continuous stream, the effects of windowing might be relevant... could be difficult to reverse that process.

I was not thinking of continuos processing. Just a one-time processing of a batch of data. In particular, the high-pass prefilter prior to demodulation used in vibration monitoring looking for bearing defects etc (for example peakvue, spike energy etc)

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

sreid (Electrical) · Answer 5 · 2008-01-27 12:25:48

FFT IFFT is used. See DSP Guide Chapter 18.

http://www.dspguide.com/ch18.htm

IRstuff (Aerospace) · Answer 6 · 2008-01-27 15:17:31

As a post process, it's different than trying to do in real time. Most books are geared toward real-time processing, because that's usually the challenge and the requirement. Whatever approach you come up with in post processing cannot be used in real-time, because real-time requires usage of sampling windows, to keep the FFT well-behaved. Additionally, you cannot make use of "future" knowledge, i.e., the data that hasn't arrived yet to do your filtering. This automatically creates a limitation on your ability to do frequency domain operations.

TTFN

FAQ731-376: Eng-Tips.com Forum Policies

electricpete (Electrical) · Answer 7 · 2008-01-27 21:11:10

sreid - what you're pointing out I believe is that a given FIR digital filter (originally developed as a time-domain sequence h[n]) can be implemented either by time domain convolution (y[n]=h[n]**x[n])  or by FFT / multiplication / IFFT (Y(w) = H(w) X (w).  And of course you get the exact same answer either way.

You are exactly correct.  But it is an implementation detail (you get the exact same result either way) and imo not particularly relevant to my question because what it implements while in the frequency domain is not a simple LP filter like   [1 1 1 1 1 1 0  0 0 0 0 ] or even a graduated scalar LP filter like [1 1 1 1 0.9 0.5 0.1  0 0 0 0 ]

It had magnitude and phase which are determined soley by FFT of the FIR time domein filter sequence h[n].

It kind of boggles my mind to see a whole chapter in Oppenheim and Schaffer's Discrete Time Signal Processing devoted to development of time filters (FIR:  h[n] or IIR: y[n]=sumk(ak * y[n-k] + bk * x[n-k[).  But not a mention of just creating H(w) directly like [1 1 1 1 0.9 0.5 0.1  0 0 0 0 ].  Could it be explained simply that they are only concerned with real-time DSP as IRStuff suggests?  I have a hard time imagining that, but could be.  Either that or as I stated at the beginning there is some problem with this approach.   I guess if I was really energetic, I would try it and find out.

Any more thougths?

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

IRstuff (Aerospace) · Answer 8 · 2008-01-28 01:17:05

It's in the intro to O&S' book. It talks about analog processing. It talks about digital post processing for algorithms that can't be run in real-time.

Read on in Chapter 1. The discussion pertains to discrete time signals as sampling of analog signals. Analog signals are always real-time.

TTFN

FAQ731-376: Eng-Tips.com Forum Policies

IRstuff (Aerospace) · Answer 9 · 2008-01-28 01:22:01

Part of the problem may be semantics. A LPF, almost by definition, is the application of a process on a real-time signal.

When you do a zeroing in frequency domain from the entire data set, and then inverse the FFT, you modify the signal across all time, hence, it cannot be a real-time process, since that means you have information from the future. Therefore, there can never be an exact translation from real-time processing to post-processing.

TTFN

FAQ731-376: Eng-Tips.com Forum Policies

MacGyverS2000 (Electrical) · Answer 10 · 2008-01-28 08:53:45

Quote (IRstuff):
Part of the problem may be semantics. A LPF, almost by definition, is the application of a process on a real-time signal.

I'll respectfully disagree with this statement... image processing is quite often not real-time (think PhotoShop), and they use LP and HP filters all day long. JPEG compression uses HP filtering on the DCT coefficients for space-efficient encoding. Wavelets use LP and HP filters as a matter of course for their processing steps. I could obviously include a number of other samples here, but I believe the point is made.

Dan - Owner
http://www.Hi-TecDesigns.com

Noway2 (Electrical) · Answer 11 · 2008-01-28 09:04:16

If I remember correctly, the primary reason why one does not use the "brick wall" technique where the impulse chain abruptly changes from 1's to 0's is that you can achieve better performance through one of the various windowing methods. In this instance, 'better' performance refering to a combination of pass band ripple, sharpness of attenuation, stop band attenuation and ripple.

As was previously mentioned, to achieve an instanteous change in the frequency domain, such as an ideal filter, requires infinite time and vice versa.

Though I have never studied it, I have seen references to using an ideal or sin(x)/x filter for the purposes of signal reconstruction when converting from digital back to analog.

electricpete (Electrical) · Answer 12 · 2008-01-28 09:41:26

Thanks. I did get my hands on a book called "Digital Filter Designers Handbook" by Rorabaugh.

He does in fact discuss the FFT / multiply by [1 1 1 0 0 0] /IFFT method. He calls it "Digital Filter Design by Frequency Sampling Method". Surprisingly it doesn't come up front. It comes in chapter 12 after he has already discussed the time domain FIR methods in 11. And he jumps quickly into how to optimize a sequence like [1 1 1 0.0 0.5 0.1 0 0 0]

So I guess it is used. It is one of many possible ways to design a filter and like any has it's pro's and con's.

I did read the chapter 1 of O&S and I agree he is probably focusing towards real-time systems (although not exclusively of course) which may be why he omitted this technique in that particular book.

=====================================
Eng-tips forums: The best place on the web for engineering discussions.

sreid (Electrical) · Answer 13 · 2008-01-28 10:09:45

I think that one reason for the focus on real time filter applications had to do with military applications primarily tracking (missles, radar). The first DSP ICs were built for these applications because the Multiply and Accumulate is the fast hardware way to implement a FIR filter.

benta (Electrical) · Answer 14 · 2008-01-28 11:09:33

I wonder how the filtered signal would look. With a "brick wall" filter you'd get an infinite impulse response.

Benta.

Come Join Us!

Posting Guidelines

reasons why digital LP filter can't be done with FFT / IFFT