VFX Appendix A - The FFT

VFX Article, Appendix A

A. The FFT

The Fourier series and its related transforms and algorithms are widely known and used in electronics. The Fourier Transform (FT) is a mathamatical method for converting a signal from the time domain to the frequency domain; simply a way of expressing a continuous waveform as a series of sine waves. The Fast Fourier Transform or FFT is an improved algorithm enhanced for computer implementation for performing a Discrete Fourier Transform (DFT), the digital equivalent of the Fourier Transform (FT). Saying it another way, the FFT is a fast way of obtaining the fourier series of a function in the time domain. In the case of the VFX processor, the time domain function is an audio signal.

The FFT is used in numerous applications from radar signal processing to brain wave analysis. How fast is the FFT? The FFT does increase the speed that a computer can compute the DFT and so a realitive improvement factor is a good way to look at it. Let's look at the DFT first. To perform an 8 point DFT (N=8) we have to generate 8 harmonics. Lets start with the fundamental. Take a sine wave, break it up into 8 data points each 360/8 degrees apart and take the sine of each point. Multiply the first data point by the first point of the sine wave. Take the 2nd data point and multiply it by the 2nd point of the sine wave. Add that to the result of the first multiplication. Repeat this for the 3rd, 4th, 5th, 6th ,7th and 8th data points. The result is a measure of the amount of the fundamental wave in the signal. So far we have performed 8 multiply accumulate (MAC's)operations. Next we repeat this for the other harmonics. Each one requires 8 MAC's. The total MAC's would thus be 8 x 8 or 64 (N squared). The FFT reduces the number of complex MAC's required to compute the DFT from N^2 to Nlog2N. With N=8 the number of MAC's required is 24. Figure 7 depicts the 8 point FFT using whats commonly known as a butterfly diagram. Each X represents two MAC's indicating that there are indeed 24 MAC's.

In the case of the VFX processor which uses a 128 point FFT, the number of Multiplications and Accumulations (MAC) is reduced from 16k to .9k or by a factor of 18. With larger FFT's the advantages are much greater. This is significant and points to the reason for the extreme popularity of the FFT. Without this algorithm, the VFX processor, despite the speed of the ADSP-2105, would not come close to real time performance. Conversely, the VFX processor and many other applications would not be possible without the FFT. How does the FFT reduce the number of calculations so markedly?

In describing this fantastic improvement many texts refer to the process of dividing an N point DFT into two N/2 DFT's. This is done in one method by dividing the set of input points into odd and even sets and performing the DFT on each set. Thus, the number of MAC operations is cut from N^2 to 2*(N/2)^2 or (N^2)/2. If this halving is performed again on each of these two DFT's the number of calculations is reduced further. Each halving produces a reduction in the MACs required with the limit being Nlog2N. Another way to look at the FFT is to understand that we are not throwing away calculations that are necessary, we are throwing away calculations that are redundant. There are many redundant calculations being performed in the DFT: a.) First of all, when the angle is 0 or 180 degrees the sine is valued at 0 so no useful data results. This calculation occurs many times for each harmonic since the angle passes through 0 and 180 each cycle. b.) The sine of 90 and -90 is 1 and -1 so that only addition is required. c.) Sine(angle) is equal to the -sine(angle + 180 deg) so that this calculation need not be repeated.

Previously we noted that the FFT is often expressed as a butterfly which is a pictorial representation of the algorithm. Its form indicates the type of algorithm, the coefficients required and the output form. An example of a butterfly diagram for an eight point FFT is shown in Figure 6. The important things to note are: a) The input data is scrambled in a special way called bit reversal. That is, the data point x(k) is replaced with x(k') where k' is the bit revered binary equivalent of k (i.e. MSB becomes the LSB). b) The output frequency coefficients are in normal order c) Each X represents a complex MAC. d. The large W's indicate twiddle factors which are basically the points of a sine wave. The numbers with the W indicate the angle of points. Thus Fourier and other frequency domain processes have become very efficient and popular in the signal processing arena.

The FFT and Inverse FFT are the most complex algorithms implemented by the VFX processor. The FFT algorithm takes 2 to the N samples, in this case 2^7 (128) in the time domain and converts them to the same number of points in the frequency domain. This process is illustrated by Figure 2. A standard FFT algorithm is implemented in a QuickBASIC included in Figure 5. The program illustrates that the algorithm is not overly complex and by entering and running it you can get a feel for how it works. This particular program allows you to change the input waveform and observe the output spectrum. It is interesting to note that the FFT algorithm was popularized for computers by James Cooley and James Tukey in the 60's. It was noted by Cooley that the algorithm itself has been around for a long time and that it was not until the advent and popularization of the digital computer that the real usefulness of the algorithm was appreciated and widely employed.