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 |