Bottom     Previous     Contents

FFT's are fast DFT Algorithms.

It may be noted that the number of complex multiply and add operations required by the simple forms both the DFT and IDFT is of order N2. This is because there are N data points to calculate, each of which requires N complex arithmetic operations. In computer science jargon, we say they have algorithmic complexity O(N2). This is not good news. If we can't do any better than this then the DFT will not be very useful for the majority of practical DSP applications. Fortunately, there are a number of different 'Fast Fourier Transform' (FFT) algorithms that enable us to do very much better than this.

For example, the popular 'Radix 2' algorithms are useful if N is a regular power of 2 (N=2p). These algorithms have complexity of only O(N.logN). If we (naively) assume that algorithmic complexity provides a direct measure of execution time (and that the relevant logarithm base is 2) then the ratio of execution times for the (DFT) vs. (Radix 2 FFT) can be expressed:

equation

For a 1024 point transform (p=10, N=1024), this gives approximately 100 fold speed improvement. This is why FFT's are important. Of course the actual speed improvement that is achieved in practice depends on other factors associated with algorithm implementation and coding efficiency, but the above expression is useful to get 'ball park' estimates.

The term 'FFT' is actually slightly ambiguous, because there are several commonly used 'FFT' algorithms. There are two different Radix 2 algorithms, the so called 'Decimation In Time' (DIT) and 'Decimation In Frequency' (DIF) algorithms. Both of these rely on the recursive decomposition of an N point transform into 2 (N/2) point transforms. This decomposition process can be applied to any composite (non prime) N, it just so happens that is particularly simple if N is divisible by 2 (and if N is a regular power of 2, the decomposition can be applied repeatedly until the trivial '1 point' transform is reached). The so called Radix 4 algorithms are similar in concept to the Radix 2 algorithms. These are sometimes slightly faster. There is also an efficient algorithm for evaluating the DFT of sequences whose length is a prime number.

In short, there is always an FFT algorithm (and usually several) which can be applied to any sequence length.

©1999 - Engineering Productivity Tools Ltd.


Next     Top