Discrete Fourier transform - Continuous and Discrete Time Signals and Systems - page 552

we assume that x 1 [ k ] and x 2 [ k ] are real-valued sequences with lengths K 1 and
K 2 , respectively.

Time-domain approach This is based on the direct computation of the con-
volution sum

∞

y [ k ] = x 1 [ k ] ∗ x 1 [ k ] = x 1 [ m ] x 2 [ k − m ] ,

m =−∞

which requires roughly K 1 K 2 multiplications and K 1 K 2 additions. The
total number of floating point operations (flops) required with the time-domain
approach is therefore given by 2 K 1 K 2 .

DFT-based approach Step 1 of the DFT-based approach computes two K =
( K 1 + K 2 − 1)-point DFTs of the DT sequences x 1 [ k ] and x 2 [ k ]. In Section
12.6, we show that the total number of flops required to implement a K -point
DFT using fast Fourier transform (FFT) techniques is approximately 5 K log 2 K .
Therefore, Step 1 of the DFT-based approach requires a total of 10 K log 2 K
flops.
Step 2 multiplies DFTs for x 1 [ k ] and x 2 [ k ]. Each DFT has a length of
K = K 1 + K 2 − 1 points; therefore, a total of K complex multiplications and
K − 1 ≈ K complex additions are required. The total number of computations
required in Step 2 is therefore given by 8 K or 8( K 1 + K 2 - 1) flops.

Step 3 computes one inverse DFT based on the FFT implementation requiring
5 K log 2 K flops.
The total number of flops required with the DFT-based approach is therefore
given by

15 K log 2 K + 6 K ≈ 15 K log 2 K flops ,

where K = K 1 + K 2 − 1. Assuming K 1 = K 2 , the DFT-based approach pro-
vides a computational saving of O((log 2 K ) / K ) in comparison with the direct
computation of the convolution sum in the time domain. Table 12.3 compares
the computational complexity of the two approaches for a few selected values
of K 1 and K 2 . The length K of the DFT should be equal to or greater than
( K 1 + K 2 − 1) depending on its value. Where ( K 1 + K 2 − 1) is not a power of
2, we have rounded ( K 1 + K 2 − 1) to the next higher integer that is a power of 2.
In the second row, for example, K 1 = 32 and K 2 = 5, which implies that ( K 1 +
K 2 − 1) = 36. Since the radix-2 FFT algorithm, described in Section 12.6, can
only be implemented for sequences with lengths that are powers of 2, K is set to
64. Based on the DFT-based approach, the number of flops required to compute
the convolution of the two sequences is given by (15 64 log 2 (64)) = 5760.
In Table 12.3, we observe that for sequences with lengths greater than 1000 sam-
ples, the DFT-based approach provides significant savings over the direct com-
putation of the circular convolution in the time domain. If x 1 [ k ] and x 2 [ k ] are
real-valued sequences, significant further savings (about 50%) can be achieved
using the procedures mentioned in Problems 12.18 and 12.19.