Fast Fourier Transform - Signal Processing of Random Physiological Signals - page 155

x (0) W 0 x (1) W 6 x (2) W 12 x (3) W 18 x (4) W 24 x (5) W 30 x (6) W 36 X (6) = + + + + + +

x (7) W 42 + = (1 + j × 0) + (0 + j × 0) + (0 + j × 0) + (0 + j × 0)

+ ( − 1 + j × 0) + (0 + j × 0) + (0 + j × 0) + (0 + j × 0) = 0 + j × 0

x (0) W 0 x (1) W 7 x (2) W 14 x (3) W 21 x (4) W 28 x (5) W 35 x (6) W 42

X (7) = + + + + + +

x (7) W 49 + = (1 + j × 0) + (0 . 5 + j × 0) + (0 + j × 0) + (0 . 5 + j × 0)

+ (1 + j × 0) + (0 . 5 + j × 0) + (0 + j × 0) + (0 . 5 + j × 0) = 0 + j × 0

13.6.5 The DF T by FF T Method

N − 1 7

e − j 2 π x ( n ) W n N x ( n ) W n 8 ;

X ( k ) = = W 8 = ; k = 0 , 1 ,... 7

8

n = 0 n = 0

3 3

e − j 2 π x (2 n ) W nk W 8 1) W nk = + x (2 n + ; W 4 = ; k = 0 , 1 ,... 3

4

4 4

n = 0 n = 0

1 1

x (4 n ) W nk W 4 2) W nk = + x (4 n +

2 2

; W 2

n = 0 n = 0

1 1

e − j 2 π W 8 1) W nk W 4 3) W nk + x (4 n + + x (4 n + = ; k = 0 , 1

2

2 2

n = 0 n = 0

Periodicity property of Twiddle factor used in the FFT implies:

W N W N + K

N

W 8 W 8+ K

N

= or =

0

W 8 . Therefore, one needs to calculate the twiddle factor for W →

8

13.7 SUMMARY
In summary, the usefulness of the FFT is the same as the DFT in Power Spectral Analysis
or Filter Simulation on digital computers; however, the FFT is fast and requires fewer
computations than the DFT. Decimation-in-time is the operation of separating the
input data series, x ( n ) into two N 2 length sequences of even-numbered points and of

odd-numbered points, which can be done as long as the length is an even number, i.e., 2
to any power. Results of the decimation in the FFT are better shown with the “Butterfly”

/