Components home

Projects

Products

Coding Corner
Components
Tips

Design Background

Curriculum Vitae

Forum

FFT Library

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. 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

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

  R. C. Singleton, "An Algorithm for Computing the Mixed Radix Fast Fourier Transform", IEEE Trans. Audio Electroacoust., v. AU-17, p. 93, June 1969

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.

Page last changed: 13Nov2009 © Copyright 2002-2009 SimDesign