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

Binary index 1st split 2nd split 3rd split Bit reversal

000 0 0 0 0 000

001
010
011

1
2
3

2
4
6

4
2
6

4 100

010
011

2

6

100 4 1 1 1 001

101
110
111

5
6
7

3
5
7

5
3
7

5 101

011
111

3

7

FIGURE 4.36

Bit reversal process in FFT.

1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8

X (0
X (1

x (0
x ()

W N 0

4
x ()

W N 0

1

X () 2

2
x (6
x (1
x (5
x (3
x ()

W N 2 W N 0

1
1

X (3
X ()

W N 0
W 1
W N 2
W N 3

1

4
X (5
X (6
X ()

W N 0

1
1
1
1

W N 0

1

W N 2 W N 0

1
1

7 7

1

FIGURE 4.37

Block diagram for the inverse of eight-point FFT.

Comparing Equation (4.45) with Equation (4.33) , we notice the difference as follows: the twiddle
factor W N

W N ¼ W 1

, and the sum is multiplied by a factor of 1 =N . Hence, by
modifying the FFT block diagram as shown in Figure 4.35 , we achieve the inverse FFT block diagram
shown in Figure 4.37 .

is changed to

N

EXAMPLE 4.12
Given a sequence xðnÞ for 0 n 3, where xð0Þ¼1, xð1Þ¼2, xð2Þ¼3, and xð3Þ¼4,
a. evaluate its DFT X ðkÞ using the decimation-in-frequency FFT method;
b. determine the number of complex multiplications.
Solution:
a. Using the FFT block diagram in Figure 4.35 , the result is shown in Figure 4.38 .
b. From Figure 4.38 , the number of complex multiplications is four, which can also be determined by
N

2 log 2 ðNÞ¼ 4 2 log 2 ð4Þ¼4