# 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.