Forums

FFT Based Filtering?

Started by moosedude November 20, 2006
Hello,

I'm writing a simple C++ application, which performs the following tasks;

1)  generates high/low pass daub 4-tap filters

2) performs a fft of those filters

3) performs a fft of the input, test signal

4) multiples the fft of the filters, with the fft of the test signal

5) performs a ifft of the result of the previous step, to output the
filtered result of the test signal.

Anyway, The results my test program is kicking out, is a bit
questionable;
is there a free Windows/PC program available that performs this type of
filtering that I can use to double check my results with, that will take
data input as CSV files?

Thanks!
> is there a free Windows/PC program available that performs this type of > filtering that I can use to double check my results with, that will take > data input as CSV files?
You can try either Scilab or GNU Octave, which are both MATLAB-like programs that are freely available. Jason
moosedude skrev:
> Hello, > > I'm writing a simple C++ application, which performs the following tasks; > > 1) generates high/low pass daub 4-tap filters > > 2) performs a fft of those filters > > 3) performs a fft of the input, test signal > > 4) multiples the fft of the filters, with the fft of the test signal > > 5) performs a ifft of the result of the previous step, to output the > filtered result of the test signal.
Seems OK so far. There are, of course, the issues about formatting the inputs and outputs etc, but there is no reason to think that might be an issue here.
> Anyway, The results my test program is kicking out, is a bit > questionable;
Why? What do you expect? What are the results of your program? You may want to be aware that the perfromance of FIR filters depends on th elength of the filters. The longe the filters, the sharper the transition bands. FIR filters also need to be designed specifically to give high attenuation. There is no reason to expect much more than, 10-15 dB attenuation for arbitrary filters. You could design a standard rectangular filter, where analytic expressions are available fir the filter function, and see if the results match up. Rune
moosedude wrote:
> Hello, > > I'm writing a simple C++ application, which performs the following tasks; > > 1) generates high/low pass daub 4-tap filters > > 2) performs a fft of those filters > > 3) performs a fft of the input, test signal > > 4) multiples the fft of the filters, with the fft of the test signal > > 5) performs a ifft of the result of the previous step, to output the > filtered result of the test signal. > > Anyway, The results my test program is kicking out, is a bit > questionable; > is there a free Windows/PC program available that performs this type of > filtering that I can use to double check my results with, that will take > data input as CSV files? > > Thanks!
There's a number of things that could be causing the output not to be as expected: - Are you using a windowing function to "taper" your sample window (if not you'll be introdocing high frequncy components) - Are you overlapping your windows by an amount appropriate - unity sum - to your tapering function (if not then your're modulating the signal by your window function) - Are you zero padding your window to sufficient length? The ftt length (achieved through zero padding) needs to be as long as the impulse response of the filter function that you are applying. Ben Bridgwater

Ben Bridgwater wrote:
> There's a number of things that could be causing the output not to be as > expected: > > - Are you using a windowing function to "taper" your sample window (if > not you'll be introdocing high frequncy components) > - Are you overlapping your windows by an amount appropriate - unity sum > - to your tapering function (if not then your're modulating the signal > by your window function) > - Are you zero padding your window to sufficient length? The ftt length > (achieved through zero padding) needs to be as long as the impulse > response of the filter function that you are applying.
Every single of the above points is wrong. For segmented FIR filter implementation using FFT, a) one does not use a window (this would periodically modulate the filter coefficients), and b) the FFT size has to be at least larger than the sum of the length of the impulse response plus the frame offset length minus one. This has been discussed here many times (for example here: http://groups.google.com/group/comp.dsp/browse_frm/thread/718fa41040b365be/7585d35fd4ba3693?#7585d35fd4ba3693), plus there is freely available literature that describes overlap-add and -save for FFT based FIR filtering (for example here: http://www.dspguide.com ). Regards, Andor
Andor wrote:

> > Ben Bridgwater wrote: > >>There's a number of things that could be causing the output not to be as >>expected: >> >>- Are you using a windowing function to "taper" your sample window (if >>not you'll be introdocing high frequncy components) >>- Are you overlapping your windows by an amount appropriate - unity sum >>- to your tapering function (if not then your're modulating the signal >>by your window function) >>- Are you zero padding your window to sufficient length? The ftt length >>(achieved through zero padding) needs to be as long as the impulse >>response of the filter function that you are applying. > > > Every single of the above points is wrong. For segmented FIR filter > implementation using FFT, > > a) one does not use a window (this would periodically modulate the > filter coefficients),
I thought that windowing functions were designed to allow unity overlap to avoid this (triangular 1/2, hanning 3/4, blackman 5/6)? http://ccrma.stanford.edu/~jos/parshl/Overlap_Add_Synthesis.html http://ccrma.stanford.edu/~jos/parshl/Choice_Hop_Size.html Is the theory here incorrect? I thought that using a segmented FFT on a non-stationary signal was always going to be modulating the input, even (or more so) if one does not use a tapering fucntion. Does this not apply to FFT based filtering?
> > and > > b) the FFT size has to be at least larger than the sum of the length of > the impulse response plus the frame offset length minus one.
Thanks for the correction. Ben Bridgwater
Ben Bridgwater wrote:

> Andor wrote: > > > > > Ben Bridgwater wrote: > > > >>There's a number of things that could be causing the output not to be as > >>expected: > >> > >>- Are you using a windowing function to "taper" your sample window (if > >>not you'll be introdocing high frequncy components) > >>- Are you overlapping your windows by an amount appropriate - unity sum > >>- to your tapering function (if not then your're modulating the signal > >>by your window function) > >>- Are you zero padding your window to sufficient length? The ftt length > >>(achieved through zero padding) needs to be as long as the impulse > >>response of the filter function that you are applying. > > > > > > Every single of the above points is wrong. For segmented FIR filter > > implementation using FFT, > > > > a) one does not use a window (this would periodically modulate the > > filter coefficients), > > I thought that windowing functions were designed to allow unity overlap > to avoid this (triangular 1/2, hanning 3/4, blackman 5/6)? > > http://ccrma.stanford.edu/~jos/parshl/Overlap_Add_Synthesis.html > http://ccrma.stanford.edu/~jos/parshl/Choice_Hop_Size.html > > Is the theory here incorrect?
I think that this describes the synthesis of sound from artificial FFT frames. Perhaps for this application, windowing is required. However, this is different to FIR filtering in the frequency domain. For filtering, a window is not necessary and will in fact, ruin your implementation.
> > I thought that using a segmented FFT on a non-stationary signal was > always going to be modulating the input, even (or more so) if one does > not use a tapering fucntion. Does this not apply to FFT based filtering?
No. FFT based filtering makes use of the fact that multiplication in frequency domain of two DFTed data frames (or vectors, as you prefer) corresponds to circular convolution in the time domain. All you need is zero-padding in the correct places to transform the circular into linear-convolution. No windows.
> > > > > and > > > > b) the FFT size has to be at least larger than the sum of the length of > > the impulse response plus the frame offset length minus one. > > Thanks for the correction.
>From the posts I see here in comp.dsp, it seems that FFT based
filtering is one of the most misunderstood concepts in DSP. I think this stems from the the (too) simple analogy one has in mind when thinking about an FFT filter like a graphic equalizer, combined with some familiarity with FFT based spectrum analyzers (where windows really do help). The most enlightening description I have read about overlap-add and -save methods was in fact written by one of the denizens of comp.dsp (Mark Borgerding), on the comp.dsp 2004 conference proceedings CD ROM. This CD ROM is available here http://www.danvillesignal.com/estore.php?sub=details&category=6&product=32&id=estore, and I can only recommend anyone even with the slightest interest in applied DSP to get a copy. It contains many more goodies from seasoned experts. Regards, Andor
Ben Bridgwater wrote:

   ...

> http://ccrma.stanford.edu/~jos/parshl/Overlap_Add_Synthesis.html > http://ccrma.stanford.edu/~jos/parshl/Choice_Hop_Size.html > > Is the theory here incorrect?
No, but you misinterpreted it. By "window", It seems that the author means the desired filter function.
> I thought that using a segmented FFT on a non-stationary signal was > always going to be modulating the input, even (or more so) if one does > not use a tapering fucntion. Does this not apply to FFT based filtering?
A tapered window is needed to mitigate the effect *in a single FFT* of the FFT size not being a multiple of the period of a periodic waveform. It serves no purpose with continuous signals, but if overlapped as you specified, does relatively little harm. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Andor wrote:
>>I thought that using a segmented FFT on a non-stationary signal was >>always going to be modulating the input, even (or more so) if one does >>not use a tapering fucntion. Does this not apply to FFT based filtering? > > > No. FFT based filtering makes use of the fact that multiplication in > frequency domain of two DFTed data frames (or vectors, as you prefer) > corresponds to circular convolution in the time domain. All you need is > zero-padding in the correct places to transform the circular into > linear-convolution. No windows.
OK, thanks. I had been thinking that the zero padding was only serving the purpose of making sure that the entire impulse response of the filter function was being included; I hadn't realized that it was also serving to take away the circularity (which is why I thought the window function was needed). Is there any intuitive way of seeing how this works, or is it just a matter of falling out in the math?
> The most enlightening description I have read about overlap-add and > -save methods was in fact written by one of the denizens of comp.dsp > (Mark Borgerding), on the comp.dsp 2004 conference proceedings CD ROM. > This CD ROM is available here > http://www.danvillesignal.com/estore.php?sub=details&category=6&product=32&id=estore, > and I can only recommend anyone even with the slightest interest in > applied DSP to get a copy. It contains many more goodies from seasoned > experts.
Thanks, Andor. I've bookmarked that link, and intend to order a copy. Ben Bridgwater
Jerry Avins wrote:

> Ben Bridgwater wrote: > > ... > >> http://ccrma.stanford.edu/~jos/parshl/Overlap_Add_Synthesis.html >> http://ccrma.stanford.edu/~jos/parshl/Choice_Hop_Size.html >> >> Is the theory here incorrect? > > > No, but you misinterpreted it. By "window", It seems that the author > means the desired filter function.
Well, I think I did mistunderstand it, but in a different way... On re-reading it appears that he is referring to the window function, but that the system being desribed isn't actually filtering. It seems that he's using a windowed FFT with optimal overlap to smoothly sample the input, but then is simply using the input peaks to drive a sinewave synthesis output using overlap and add. It makes more sense now! Ben