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.

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 w

The frequency corresponding to index m is m * w

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

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 W

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.

COPYRIGHT © 2007 Cuthbert Nyack.