Digital Signal Processing 101, 2nd Edition

Chapter 10

Discrete and Fast Fourier Transforms (DFT, FFT)

Abstract

This chapter covers both discrete Fourier transform (DFT) and it's more efficient form, the fast Fourier transform (FFT). These transforms provide a means to convert time domain signals into frequency domain, and their inverse forms allow for the reversal. The DFT is covered in detail, as this is one of the most fundamental building blocks in digital signal processing. The FFT is a dramatically more efficient method to compute the DFT, and this is what is used in practice. Practical implementation issues such as bit growth as well as bit reversal addressing are also discussed.

Keywords

Butterfly; DFT; FFT; Frequency spectrum; IFFT; Twiddle factors

Many of us have heard the term “FFT.” ...