How are FFTs different from DFTs and how would one go about implementing them in C++?

After some studyi开发者_JS百科ng, I created a small app that calculates DFTs (Discrete Fourier Transformations) from some input. It works well enough, but it is quite slow.

I read that FFTs (Fast Fourier Transformations) allow quicker calculations, but how are they different? And more importantly, how would I go about implementing them in C++?

If you don't need to manually implement the algorithm, you could take a look at the Fastest Fourier Transform in the West

Even thought it's developed in C, it officially works in C++ (from the FAQ)

Question 2.9. Can I call FFTW from C++?

Most definitely. FFTW should compile and/or link under any C++ compiler. Moreover, it is likely that the C++ template class is bit-compatible with FFTW's complex-number format (see the FFTW manual for more details).

FFT has n*log(n) compexity compared to DFT which has n^2.

There are lot of literature about that, and I strongly advise that you check that first, because such wide topic can not be full explaned here. http://en.wikipedia.org/wiki/Fast_Fourier_transform (check external links )

If you need library I advise you to use existing one, for instance. http://www.fftw.org/ This library has efficiently implementation of FFT and is also used in propariaretery software (MATLAB for instance)

Steven Smith's book The Scientist and Engineer's Guide to Digital Signal Processing , specifically Chapter 8 on the DFT and Chapter 12 on the FFT, does a much better job of explaining the two transforms that I ever could.

By the way, the whole book is available for free (link above) and it's a very good introduction to signal processing.

Regarding the C++ code request, I've only used the Fastest Fourier Transform in the West (already cited by superexsl) or DSP libraries such as those from TI or Analog Devices.

The results of a correctly implemented DFT are essentially identical to the results of a correctly implemented FFT (they differ only by rounding errors). As others have pointed out here, the major difference is that of performance. DFT has O(n^2) operations while the FFT has O(nlogn) operations.

The best, most readable publication I have ever found (the one I still refer to) is The Fast Fourier Transform and its Applications by E Oran Brigham. The first few chapters provide a very thorough overview of the continuous and discrete forms of the Fourier Transform. He then uses that to develop the fast version of the DFT based on the Cooley-Tukey Algorithm for the radix-2 (n is a power of 2) and mixed-radix cases (though the latter being somewhat more shallow treatise than the former).

The basic approach in the radix-2 algorithm to perform a linear time operation on the input X and to recursively split the result in half and perform a similar linear time operation on the two halves. The mixed radix case is similar, though you need to divide X into equal portions each time, so it helps if n doesn't have any large prime factors.

I've found this nice explanation with some algorithms described.

FastFourierTransform

About implementation,

• first i'd make sure your implementation returns correct results (compare the output from matlab or octave - which have built in fourier transformates)
• optimize when necessary, use profilers
• don't use unnecesary for loops