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

Symmetric property of twiddle factor implies:

N
2

k +

W N = W 8 W k +4

= =− , which gives

W

N 8

0

W 8 W 8

6

W =− =− W

8 8

W 8 W 8 W 8 W 8 =− =−

13.6.1 Butterfly First-Stage Calculations

x ( 0 ) H

1

x ( 4 ) H

2

0

H 1 = x (0) + W

8 x (4)

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

0

H 2 = x (0) − W

8 x (4)

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

x ( 2 )

H
H

x ( 6 )

0

H 3 = x (2) + W

8 x (6)

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

0

H 4 = x (2) − W

8 x (6)

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

x ( 1 )

H 5

x ( 5 ) H 6

0

H 5 = x (1) + W x (5) = (0 . 707 + j × 0) + (1 + j × 0)( − 0 . 707 + j × 0) = 0 + j × 0

8

0

H 6 = x (1) − W x (5) = (0 . 707 + j × 0) − (1 + j × 0)( − 0 . 707 + j × 0)

8

= 1 . 414 + j × 0

x ( 3 ) H 7

x ( 7 ) H 8

0

=

x (3)

+

8 x (7)

= ( − 0 . 707 + × 0) + (1 + × 0)(0 . 707 + × 0) = 0 + × 0

H 7 W j j j j

0

=

x (3)

−

8 x (7)

= ( − 0 . 707 + × 0) − (1 + × 0)(0 . 707 + × 0)

H 8 W j j j

=− 1 . 414 + j × 0