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

Bit reversal
00
10
01
11

Bit index
00
01
10
11

10
2
2 2

4
6
2
2

x (01
x ()12

X (0

W 4 0 1

X () 2

1

j
2 2

W 4 0 1
Wj
4

x (23 X (1

1
1

1

W 4 0

j

1

X (3

x (34

1

FIGURE 4.38
Four-point FFT block diagram in Example 4.12.

EXAMPLE 4.13
Given the DFT sequence X ðkÞ for 0 k 3 computed in Example 4.12, evaluate its inverse DFT xðnÞ using the
decimation-in-frequency FFT method.
Solution:
Using the inverse FFT block diagram in Figure 4.37 , we have the result shown in Figure 4.39 .

Bit index
00
01
10
11

Bit reversal
00
10
01
11

1
4 8

4
12
j 4

4
12
8
16

X (0 0
X

x (01
x (23
x ()12
x (44

W 4 0 1

4
1
4
1
4

1

()122 j

W 4 0 1
~ Wj
4

1

X () 2 2

W 4 0

1
1

1

1

X ()322 j

1

FIGURE 4.39

Four-point inverse FFT block diagram in Example 4.13.

4.5.2 Decimation-in-Time Method
In this method, we split the input sequence xðnÞ into the even indexed xð 2 mÞ and xð 2 m þ 1 Þ , each with
N data points. Then Equation (4.33) becomes

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

X X

2 mk

xð 2 m þ 1 ÞW N W

2 mk

XðkÞ¼ xð 2 mÞW

N þ N ;

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

m¼ 0 m¼ 0