Where can I find a good FFT implementation / curriculum?

Question

I searched everywhere for an example implementation / training of fast Fourier transform in (preferably) C #.

However, everyone I found poorly explained what was happening and / or commented poorly; either they assume that you already know the FFT algorithm, or they are tutorials on how to use FFT.

Does anyone know a good sample / tutorial?

Answer 1

I apologize for the lack of hyperlinks, I do not have rights to add them :(

You are asking for two things here.

1) FFT explanation

Very briefly:

If you want to get a representation of the frequency domain of a signal using the Fourier transform, this is a mathematical transformation that converts the signal from the time domain to the frequency domain. When working with digital signals, we have a set of discrete samples, so we must use a discrete Fourier transform or DFT. However, this is a rather slow operation and is easily optimized, so instead we use the fast Fourier transform algorithm or FFT.

This is a big topic in signal processing, so I suggest you look for a signal processing book to use as a reference. I suggest Digital Signal Processing: A Practical Approach. There is, of course, a widespread Wikipedia article.

2) FFT implementation

Due to the highly optimized nature of FFT platforms and languages, specific implementations often arise, you should check the headers and documentation (as a rule, it will be found in the "audio" section) if it is included in the standard library.

If you want to implement the algorithm yourself, I recommend finding a copy of Numericical Recipes, which contains a whole chapter on FFT, as well as the chapter "Fourier Applications and Spectral Applications". There is a well-documented pseudo-code that should be easily translated into any language.

A popular choice for a third-party solution is FFTW, Library C. I am looking for google for the “FFT Library” to provide you with some alternatives.

Answer 2

See kissfft on sourceforge. It lacks FFTW speed, but it compensates for its small size and readability. There is also a pdf file on sourceforge about output - required if you try to understand it.

Answer 3

Google displays several:

• Exocortex.DSP

• FFTW (a DLL library that can be called from C #)

The FFTW library is recommended as a quick FFT solution.

Answer 4

Here is another one written in C.

http://www.archelon.com/fft.html

In addition, you can clarify your question. For example, do you want to compare DFT with FFT? Interested in why FFT is much faster?

If I remember correctly that DFT is something like multiplication N ^ 2, and FFT - N multiplications NN, where N is the number of samples in the signal.

Answer 5

Wikipedia has an excellent FFT entry: http://en.wikipedia.org/wiki/Fft .

In terms of implementations, FFTW is the fastest I have ever used, but the code is extremely difficult to understand, as it is crazy optimized. There are many references to the main FFT implementations, including C #; Google is your friend here.

Answer 6

http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html (yeesh, I found this useful, but the font and layout are terrible. I hope that only my browser will weird)

Answer 7

An old standard book for crunching numbers: Numericical Recipes, may have ample explanation.

Answer 8

If you can find a copy, microprocessor music applications by Hal Chamberlin, 1983 (?) May have an FFT section - alas, my copy is working now, so I can’t check the book specifically for the FFT wisdom. But I learned a lot of the basics of sound filtering, sampling, etc., And there is a lot of material about Fourier transforms and their use.

Answer 9

The problem is interpreting your word “good” for two completely different things.

A fast, modern, optimized FFT, such as FFTW, is almost useless for explaining what is happening. A huge part of the code is, as a rule, performance optimization, which is more associated with compiler hints, pipelining, parallelism, cache locking, etc., than the basic FFT algorithm.

While a good short (half a page of code) recursive FFT code example may look exactly like a summary of one of the conclusions of the FFT tutorial, it will be rather slow compared to FFTW.