Page 377 - Matrix Analysis & Applied Linear Algebra

5.8 Discrete Fourier Transform 373

Fast Fourier Transform
r
For a given input vector x containing n =2 components, the discrete
Fourier transform F n x is the result of successively creating the following
arrays.

X 1×n ←− rev(x) (bit reverse the subscripts)
For j =0, 1, 2, 3,. . . ,r − 1
1
 
e −πi/2 j
 
 −2πi/2 j  j+1 th
e
  (Half of the (2 ) roots of 1,
D ←−  −3πi/2 j 
 e  perhaps from a lookup table)
 . 
.
 . 
j
e −(2 −1)πi/2 j
2 j ×1

X (0) ←− X ∗0 X ∗2 X ∗4 ··· X ∗2 r−j −2
2 j ×2 r−j−1

X (1) ←− X ∗1 X ∗3 X ∗5 ··· X ∗2 r−j −1
2 j ×2 r−j−1
X + D × X Define × to mean

(0) (1)
X ←−
X (0) − D × X (1) [D × M] ij = d i m ij
2 j+1 ×2 r−j−1
Example 5.8.5
 
x 0
Problem: Perform the FFT on x =  x 1  .
x 2
x 3
x 3 ) .
Solution: Start with X ←− rev(x)=( x 0 x 2 x 1
For j =0:

D ←− (1) (Half of the square roots of 1)
X (0) ←− ( x 0 x 1 )
X (1) ←− ( x 2 x 3 ) and D × X (1) ←− ( x 2 x 3 )
X + D × X x 0 + x 2 x 1 + x 3

(0) (1)
X ←− (0) (1) =
X − D × X x 0 − x 2 x 1 − x 3