Biomedical Engineering Reference
In-Depth Information
3
2
1
W
W
W
4
0
W
W
5
6
7
W
W
W
FIGURE 13.2
:
Symmetry and periodicity of
W
N
for
N
=
8
For each
k
, (13.5) needs 4
N
real multiplications and (4
N
−
2) real additions.
The computation of
x
(
k
) needs 4
N
2
real multiplications and
N
(4
N
−
2) real additions.
In terms of complex operations, there are
N
2
1)
complex additions. As
N
increases, it can be seen that the number of computations
become tremendously large. Hence, there was a need to improve the efficiency of DFT
computation and to exploit the symmetry and periodicity properties of the twiddle factor,
W
N
, as shown in (13.6) and Fig. 13.2.
complex multiplication and
N
(
N
−
N
2
W
k
+
Symmetry :
W
N
=−
N
(13.6)
Periodicity :
W
N
=
W
N
+
k
N
13.4 COOLEY-TUKEY FF T (DECIMIMATION IN TIME)
The Cooley-Tukey FFT was one of the first FFTs developed. Suppose a time series
having
N
samples is divided into two functions, of which each function has only half of the
data points (
N
/
2). One function consists of the even numbered data points (
x
0
,
x
2
,
x
4
...,
etc,), and the other function consists of the odd numbered data points (
x
1
,
x
3
,
x
5
,...,
etc.). Those functions may be written as
Y
k
=
x
2
k
;
Z
k
=
x
2
k
+
l
,
for
:
k
=
0
,
1
,
2
,...,
(
N
/
2)
−
1
Since
Y
k
and
Z
k
are sequences of
N
2 points each, the two sequences have Discrete
Fourier transforms, which are written in terms of the odd and even numbered data
points. For values of
r
greater than
N
/
/
2, the discrete Fourier transforms
Br
and
Cr
repeat
Search WWH ::
Custom Search