522 A Computational Introduction to Digital Image Processing, Second Edition
FFT
FFT
x
7
Y
3
x
3
Y
2
x
5
Y
1
x
1
Y
0
x
6
Y
3
x
2
Y
2
x
4
Y
1
x
0
Y
0
X
7
X
6
X
5
X
4
X
3
X
2
X
1
X
0
ω
7
ω
6
ω
5
ω
4
ω
3
ω
2
ω
1
ω
0
FIGURE C.4: A butterfly diagram for an eight-element FFT
The Fast Fourier Transform 523
x
7
x
3
x
5
x
1
x
6
x
2
x
4
x
0
X
7
X
6
X
5
X
4
X
3
X
2
X
1
X
0
FIGURE C.5: A complete butterfly diagram for an eight-element FFT
524 A Computational Introduction to Digital Image Processing, Second Edition
3. Butterfly the resulting elements four at a time, using the scaling factors 1, ω, ω
2
and
ω
3
, with ω = exp(2iπ/4)
4. Butterfly the resulting elements eight at a time, using the scaling factors 1, ω, ω
2
, . . . , ω
7
,
with ω = exp(2iπ/8)
5. And so on, until we butterfly all elements together using scaling factors ω
k
, with
ω = exp(2iπ/2
n
).
In practice, an FFT program will use a divide and conquer strategy: the initial vector is
broken up into smaller vectors, the algorithm is applied recursively to these smaller vectors,
and the results “butterflied” together.
There are many other forms of the FFT, but they all work by the same basic principle
of dividing the vector into shorter lengths. Clearly we will obtain the greatest speed f or
vectors whose lengths are a power of 2 (such as in the previous examples), but we can also
apply similar schemes to other lengths.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.