can someone explain FFT filters?

[Churchy]

i know it stands for fast fourier transform, but when i look on the net for information, i get a lot of really full on mathmatical formulas .. i'm not a dummy but i'm no mathmatician either!

can anyone explain it in reasonable terms (or point to somewhere that does?)

cheers

[Lunch Money]

I'd be curious to know, too. I always thought the first "F" was "Full". SO you're one up on me. Thank god the BBA devs give me the details I need before I write the documents. <laff>

I also know that they operate by taking full-on chunks of audio and processing them that way. You might have a code that uses a buffer of 4096 samples for the FFT, which I ASSUME (someone can correctly) means that it's processing those 4096 samples of information before moving on to the next 4096 samples. The practical result is that you will always have a fixed latency at least equal to the number of samples used in the buffer.

[aciddose]

basically you can get the relative amplitudes and phases of certain frequencies in the waveform by using this function:

void DFT(long n, double *realTime, double *imagTime, double *realFreq, double *imagFreq)
{
long k, i;
double sr, si, p, a, d;

for(k = 0; k < n; k++)
{
realFreq[k] = 0.0;
imagFreq[k] = 0.0;
}

a = 0.0;
d = (2.0 / n) * __PI;
for(k = 0; k < n; k++)
{
p = 0.0;
for(i = 0; i < n; i++)
{
sr = cos(p);
si = -sin(p);
realFreq[k] += (realTime * sr) - (imagTime * si);
imagFreq[k] += (realTime * si) + (imagTime * sr);
p += a;
}
a += d;
}
}

an FFT is an optimization of that, realizing several possible improvements can be made by using a window (n) which is a power of two. 2^

once you have the amplitudes and phases of all those frequencies, you can adjust them individually in any way you like.

you then take the modified data and turn it back into a waveform via the function:

void InverseDFT(long n, double *realTime, double *imagTime, double *realFreq, double *imagFreq)
{
long k, i;
double sr, si, p, a, d;

for(k = 0; k < n; k++)
{
realTime[k] = 0.0;
imagTime[k] = 0.0;
}

a = 0.0;
d = (2.0 / n) * __PI;
for(k = 0; k < n; k++)
{
p = 0.0;
for(i = 0; i < n; i++)
{
sr = cos(p);
si = -sin(p);
realTime[k] += (realFreq * sr) + (imagFreq * si);
imagTime[k] += (realFreq * si) - (imagFreq * sr);
p += a;
}
realTime[k] /= n;
imagTime[k] /= n;
a += d;
}
}

that is all there is to it.

[aciddose]

oh, about your observation of the "window" size, no that is incorrect. you operate on the 'window' of samples at a time, however you only move ahead by one sample for every execution of the function. basically you're taking "window" of samples into account to modify one sample. otherwise, you'd be able to use any window size and have the same amount of time taken to perform the operation. obviously however, it takes much more time to operate 1000 times for one sample than to operate 10 times, so using large windows is obviously a more intensive calculation.

[Lunch Money]

Groovy. Greek, but Groovy.

[Churchy]

oh cool! that clears things up a lot, thanks

[ouroboros]

Groovy. Greek, but Groovy.

ROFL!


FFT= Fast Fourier Transformations.
(I truly do not comprehend the math, so take this with a grain of salt). FFT is essentially an algorithm that can quickly (i.e., using a minimal amount of cpu/mathematical steps(?)) detemine the composite frequencies of a sound if the sample is of a finite length.

So, a FFT sonograph uses an algorithm to efficiently analyze and break down a sound into its constituent parts. In a sonograph, a "snapshot" of the sound is given in which the FFT algorithm has determined what frequencies compose the sound examined.

Presumably an FFT filter would take a sound apart (describe the constiuent elements) and then filter out the undersireables. There's probably a much clearer and more practical xplanation to be had.

I believe that the (F)ast in FFT implies that there are a number of "transformations," or algorithms that Mr. Fourier developed, and so different programs may use different FFTs (?)

I offer this only as an attempt to refine my own knowledge by trying to articulate the little I understand Others with waaay more knowledge will chime in, I hope, but it took me a while to suss this much out...so there it is

[duncanparsons]

To give an explanation avoiding all the math, it gets the frequencies contained in your samples using sympathetic resonance (like when you strike the low E on a guitar, the top E will vibrate a little, since some of the harmonics of the Low E correspond to harmonics of the Top E).

The algorithm essentially loops through the buffer with sine waves of increasing frequency and for a bunch of wave starting points (the phase), then tests whether there is any resonance. It does this by multiplying the current buffer sample with the current wave sample, and adding it to any previous numbers for the same position.
That's the part which reads.
realFreq[k] += (realTime * sr) - (imagTime * si);
imagFreq[k] += (realTime * si) + (imagTime * sr);

You don't need to know about what real and imaginary mean, particularly, it's to do with complex math (imaginary numbers are ones which relate to sqrt(-1) [try that in a calclator to see why it's imaginary..]

At the end of all the loops, you have a set of data that is the same length as your original sample set, but rather than being discrete time samples, they are now grouped together as relative frequency volumes with phase information which describe the sine waves needed to reconstruct your signal.

EQ is now really easy. Want a cut at 3k? Just find the 'bin' or bins around 3k, and reduce the volume level. Pitch shifting, phase manipulation, etc all becomes fairly easy (you still need to have some respect for your data tho..)

Once everything is sorted, you do the reverse of how you got there, basically you go through the frequencies, and build up the sine waves, like a synth with several thousand oscillators...

I disagree slightly with acidose.. Whilst you can go through that whole rigamaroll for each sample, more generally a coder will take a buffer, and process it; then, rather than move on that whole buffer length, they will move on half the buffer length, process then add the overlap together (you might read about 'overlap and add' - all makes sense!). You don't get overshoots in the add, since the buffer is processed with a fadein and fadeout which attempts to keep the signal at a constant level. There are different types of fades, which produce different results (you'll see the names Hanning, Hamming, Blackman, Turner, Overdrive.. Those last two were a joke..)

This all sounds really dandy, and why doesn't everyone do it? Well
i. it's computationally expensive to do the conversion

ii. the frequency 'bins' aren't as accurate as we would like (they are evenly spaced linearly, we interpret stuff logarithmically, so an FFT has great fidelity in the HF region, and very poor in the LF).
You can increase the resolution of the frequencies, by using a larger buffer. If you recall, the processed information fits in the same degree of space as the initial buffer; so if we have a larger buffer to process, the information back will be greater. However, doing this means that your discrete time stuff is less accurate. It's a trade off.
The best system would be to split your normal time related samples into 2 or 3 frequency regions, then process each region with an appropriate sized window (large for LF, smaller for HF), and maybe adjust the overlap, so rather than tracking on half a buffer and adding, track a third of a buffer and do more overlaps. Your CPU has now melted trying to keep this up at 96kHz.

So there you are! If you want an intelligent paper than does the math, but keeps you sane, then read 'DFT a Pied' by Stephan Bernsee on dspdimension.

HTH
DSP

[aciddose]

hm, i suppose there are many possible implementations. i've never really spent a huge amount of time working with FT stuff, generally when i want to do something it works with what i've done so far. generating pulses and stuff is pretty simple, doesnt require anything complicated.

it seems to me processing every sample is kind of overkill for most of the general uses, isnt it. i've been meaning to look into more example source for the commonly used methods to see if what i'm doing is even close to usual. but its been ages and i still havent gotten around to it. some time i suppose i'll have a need for FT and i'll do it, i guess.

[arke]

Why don't we ask Tony Tony Chopper? He's done it plenty of times, I'm sure

[ouroboros]

Taut explanation, thanks! Best short-non-math explanation I've read and helped put the idea better in place, thanks!
That link is really great: <BOOKMARKED!>
I love KVR. There's no substitute for people who know what they're talking about. I imagine.

[autloc]

it seems to me processing every sample is kind of overkill for most of the general uses

It's probably overkill for all filtering uses* -- might as well just use a FIR at that point. If you're doing a 1024 point FFT per sample, you're taking on the order K * 1024*log(1024) cpu cycles, whereas a 1024 point FIR filter would only be taking K*1024 cycles. The FIR filter would also allow you to easily change it over time without worrying about artifacts.

*trust someone to come up with an exception...

[SKoT_FX]

Nothing beats multiplication in the frequency domain for speeding up convolution, an essential use of FFTs. Also, complex + complicated filter design is much MUCH easier in the frequncy domain, as you can design phase and amplitude response across the spectrum, and apply it as a single filter. Horses for courses.

[duncanparsons]

..is there a VST host for Cray2?

DSP