So how fast can I FFT?

[bluefoxicy]

How fast can I fast fourrier transform a stream to get fundamental frequencies? Can I pull this off in 10mS or less in a hard real-time scheduling system?

What I want to do is i.e. bring in a guitar signal; fast fourrier transform it; then reassemble with sine waves based on primary frequencies +/- so many Hz at a specific resolution.

In theory, if I were to generate sine waves at every amplitude indicated along a perfectly smooth graph, it would sound exactly like the input, correct? If I do considerably fewer, it would sound... actually, probably like an MP3 or Ogg Vorbis file, considering.

Here's the interesting part: If I tuned the waveform generators in the same way you'd tune a pure synthesizer (i.e. no samples), i could spit out interesting synth effects... matching an instrument. Any instrument. I could have a guitar that plays square waves, saws, funky synth effects, etc. In theory anyway.

[Steve Conner]

How long is a piece of string? The DSPs I use at work will do a 1K point FFT in 200 microseconds, and I imagine a desktop PC will be faster, in terms of throughput if not latency.

Windows and Linux are not hard real-time, no matter what anyone will tell you. Sure, you can get single-digit audio latencies on a well-set-up system, but the point is that they're not guaranteed by design, as they would be in a real RTOS.

But even if we assumed they were perfect, then the biggest FFT you can do without violating your 10ms latency spec is, naively, one that contains 10ms worth of samples, ie about 441. There are tricks to get round this, if you're interested I recommend some heavy googling of the music-dsp mailing list archives.

Oh, and the process you call "reassemble with sine waves" is just the inverse FFT, of course. If you do a FFT followed by an IFFT then you get back exactly what you started with. It's a common procedure to FFT, multiply the output by some kernel, and then do the inverse FFT. This is called FFT convolution and it's how many reverbs and cabinet simulators work, for example. You can think of it as an efficient way to implement FIR filters with large kernels.

[bluefoxicy]

Cool, so a small embedded system could probably pull this off on an ARM no problem. Hmm...

...guitar-controlled synthesizer, naive and unaware of what exact "notes" are being played. Doable?

[Enzo]

Have you looked into existing guitar synth systems? Yamaha, Roland, I don;t recall who else.

[R.G.]

How fast you can compute an FFT is not such an issue. How much data you have to compute it on is. 10mS is one period of 100Hz. The period of an 82Hz E string is 12mS.

I haven't touched sampling issues in quite a while, but is sampling for one cycle enough for the errors in the FFT to be tolerable, even if your FFT is instantaneous?

[Old Tele man]

...also, if you only do "forward" FFT, you can "pack" real data into both sides of the butterflies (real & imaginary) and the FFT will then only have to handle HALF as many inputs, so it will be much, MUCH faster...but, at the end of the FFT you will loose a little time by having to "unpack" the real results from both real & imaginary values.