Sequence Analysis II: Optimal Filtering and Spectral Analysis
File last modified 9 October 1996
7.2 The Fast Fourier Transform (FFT)
We're sure you've heard of the Fast Fourier Transform. It is the swiss army knife of numerical algorithms. It slices, it dices, it even minces. We are not going to tell you how to write the MATLAB code to do an FFT. We will, however, tell you briefly how it is used, and point out why it's such a big deal.
You actually have a prescription for computing the Fourier Transform of
a function. It involves a convolution which requires of order
N2 multiplications. For a series of 1000 points, this
amounts to about a million operations. For really long
series, this could become computationally very expensive. The
Fast Fourier Transform was discovered in the 1940s but
did not become generally known until the 1960s. Rather than requiring
order N2 operations, the FFT requires only Nlog2N
operations. For a time series of a thousand points, this results
in a savings in computer time of approximately a factor of a
hundred. For a series of a million points, the savings is a factor
of 50,000. The latter would correspond to the difference between
4 seconds for your result and waiting two days!
The one requirement is that the length of your data array is an integral power of two. This means that your data array must be of length 2, 4, 8, ….., 512, 1024, 2048, … 65536 … 1048576 … etc. That is, N = 2n where n is an integer. This is a result of the underlying nature of the algorithm. You may think this terribly restrictive, and it is, but there are ways out of the problem. You can always pad the end of your data set with zeros (not a bad thing to do), or throw out those few extra points that extend beyond the nearest boundary (not a fun thing to do). Well, if you have a million points, then a few thousand points here or there won't make a difference anyway. The computational savings may be sufficient to warrant that choice. If you have just a few thousand data points, then why not just use the plain old, vanilla, Slow Fourier Transform.
MATLAB implements the FFT in an interesting way. You can invoke it simply with
Y = fft(y);
If the length of your vector "y" is an integral power of two, then MATLAB uses FFT. If it is not, then MATLAB uses the slow way instead. If you want, you can insist that MATLAB uses the FFT algorithm even when the length isn't an integral power of two. You just invoke the function as
Y=fft(y,n);
where "n" is some integral power of two closest in size to your vector length. If it exceeds your vector length, MATLAB pads it with zeros before doing the FFT. If it is smaller, it chops it. For example, if your vector is 1000 elements long, you might try
Y=fft(y,1024);
since 1024 is the closest radix-2 number to 1000. The inverse transform is obtained from
y=ifft(Y);
where you again have the option of specifying a length different
from your input vector.
GoTo Next Section
GoTo Lecture TOC
GoTo 12.747 TOC