|
Components |
home
FFT Library
Added: 11Mar2003
This library provides a free Delphi implementation (source included)
for a complex Fast Fourier Transform (FFT)
on an arbitrary length data series.
Introduction
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.
Theory
This FFT algorithm is a modified version based on a method called mixed-radix, 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 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
x[m].
Files
| FFTs.pas | Forward FFT transform and inverse FFT transform on complex data series |
| Complexs.pas | Complex number arithmic |
| Types.pas | Definition of the floating point type (either single
or double) |
| Readme.txt | File with information about the library |
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.
Download
By downloading the package you must agree to the terms stated in the readme.txt file. Download here (rightclick and use Save As...).
References
| [1] | R. C. Singleton, "An Algorithm for Computing the Mixed Radix Fast Fourier Transform", IEEE Trans. Audio Electroacoust., v. AU-17, p. 93, June 1969 |
Related Links
Com-N-Sense
developer's page
This company provides highly specialised software for many imaging and
audio processing tasks. On this page for developers you can find source
code that can help you with reading and writing WAV and RIFF files.
JEDI-Math library
A free Delphi source code library with many mathematical components.
The Scientist and
Engineer's Guide to Digital Signal Processing
On this page you can download a free personal copy of this book. I highly
recommend this book as a starting point when starting with digital signal
processing. Read especially chapter
12 to get up to par with your FFT knowledge.
Fast
Fourier Transforms
Steve Kifowit has compiled this comprehensive list of FFT code
snippets with explanation. Some other general FFT-related information
can be found here.