Signals and Systems - Electrical Engineering

12.2 Application to Digital Signal Processing 717

transformed. Sincek=k 1 p+k 0 the final equation isY[k]+WNkZ[k], which we obtained in the
decimation-in-time approach (see Eq. 12.3).

FactoringN= 2 ×N/2 corresponds to one step of the decimation-in-time method. If we factorN/ 2
asN/ 2 =( 2 )(N/ 4 ), we would obtain the second step in the decimation-in-time algorithm. IfN= 2 γ,
this process is repeatedγtimes or until the length is 2.

RemarkA dual of the decimation-in-time FFT algorithm is the decimation-in-frequency method.

The Modern FFT

A paper by James Cooley, an IBM researcher, and Professor John Tukey from Princeton University [15] describing an algo-

rithm for the machine calculation of complex Fourier series appeared inMathematics of Computationin 1965. Cooley,

a mathematician, and Tukey, a statistician, had in fact developed an efficient algorithm to compute the discrete Fourier

transform (DFT), which will be called the FFT. Their result was a turning point in digital signal processing: The proposed

algorithm was able to compute the DFT of a sequence of lengthNusingNlogNarithmetic operations, much smaller than

theN^2 operations that had blocked the practical use of the DFT. As Cooley indicated in his paper “How the FFT Gained

Acceptance” [14], his interest in the problem came from a suggestion from Tukey on lettingNbe a composite number,

which would allow a reduction in the number of operations of the DFT computation.

The FFT algorithm was a great achievement for which the authors received deserved recognition, but also benefited the

new digital signal processing area, and motivated further research on the FFT. But as in many areas of research, Cooley

and Tukey were not the only ones who had developed an algorithm of this class. Many other researchers before them had

developed similar procedures. In particular, Danielson and Lanczos, in a paper published in theJournal of the Franklin

Institutein 1942 [19], proposed an algorithm that came very close to Cooley and Tukey’s results. Danielson and Lanczos

showed that a DFT of lengthNcould be represented as a sum of twoN/2 DFTs proceeding recursively with the condition

thatN= 2 γ. Interestingly, they mention that (remember this was in 1942!):

Adopting these improvements the approximation time for Fourier analysis are: 10 minutes for 8 coefficients, 25

minutes for 16 coefficients, 60 minutes for 32 coefficients, and 140 minutes for 64 coefficients.

nExample 12.2

Consider computing the FFT of a signal of lengthN= 23 =8 using the decimation-in-time

algorithm.

Solution

LettingN=qp= 2 ×4, we then have that

X[k 0 ,k 1 ]=

∑^1

n 0 = 0

W 8 n^0 (k^1 p+k^0 )

N∑/ 2 − 1

n 1 = 0

x[n 0 ,n 1 ]Wn 41 (k^1 p+k^0 )

=

∑^3

n 1 = 0

x[0,n 1 ]W 4 n^1 (k^1 p+k^0 )+W 8 (k^1 p+k^0 )

∑^3

n 1 = 0

x[1,n 1 ]Wn 41 (k^1 p+k^0 )

where

k= 4 k 1 +k 0 fork 0 =0,..., 3,k 1 =0, 1

n= 2 n 1 +n 0 for n 0 =0, 1,n 1 =0,..., 3