The Fast Fourier Transform It is difficult to overstate the importance of the FFT algorithm for DSP. We have often seen the essential duality of signals in our studies so far; we know that exploiting both the time and the frequency aspects is critical for signal processing. We may safely say that were there not a fast algorithm for going back and forth between time and frequency domains, the field of DSP as we know it would never have developed. The discovery of the first FFT algorithm predated the availability of hardware capable of actually exploiting it. . | 14 Digital Signal Processing A Computer Science Perspective Jonathan Y. Stein Copyright 2000 John Wiley Sons Inc. Print ISBN 0-471-29546-9 Online ISBN 0-471-20059-X The Fast Fourier Transform It is difficult to overstate the importance of the FFT algorithm for DSP. We have often seen the essential duality of signals in our studies so far we know that exploiting both the time and the frequency aspects is critical for signal processing. We may safely say that were there not a fast algorithm for going back and forth between time and frequency domains the field of DSP as we know it would never have developed. The discovery of the first FFT algorithm predated the availability of hardware capable of actually exploiting it. The discovery dates from a period when the terms calculator and computer referred to people particularly adept at arithmetic who would perform long and involved rote calculations for scientists engineers and accountants. These computers would often exploit symmetries in order to save time and effort much as a contemporary programmer exploits them to reduce electronic computer run-time and memory. The basic principle of the FFT ensues from the search for such time-saving mechanisms but its discovery also encouraged the development of DSP hardware. Today s DSP chips and special-purpose FFT processors are children of both the microprocessor age and of the DSP revolution that the FFT instigated. In this chapter we will discuss various algorithms for calculating the DFT all of which are known as the FFT. Without a doubt the most popular algorithms are radix-2 DIT and DIF and we will cover these in depth. These algorithms are directly applicable only for signals of length N 2m but with a little ingenuity other lengths can be accommodated. Radix-4 split radix and FFT842 are even faster than basic radix-2 while mixed-radix and prime factor algorithms directly apply to N that are not powers of two. There are special cases where the fast Fourier transform can be
