Digital Signal Processing and Applications with the OMAP-L138 eXperimenter

Chapter 5

Fast Fourier Transform

• The fast Fourier transform (FFT) using radix-2 and radix-4
• Decomposition in time and in frequency
• Program examples using C code
• Frame-based processing

5.1 INTRODUCTION

Fourier analysis describes the transformations between time and frequency domain representations of signals. Four different forms of Fourier transformation (the Fourier transform (FT), the Fourier Series (FS), the discrete-time Fourier transform (DTFT) and the discrete Fourier transform (DFT)) are applicable to different classes of signal according to whether, in either domain, they are discrete or continuous and whether they are periodic or a periodic. The DFT is the form of Fourier analysis applicable to signals that are discrete and periodic in both domains, that is, it transforms a discrete, periodic, time domain sequence into a discrete, periodic, frequency domain representation. A periodic signal may be characterized entirely by just one cycle; if that signal is discrete, then one cycle comprises a finite number of samples. Hence, both forward and inverse DFTs are described by finite summations as opposed to infinite summations or integrals. This is very important in digital signal processing since it means that it is practical to compute the DFT using a digital signal processor or digital hardware.

The fast Fourier transform is a computationally efficient algorithm for computing the DFT. It requires fewer multiplications than a more straightforward programming implementation ...