Biomedical Engineering Reference
In-Depth Information
Their algorithm makes use of the fact that e
−
2
πj/N
is symmetrical and the
number of computations can be reduced from
N
2
to
N
log
2
N
. The original
algorithm is applicable only when
N
is an integer power of 2. There are, how-
ever, more recent algorithms, which improve on the original algorithm (Stein,
2000; Oppenheim et al., 1999) by decomposing the DFT into smaller Fourier
transforms and are known as
decimation in time
and
decimation in frequency
algorithms. We describe the decimation in time algorithm here because the
decimation in frequency shares the same principle with the exception that
it is in frequency domain. Further details can be found in references such as
Oppenheim et al. (1999) and Stein (2000).
The decimation in time algorithm decomposes the time sequence
x
(
n
)into
two terms, one containing the “even” terms and the other the “odd” terms
corresponding to values of
n
. The DFT sequence is usually rewritten as
N
x
(
n
)
W
n
N
X
(
k
)=
(2.23)
n
=1
for
n
=
k
=1
,...,N
and
W
n
N
=e
−jω
k
n
.Nowif
N
=2
p
, we can rewrite Equa-
tion 2.23 as
N
N
x
(
n
)
W
n
N
+
x
(
n
)
W
n
N
X
(
k
)=
(2.24)
n
=2
j
n
=2
j
+1
for
j
=1
,...,
2
or equivalently as
N
2
N
2
x
(2
n
+1)
W
(2
n
+1)
k
N
x
(2
n
)
W
2
nk
N
X
(
k
)=
+
n
=1
n
=1
N
2
N
2
x
(2
n
)
W
2
nk
N
+
W
N
x
(2
n
+1)
W
2
nk
N
=
(2.25)
n
=1
n
=1
This scheme works principally for even sequence lengths but if the sequence
length is odd, an augmenting zero term is usually added to make it even.
Equation 2.25 can be further reduced to
X
(
k
)=
X
e
(
k
)+
W
N
X
o
(
k
)
(2.26)
where
X
e
(
k
) is the DFT of the even terms and
X
o
(
k
) the DFT of the odd
terms. This algorithm is also known as the Cooley-Tukey algorithm and is
best illustrated by a sample computation of DFT for eight samples.
Let the discrete signal
X
contain the following samples:
X
(
k
)=
{x
0
,x
1
,x
2
,x
3
,x
4
,x
5
,x
6
,x
7
}
Then form the DFT as in Equation 2.26 to obtain
X
(
k
)=
X
e
1
(
k
)+
W
N
X
o
1
(
k
)
(2.27)
Search WWH ::
Custom Search