FFT, Brief Introduction
Cuthbert Nyack
The Fast Fourier Transform(FFT) is a special case of the Discrete
Fourier Transform(DFT) where the information about the signal is limited to a number of samples x(n) taken at discrete intervals of time T. In order to use the FFT, the number of samples should be a power of 2(
2, 4, 8, 16, 32, etc). The basic definition of the transform X(m) and its inverse x(n) is the same as that
for the DFT and is shown below.
The input x(n) usually consists of N real numbers although complex ones are allowed. X(m) consists of N complex numbers but because of the
symmetry of the FFT, X(m) contains only N independent variables.
If the number of samples Ns is not a power of 2 then (2n - Ns) zero samples
can be added to bring the total to a power of 2(n is given by 2n - 1 < Ns < 2n).
At first sight it may be confusing as to how this definition relates to
the Fourier Series. For large N, the magnitude of the coefficient of the
Fourier Series (am2 + bm2)½ = (2/N) * |X(m)|. This
definition is not universal and at least 2 other definitions can be
found in the literature. One puts the 1/N factor in front
of the transform.
Another possibility, often found in software packeges has N-½ in front of both the transform and its inverse.
The symmetry properties of the FFT are the same as those for the DFT.
Relation between m and frequency.
The result of the FFT calculation gives N complex numbers corresponding
to the real and imaginary parts of the frequency component X(m).
If N samples are taken in the sampling interval Ti, then the sampling
frequency ws = 2 * p * (N - 1)/Ti.
The frequency corresponding to index m is m * ws/N rad/s.
Decimation in Time.
When the number of samples N is a power of 2 then the transform can
be represented by the following expression.
The first summation is a N/2 samples DFT using the even samples and the
second summation is a N/2 samples DFT using the odd samples. Thus the
original N samples DFT has been reduced to 2 N/2 samples DFT. The
2 DFT's are then combined using WNm as shown above.
The N/2 even samples of the original N samples can also be broken down
into N/4 even and N/4 odd samples. The DFT of each can be found and
combined to form the N/2 point DFT as shown by the equation above. A similar proceedure is applied
to the N/2 odd samples. This reduction can be continued until only
2 point DFT's are left. Because the proceedure started with samples in
the time domain, then it is referred to as Decimation in Time.
The equation below shows the result X(m) for N = 4. In this case only
1 reduction step is required.
The above result for 4 samples can be expressed as the product
of 3 matrices as shown below. WS is the scrambling matrix. The scrambling matrix is obtained by bit reversal of the binary representation of n in x(n).
If the DFT is used, the multiplication required is shown below.
At first sight, it might appear that the DFT is simpler because
only one matrix multiplication is required. However all the elements
in the DFT matrix are nonzero, while the FFT matrices WT1, WT2 contain
only 2 elements per row and at least one is 1. As N increases, the DFT always requires N2 complex multiplications while for the FFT it can be shown that only N log2(N) is required.
The calculation is illustrated by the 'butterfly' diagrams in the applet below, which shows both the DIT FFT and the DFT calculations. xs(n) is the input after scrambling is applied. The heavy lines require multiplication.
The second row of WT1 can be written as
x1(1) = xs(0) - xs(1)
The second row of WT2 can be written as
X(1) = x1(1) - j x1(3)
Both of which can be verified by changing the x's using the scrollbars.
The node numbers refer to the W multiplying factor and show the calculations required.
eg X(3) = x1(1) + W(3) * x1(3); x1(3) = xs(2) + xs(3) * W(2).
Note that each step in the calculation requires one
complex multiplication (W(3) * x1(3)) followed by 1 addition
(x1(1) + (W(3) * x1(3))). DSP microprocessors whicah are optimised for DSP calculations can carry out one complex multiplication and 1 addition in one clock cycle.
W(n) on the applet is equivalent to WNn
The colors are meant to indicate the additional number of calculations required to calculate an output assuming the result of previous calculations are stored. The red lines
show the calculations required for X(0). Three heavy lines mean
3 multiplications. Yellow lines show the calculations required
for X(1), 3 heavy lines also mean 3 multiplications. Magenta
lines show additional calculations required for X(2), only 1
multiplication. Cyan lines show only 1 multiplication required
for X(3).
Decimation in Frequency.
Instead of breaking up the time samples into odd and even parts, the
Frequency spectrum can be broken up into odd and even parts as
shown below.
For 4 frequency samples, the result can be expanded as shown below.
This approach can also be described as a matrix multiplication using
the 2 matrices shown below. The result is scrambled and an additional unscrambling operation is required.
The Decimation in Frequency calculation is shown by the applet below.
For the DIT calculation each node has 1 light and 1 heavy line leading
to it. For the DIF case, the input lines to any node are either 2 heavy or 2 light
ones.
The node numbers show the calculations required to obtain the value at the node.
eg 1- on the x1(3) node which has 2 heavy lines leading to it means x1(3) = (x(1) - x(3)) * W(1).
the + on the X(1) node which has 2 light lines leading to it means X(1) = x1(2) + x1(3).
The equation used to arrive at a node is also one way to distinguish
between DIT and DIF butterfly diagrams.
Return to main page
Return to page index
COPYRIGHT © 2007 Cuthbert Nyack.