Signals and Systems - Electrical Engineering

716 CHAPTER 12: Applications of Discrete-Time Signals and Systems

the same locations. Since X[k]is typically complex, to have identical allocation with the output, the input

sequence x[n]is assumed to be complex. If x[n]is real, it is possible to transform it into a complex sequence

and use properties of the DFT to obtain X[k].

12.2.3 General Approach of FFT Algorithms

Although there are many algorithmic approaches to the FFT, the initial idea was to represent the

finite one-dimensional signalx[n] as a two-dimensional array. This can be done by representing the

lengthNofx[n] as the product of smaller integers, providedNis not prime. IfNis prime, the DFT

computation is done with the conventional formula, as the FFT does not provide any simplification.

However, in that case we could attach zeros to the signal (if the signal is not periodic) to increase

its length to a nonprime number. This factorization approach has historic significance as it was the

technique used by Cooley and Tukey, the authors of the FFT.

SupposeNcan be factored asN=pq; then the frequency and time indiceskandnin the direct DFT

can be written as

k=k 1 p+k 0 for k 0 =0,...,p−1,k 1 =0,...,q− 1

n=n 1 q+n 0 forn 0 =0,...,q−1,n 1 =0,...,p− 1

The values ofkrange from 0 (whenk 0 =k 1 =0) toN−1 (whenk 1 =q−1 andk 0 =p−1 then

k=k 1 p+k 0 =(q− 1 )p+(p− 1 )=qp− 1 =N−1). Likewise forn. The direct DFT

X[k]=

N∑− 1

n= 0

x[n]Wnk

can be written to reflect the dependence on the new indices as

X[k 0 ,k 1 ]=

∑q−^1

n 0 = 0

p∑− 1

n 1 = 0

x[n 0 ,n 1 ]WN(n^1 q+n^0 )(k^1 p+k^0 ) (12.9)

giving a two-dimensional array.

The decimation-in-time FFT presented before may be viewed in this framework by lettingq=2 and

p=N/2, where as beforeN= 2 γis even. We then have usingW

2 n 1 (k 1 p+k 0 )

N =W

n 1 (k 1 p+k 0 )

N/ 2 ,

X[k 0 ,k 1 ]=

∑^1

n 0 = 0

WnN^0 (k^1 p+k^0 )

N∑/ 2 − 1

n 1 = 0

x[n 0 ,n 1 ]WNn^1 /( 2 k^1 p+k^0 )

=

N∑/ 2 − 1

n 1 = 0

x[0,n 1 ]WNn^1 /( 2 k^1 p+k^0 )+WN(k^1 p+k^0 )

N∑/ 2 − 1

n 1 = 0

x[1,n 1 ]WNn^1 /( 2 k^1 p+k^0 )

=Y[k]+WN(k^1 p+k^0 )Z[k] k 0 =0,...,N/ 2 −1,k 1 =0, 1 (12.10)

where whenn 0 =0 the even terms (x[0,n 1 ]=x[qn 1 ]=x[2n 1 ]) in the input are being transformed,

while when n 0 =1 the odd terms (x[1,n 1 ]=x[qn 1 +1]=x[2n 1 +1]) of the input are being