GameDev.netFast Fourier Transforms

Fast Fourier Transforms
First a little bit about me: I'm a software engineer for company in southeastern Michigan that makes test equipment for the friction materials industry (mostly car & truck brakes). It's aesthetically important (consequentially financially important) that brakes make minimal noise while stopping the vehicle. So there's an NVH option on our dynamometers to hook up to a dedicated hardware analyzer to collect audio spectrum data. The analyzers are really expensive (30k or so) and we use a miniscule portion of their capabilities, so my boss had me investigate the possibility of using a PC software based spectrum analysis. This is just an example of the ubiquitous applications of Fourier transforms (named after French mathematician Jean Baptiste Joseph Fourier). The Fourier transform has the unique capability of taking functions from the time domain to the frequency domain. A few hundred years ago French mathematician Jean Baptiste Joseph Fourier developed the calculus based transform to solve heat diffusion problems. A number of decades ago a method to quickly calculate discrete FFT's of the power was developed, and first implemented in Fortran. If you are interested in more history or details on implementing an FFT check out Numerical Recipes. I would be lying if I said Numerical Recipes (popular & comprehensive numerical algorithm book) had absolutely no impact on my FFT, but I would also be lying if I didn't find their C source revolting (it's a direct port of their algorithm from Fortran). Their licensing arrangements are also unacceptable (royalties & no dlls allowed). So I decided to write my own in C++; one that didn't use any gotos and that was faster by design. Nearly every FFT algorithm I have reviewed has been concerned with preserving the amount of memory being used. They always use a so-called "in place" FFT. For the application I was concerned with, I had memory to blow, and I think my code is slightly more readable than most available on the Internet, made so by its limited use and the FFTing methodology I implemented. It may not be clear why it accomplishes a FFT, but what the code does should be clear. The function of interest is _ROFFT (Real Out-of-place Fast Fourier Transform). _CISFT (Complex In-place Slow Fourier Transform) is a naïve implementation, but is the simplest to implement & understand. The source is a VC6 workspace and has two projects, one to create a dsp.dll and a simple test program. Incidentally, Intel has a DSP package available for download here
© 1999-2011 Gamedev.net. All rights reserved. |