14 - Discrete Fourier Transform and Fast Fourier Transform

Summary

This chapter introduces the fast Fourier Transform (FFT) for discrete Fourier Transform, beginning with the discretization of the Fourier Transform to its digital expression with constant time intervals. When the integral in Fourier Transform is replaced by a summation, the continuous Fourier Transform is changed to discrete. The discrete Fourier Transform and its inverse are exact relations. An example of the discrete Fourier Transform is discussed for a simple rectangular window function which results in the sinc function, useful for the interpretation of finite sampling effect. A technique of zero-padding is introduced with the discrete Fourier Transform for better visualization of the spectrum. But the computation of discrete Fourier Transform of a long time series can be quite “labor intensive” or costly in computer time with a direct computation. However, since the base functions are periodic, a direct computation can have many duplications in multiplications of terms. Algorithms can be designed to reduce the duplications so that the speed of computation is increased. The reduction of duplicated computations can be repeatedly done through an FFT algorithm. In MATLAB, this is done by a simple command fft. The efficiency of FFT is discussed.