FFT Based Filtering?

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