Discrete Fourier Transform and Signal Spectrum - Digital Signal Processing: Fundamentals and Applications - page 123

4.5 FAST FOURIER TRANSFORM
Now we study FFT in detail. FFT is a very efficient algorithm in computing DFT coefficients and can
reduce a very large amount of computational complexity (multiplications). Without loss of generality,
we consider the digital sequence xðnÞ consisting of 2 m samples, where m is a positive integer, that is,
the number of samples of the digital sequence xðnÞ is a power of 2, N ¼ 2 ; 4 ; 8 ; 16 ; etc. If xðnÞ does
not contain 2 m samples, then we simply append it with zeros until the number of the appended
sequence is a power of 2.
In this section, we focus on two formats. One is called the decimation-in-frequency algorithm,
while the other is the decimation-in-time algorithm. They are referred to as the radix-2 FFTalgorithms.
Other types of FFT algorithms are the radix-4 and the split radix and their advantages can be explored
in more detail in other texts (see Proakis and Manolakis, 1996).

4.5.1 Decimation-in-Frequency Method
We begin with the definition of DFT studied in the opening section in this chapter:

N 1
n¼ 0 xðnÞW k N

XðkÞ¼ for k ¼ 0 ; 1 ; / ; N 1 (4.33)

where W N ¼ e j

2 p
N is the twiddle factor, and N ¼ 2 ; 4 ; 8 ; 16 ; / . Equation (4.33) can be expanded as

XðkÞ¼xð 0 Þþxð 1 ÞW N þ / þ xðN 1 ÞW kðN 1 Þ (4.34)

N

Again, if we split Equation (4.34) into

2 1

W kðN= 2 1 Þ
N

XðkÞ¼xð 0 Þþxð 1 ÞW N þ / þ x

(4.35)

2

þ / þ xðN 1 ÞW kðN 1 Þ W kN= 2

þx

N

then we can rewrite it as a sum of the following two parts:

ðN= 2 Þ 1

X N 1

n¼N= 2 xðnÞW k N

xðnÞW k N þ XðkÞ¼ (4.36)

n¼ 0

Modifying the second term in Equation (4.36) yields

ðN= 2 Þ 1 ðN= 2 Þ 1

X X

n þ 2

xðnÞW k N þ W ðN= 2 Þk

W k N XðkÞ¼ x (4.37)

N

n¼ 0 n¼ 0