The FFT is an algorithm which vastly reduces the amount of processing necessary to form a bank of digital filters with the DFT. Its efficiency is achieved primarily by choosing the parameters of the bank so that they are harmonically related and consolidating the formation of the filters into a single multiple-step process. By making the number of filters, N, equal to a power of two and the number of samples summed equal to N, the processing is accomplished in log₂N steps. In the first step, each sample is algebraically summed with one of the other samples. In each succeeding step, certain phase rotations are performed, and each partial sum is algebraically summed with one of the other partial sums.The required phase rotations and pairing of the quantities to be summed in each step can readily be determined mathematically. The basic processing instruction for performing the individual partial summations - consisting of a phase rotation, a complex addition, and a complex subtraction - is called the FFT butterfly. The phase rotations themselves are performed the same way as in the DFT.

Chapter Contents:

• Basic Concept
• A Representative FFT
• FFTs for Filter Banks of Any Size
• Rules of Thumb for Estimating Number of Computations

Inspec keywords: discrete Fourier transforms; digital filters

Other keywords: digital filter bank; partial summation; complex subtraction; DFT; FFT; complex addition; phase rotation

Subjects: Integral transforms; Digital filters; Integral transforms; Digital filters