

Home > Coding Corner > Components > FFT Library  

FFT Library This library provides a free Delphi implementation (source included)
for a complex Fast Fourier Transform (FFT)
on an arbitrary length data series. Historically, FFT only works well for series with lengths that are a power of 2. However, practical problems often require Fourier transforms of series with lengths that are for instance a power of ten. With the code below, these transforms are calculated with virtually the same speed as for series with powerof2 lengths. Fast Fourier Transforms are probably more widely used than one might realise. Commonly, FFT is used to find the frequency distribution of a sampled signal. A good way to think of this is to see FFT as the digital version of the equalizer of your audio equipment. It will find how much each frequency band is represented in the signal. The complex version is often used because it will also allow to find the phase of signals and because the algorithm is more general and elegant. The complex version can be used for real signals without any problem, by simply setting the imaginary part of each element to zero. Theory This FFT algorithm is a modified version based on a method called mixedradix, first published by Singleton^{[1]}. It behaves like FFT for any series that can be factored in factors 2, 3, 4, 5, 8 and 10. When there are other prime factors in the series, it will calculate the subseries with a complex Discrete Fourier Transform (DFT). The largest prime factor that can be processed is limited in the source to 1021, but this can be easily changed. For "normal" length series, like 1.000, 10.000, etc, this is not neccesary. These are usually composed of a lot of factors 10 and therefore handled quite optimally by the radix10 FFT submethod. The mixedradix FFT is just as fast as normal FFT for power of 2 series, in all cases where the series can be composed of the factors above. In other cases it will be slightly slower. The slowest case would be a series length composed of one big prime factor, for example a length of 1021. In this case, the algorithm works just like DFT, and it would be advisary to add zeroes to the series to make it a length of e.g. 1024. The official formula for a complex DFT is given by: Where elements y[k] contain the Fouriertransformed version of elements
x[m].
License The library is released under the Mozilla Public License. More information can be found here. By downloading the library you agree to the terms in the license. By downloading the package you must agree to the terms stated in the readme.txt file. Download here (rightclick and use Save As...). References
Related Links ComNSense
developer's page JEDIMath library The Scientist and
Engineer's Guide to Digital Signal Processing Fast
Fourier Transforms


Page last changed: 13Nov2009 © Copyright 20022009 SimDesign 