4.4 Numerical Computation in Frequency Domain
149
Equation (3.122) can be replaced by the following finite sum
F(ω n ) = t
n − 1
n = 0
F(t m ) e
(−2πinm/N )
(4.51)
Equations (4.50) and (4.51) are defined as discrete Fourier transform (DFT) pairs.
They correspond to the transforms given by. Equations (3.124) and (3.125).
4.4.2 Fast Fourier Transform (FFT)
FFT is a computer algorithm for calculating DFTs. The DFT of a finite sequence
{F(t m )}, m = 0, 1, 2, . . . , (N − 1) is a new finite sequence {F(ω n )} defined
by (from Eq. [4.51]).
F(ω n ) =
T
N
N − 1
m = 0
F(t m ) e
i(−2nnm/N )
(4.52)
If we want to calculate values of F(ω n ) by a direct approach, N multiplications
of the form F(t m ) e
−i(2π nmN) for each of the N values of F(ω n ) and the total work of
calculating full sequence will require N
2 multiplications. As we shall see shortly, FFT
reduces this work to a number of operations equal to N log 2 N. IfN = 2
20 , then N
2
=
1.1 × 10
12 , whereasN log 2 N = 2.1 × 10
7 , which is only about 1/52,000th of the
number of operations. The FFT therefore offers an enormous reduction of computer
time. Further, the number of operations being performed by the computer being less,
round-off errors due to truncation will be less and accuracy will be increased.
The FFT works by partitioning full sequence {F(ω n )} into a number of shorter
sequences. Instead of computing the DFT of the original sequence, only the DFTs
of the shorter sequences are worked out. These are combined in an ingenious way to
yield full DFT of F(ω n ).
In FFT, full sequence of F(t m ) will be partitioned into a number of shorter
sequences. Instead of calculating DFTs for the original sequence, only the DFTs
of the shorter sequences are to be calculated. As to how the DFTs of the shorter
sequences are combined to yield the full DFT is explained below, and this is the
technique of FFT.
F(t m ) is written singly as F m in short. {F m }, m = 0, 1, 2, (N − 1) is a sequence
shown in Fig. 4.7a, where N is even. This is partitioned into two shorter sequences
{y m } and {z m } where
y m = F 2m
z m = F 2m + 1
⎫
⎪ ⎬
⎪ ⎭
m = 0, 1, 2, . . . ,
N
2
− 1
(4.53)
149
Equation (3.122) can be replaced by the following finite sum
F(ω n ) = t
n − 1
n = 0
F(t m ) e
(−2πinm/N )
(4.51)
Equations (4.50) and (4.51) are defined as discrete Fourier transform (DFT) pairs.
They correspond to the transforms given by. Equations (3.124) and (3.125).
4.4.2 Fast Fourier Transform (FFT)
FFT is a computer algorithm for calculating DFTs. The DFT of a finite sequence
{F(t m )}, m = 0, 1, 2, . . . , (N − 1) is a new finite sequence {F(ω n )} defined
by (from Eq. [4.51]).
F(ω n ) =
T
N
N − 1
m = 0
F(t m ) e
i(−2nnm/N )
(4.52)
If we want to calculate values of F(ω n ) by a direct approach, N multiplications
of the form F(t m ) e
−i(2π nmN) for each of the N values of F(ω n ) and the total work of
calculating full sequence will require N
2 multiplications. As we shall see shortly, FFT
reduces this work to a number of operations equal to N log 2 N. IfN = 2
20 , then N
2
=
1.1 × 10
12 , whereasN log 2 N = 2.1 × 10
7 , which is only about 1/52,000th of the
number of operations. The FFT therefore offers an enormous reduction of computer
time. Further, the number of operations being performed by the computer being less,
round-off errors due to truncation will be less and accuracy will be increased.
The FFT works by partitioning full sequence {F(ω n )} into a number of shorter
sequences. Instead of computing the DFT of the original sequence, only the DFTs
of the shorter sequences are worked out. These are combined in an ingenious way to
yield full DFT of F(ω n ).
In FFT, full sequence of F(t m ) will be partitioned into a number of shorter
sequences. Instead of calculating DFTs for the original sequence, only the DFTs
of the shorter sequences are to be calculated. As to how the DFTs of the shorter
sequences are combined to yield the full DFT is explained below, and this is the
technique of FFT.
F(t m ) is written singly as F m in short. {F m }, m = 0, 1, 2, (N − 1) is a sequence
shown in Fig. 4.7a, where N is even. This is partitioned into two shorter sequences
{y m } and {z m } where
y m = F 2m
z m = F 2m + 1
⎫
⎪ ⎬
⎪ ⎭
m = 0, 1, 2, . . . ,
N
2
− 1
(4.53)