Basis of the Fast Fourier Transform

1. Basic equation

We shall take as the basic relationship of the discrete Fourier Transform: where X[k] is the kth harmonic (k=0..N-1), x[n] is the nth input sample (n=0..N-1), and WN is shorthand for exp(-i2p/N).  This is a slight simplification of the formula in the notes for purposes of exposition.

2. The 2 point transform

When N=2, we can write out the formulae for the harmonics as:  but, = 1 and = exp(-ip) = -1.  So this can be re-written as:  The 2 point transform is very easy to compute!  It takes just one addition and one subtraction.

3. Decimation in time

What we aim to do is to simplify the expression for a transform of length N by re-writing it as the combination of two transforms of length N/2.  Here we use the procedure called decimation in time. Here, we decompose the operations on x[] into the sum of operations on the even samples of x[] and the odd samples of x[].  In the next line, we rewrite the sum to involve the exponential terms rather than .  Now use the important equality: to show that the division into two sub-sequences gives the same result (apart from a ‘twiddle factor’) as the sum of two transforms of length M=N/2: Where G[k] and H[k] are transforms of half the original size.  If N is a multiple of 4, then the decomposition can be applied again to into the sum of 4 transforms of length N/4.  If N is a power of 2, then we can perform log2N decomposition stages into the sum of N/2 transforms of length 2.  And we have already noted that transforms of length 2 are very simple to implement.

4. Signal flow graph realisation

If we study the set of equations for a transform of some length N which is a power of 2, we find that the values of the WN factors take on a small range of values, many of which are ±1 or ±i.  These terms can be implemented without multiplication.  In addition, many of the products of x[n] with these terms arise many times, and hence need only be calculated once.

The combination of the ideas of (i) the simplicity of the 2 point transform, (ii) the decimation in time of a transform of length N into transforms of length 2, and (iii) the removal of unnecessary multiplication, produces a DFT procedure that is substantially more efficient.

Let us implement a transform of length 4 in an efficient way using these ideas.  The procedure could be applied to any transform of length 2M. but note that is the same as , and is the same as , so the last two harmonics can be written as: We can now see that some of the two-point transforms are shared between the harmonics and so only need to be calculated once.  We can demonstrate this in a signal flow diagram such as the one below: The diagram shows two processing stages.  In stage 1, four intermediate values are calculated: Then in stage 2, these values are combined to give the final results: 5. Performance improvements

The basic DFT formula requires N complex multiplications for each of N harmonics, making N2 multiplications in total.  In the decimation in time procedure and the signal flow graph, there are log2N processing stages, each of N complex multiplications, or Nlog2N multiplications in total.  The difference is large for reasonable N:

 N N2 Nlog2N Ratio 8 64 24 2.7 64 4096 384 10.7 512 262144 4608 56.9 4096 16777216 49152 341.3