Menu
I've been looking everywhere for a sample Fast Fourier Transform implementation/tutorial in (preferably) C#.
However, every one I've found has been poor at explaining what's going on, and/or poorly commented; or they assume that you already know the FFT algorithm, or they're tutorials about how to USE FFTs.
Anyone know of a good sample/tutorial?
290
FFTW is the most popular FFT library. It has planty of features and it's often used as the reference point, but a number of other libraries has comparable or better performance.
Y = fft( X ) computes the discrete Fourier transform (DFT) of X using a fast Fourier transform (FFT) algorithm. If X is a vector, then fft(X) returns the Fourier transform of the vector. If X is a matrix, then fft(X) treats the columns of X as vectors and returns the Fourier transform of each column.
Hence, fast algorithms for DFT are highly valuable. Currently, the fastest such algorithm is the Fast Fourier Transform (FFT), which computes the DFT of an n-dimensional signal in O(nlogn) time. The existence of DFT algorithms faster than FFT is one of the central questions in the theory of algorithms.
The FFT can have any number of dimensions, but 1D FFTs are commonly used for data that is inherently one dimensional, e.g. audio, and 2D FFTs are used for 2D data such as images. In the general case both the input data and output data are complex, i.e. there are real and imaginary components in each input/output value.
Apologies for lack of hyperlinks, I do not have permissions to add them :(
You are asking for two things here
1) An explanation of the FFT
Very briefly:
If you want to obtain the frequency domain representation of a signal you use the fourier transform, this is a mathematical transform which transforms a signal from the time domain to the frequency domain. When operating on digital signals we have a set of discrete samples so we must use the Discrete Fourier Transform or DFT. However this is a rather slow operation and is easily optimised, so we instead use a Fast Fourier Transform algorithm or FFT.
This is a large signal processing topic 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 the ubiquitous wikipedia article as well.
2) An implementation of the FFT
Because of the highly optimised nature of the FFT platforms and languages often have specific implementations, you should check headers and documentation (typically it will be found in an 'audio' section) in case it is included in a standard library.
If you want to implement the algorithm yourself I recommend finding a copy of Numerical Recipes, this contains an entire chapter on the FFT, as well as a chapter on "Fourier and Spectral Applications". There is well documented pseudocode which should be easy to transcribe into any language.
For a third party solution a popular choice is FFTW, a C library. I google search for "FFT Library" will provide you with some alternatives.
72
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
