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

multiplications. For a data length of N , the number of complex multiplications for DFT and FFT,
respectively, are determined by

2

Complex multiplications of DFT ¼ N ; and

Complex multiplications of FFT ¼ 2 log 2 ðNÞ
To see the effectiveness of FFT, let us consider a sequence with 1,024 data points. Applying DFT
will require 1 ; 024 1 ; 024 ¼ 1 ; 048 ; 576 complex multiplications; however, applying FFT will
require only ð 1024 = 2 Þ log 2 ð 1 ; 024 Þ¼ 5 ; 120 complex multiplications. Next, the index (bin
number) of the eight-point DFT coefficient XðkÞ becomes0,4,2,6,1,5,3,and7,respectively,
which is not the natural order. This can be fixed by index matching. The index matching between
the input sequence and output frequency bin number by applying reversal bits is described in
Table 4.2 .
Figure 4.36 explains the bit reversal process. First, the input data with indices 0, 1, 2, 3, 4, 5, 6, 7 are
split into two parts. The first half contains even indices d 0, 2, 4, 6 d while the second half contains odd
indices. The first half with indices 0, 2, 4, 6 at the first iteration continues to be split into even indices 0,
4 and odd indices 2, 6 as shown in the second iteration. The second half with indices 1, 3, 5, 7 at the
first iteration is split to even indices 1, 5 and odd indices 3, 7 in the second iteration. The splitting
process continues to the end at the third iteration. The bit patterns of the output data indices are just the
respective reversed bit patterns of the input data indices.
Although Figure 4.36 illustrates the case of an eight-point FFT, this bit reversal process works as
long as N is a power of 2.
The inverse FFT is defined as

N 1
k ¼ 0 XðkÞW k N ¼

N 1
k ¼ 0 XðkÞ W kn

1
N

1
N

xðnÞ¼

N ;

for k ¼ 0 ; 1 ; / ; N 1 (4.45)

Table 4.2 Index Mapping for Fast Fourier Transform
Input Data

Index Bits Reversal Bits Output Data

000 000

xð 0 Þ Xð 0 Þ

001 100

xð 1 Þ Xð 4 Þ

010 010

xð 2 Þ Xð 2 Þ

011 110

xð3Þ Xð6Þ

100 001

xð4Þ Xð1Þ

101 101

xð5Þ Xð5Þ

110 011

xð6Þ Xð3Þ

111 111

xð 7 Þ Xð 7 Þ