4.4 Numerical Computation in Frequency Domain
151
or
F(ω n ) =
1
2
Y n + e
−i(2πn/N ) Z n
(4.55)
for n = 0, 1, 2, . . . ,
N
2
− 1
It is thus seen that the DFTs of the original sequence is obtained from the two
half-sequence of Y n and Z n directly. Thus, Eq. (4.55) forms the very basis of the
FFT method. The half-sequences of {Y m } and {Z m } may further be partitioned into
quarter-sequences and so on, till the last sequence may contain only one term.
Equation (4.55) indicates that F(ω n ) can be calculated for0 < n <
N
2
− 1,,
i.e. only half of the coefficients of F(ω n ) can thus be obtained, But F(ω n ) need to
be calculated for the values of n from
N
2
to (N − 1). In order to do that, advantage
may be taken of the fact that Y n and Z n are periodic in n and repeat themselves with
period N/2, so that
Y n − N /2 = Y n
Z n − N /2 = Z n
(4.56)
Therefore, computation of all values of F(ω n ) can be done as follows:
F(ω n ) =
1
2
Y n + e
−i(2πn/N ) Z n
for n = 0, 1, 2, ... ,
N
2
− 1
F(ω n ) =
1
2
Y n − N /2 + e
−i(2πn/N ) Z n − N /2
(4.57)
for n =
N
2
,
N
2
+ 1, · · · , (N − 1).
Equation (4.57) can also be written as
F (ω n ) =
1
2
Y n + e
−i(2πn/N ) Z n
F
ω n + N /2
=
1
2
Y n + e
−i(2π/N ) (n + N /2) Z n
(4.58)
where n = 0, 1, 2, . . . ,
N
2
− 1
.
Noting that e
−iπ
= 1
F (ω n ) =
1
2
Y n + e
−i(2πn/N ) Z n
F
ω n +
N
2
=
1
2
Y n − e
−i(2πn/N ) Z n
(4.59)
for n = 0, 1, 2, . . . ,
N
2
− 1
.
Further, we define a new complex variable as follows
W
n
N = e
−i(2πn/N )
(4.60)