Bottom     Contents

Introduction

This document describes several 'Fast Fourier Transform' (FFT) algorithms, which may be used to efficiently evaluate the Discrete Fourier Transform (DFT). It does not describe the properties of the Discrete Fourier Transform in detail, nor does it attempt to explain why you should want to evaluate a DFT in the first place. It does contain a little detail on FFT based convolution, largely because this needed to understand some of the FFT algorithms. If you'd like to read this document off line you can download the zipped version (go to http://www.pkware.com/ if you don't know how to unzip). Please direct any comments about this document to the Web Master.

Of course, FFT algorithms cannot be properly understood without some understanding of the properties of the DFT. So, where necessary, the some of the relevant properties are presented in this document. The only thing you really need to understand before reading this document are the use of complex numbers in signal processing. Here's a very brief refresher on complex numbers:

Imaginary Numbers

Define:

equation

So the square root of any negative real number -x (x is positive!) is:

equation

Complex Numbers

A complex number A is the sum of real (ar) and imaginary (j.ai) part:

equation

Note both ar and ai are assumed to be real.

Complex Addition:

equation

Complex Multiplication:

equation

equation

Modulus:

equation

(The modulus is real.)

Complex Conjugate:

equation

equation

equation

equation

Complex Division:

equation

Complex Exponentials (x is real):

equation

equation

equation

equation

equation

equation

equation

(The arctan function above must work over 4 quadrants, by taking account of the signs ar and ai separately.)

©1999 - Engineering Productivity Tools Ltd.


Next     Top