|home||Home > Coding Corner > Components > 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 power-of-2 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.
This FFT algorithm is a modified version based on a method called mixed-radix, first published by Singleton. 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 radix-10 FFT submethod.
The mixed-radix 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 Fourier-transformed version of elements
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...).
The Scientist and
Engineer's Guide to Digital Signal Processing
|Page last changed: 13Nov2009 © Copyright 2002-2009 SimDesign|