Information Technology Reference
In-Depth Information
the N-point DFT can be expressed in terms of the DFT's of the decimated
sequences shown in Equation 19.5.
X
ð
k
Þ¼
X
N
1
x
ð
n
Þ
W
k
N
;
k
¼
0
;
; ...;
N
1
1
n
¼
0
X
x
ð
n
Þ
W
k
N
þ
X
n
x
ð
n
Þ
W
k
N
¼
ð
19
:
5
Þ
n
even
odd
ð
N
=
2
Þ
1
X
þ
X
ð
N
=
2
Þ
1
x
ð
2m
þ
1
Þ
W
k
ð
2m
þ
1
Þ
N
x
ð
2m
Þ
W
2mk
N
¼
m
¼
0
m
¼
0
But W
N
2
=W
N/2
. With this substitution, Equation 19.5 can be expressed as
X
ð
k
Þ¼
X
ð
N
=
2
Þ
1
f
1
ð
m
Þ
W
k
N
=
2
þ
W
N
X
ð
N
=
2
Þ
1
f
2
ð
m
Þ
W
k
N
=
2
;
ð
19
:
6
Þ
m
¼
0
m
¼
0
¼
F
1
ð
k
Þþ
W
N
F
2
ð
k
Þ;
k
¼
0
;
1
; ...;
N
1
where F
1
(k) and F
2
(k) are the N/2-point DFTs of the sequences f
1
(m)andf
2
(m),
respectively.
Since F
1
(k)andF
2
(k) are periodic, with period N/2, we have F
1
(k+N/2)=F
1
(k)
and F
2
(k+N/2)=F
2
(k). In addition, the factor W
N
k+N/2
=
W
N
k
. Hence Equation
19.6 (called butterfly computation) may be expressed as
N
2
1
X
ð
k
Þ¼
F
1
ð
k
Þþ
W
N
F
2
ð
k
Þ;
k
¼
0
;
1
; ...;
¼
F
1
ð
k
Þ
W
N
F
2
ð
k
Þ;
2
1
:
ð
19
:
7
Þ
N
2
N
Xk
þ
k
¼
0
;
1
; ...;
This method is illustrated in Figure 19.5.
We observe that the direct computation of F
1
(k) requires (N/2)
2
complex
multiplications. The same applies to the computation of F
2
(k). Furthermore, N/2
additional complex multiplications are required to compute W
N
k
F
2
(k). Hence, the
computation of X(k) requires 2(N/2)
2
+N/2=N
2
/2+N/2 complex multiplications.
This first step results in a reduction of the number of multiplications from N
2
to
N
2
/2+N/2, which is about a factor of 2 for N large. Note that these results are
based on radix-2 decomposition; however it can be repeated for N/4, N/8,
y
1
points to implement radix-4, radix-8, radix-2
n
FFT.
Search WWH ::
Custom Search