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

Table 12.3. Comparison of the computational complexities of the
time-domain versus the DFT-based approaches used to compute
the linear convolution

Computational complexity, flops

Length K 1 Length K 2 Time domain DFT

of x 1 [ k ] o f x 2 [ k ] ( 2 K 1 K 2 flops) (15 K log 2 K flops)

32 5 320 5760

32 32 2048 5760

1000 200 400 000 337 920

1000 1000 2 000 000 337 920

2000 2000 8 000 000 737 280

12.6 Fast Fourier tr ansform

There are several well known techniques including the radix-2, radix-4, split
radix, Winograd, and prime factor algorithms that are used for computing the
DFT. These algorithms are referred to as the fast Fourier transform (FFT) algo-
rithms. In this section, we explain the radix-2 decimation-in-time FFT algo-
rithm.
To provide a general frame of reference, let us consider the computational
complexity of the direct implementation of the K -point DFT for a time-limited
complex-valued sequence x [ k ] with length K . Based on its definition,

K − 1

− j(2 π kr / K ) ,

X [ r ] = x [ k ]e (12.30)

k = 0

K complex multiplications and K − 1 complex additions are required to com-
pute a single DFT coefficient. Computation of all K DFT coefficients requires
approximately K 2 complex additions and K 2 complex multiplications, where
we have assumed K to be large such that K − 1 ≈ K .
In terms of flops, each complex multiplication requires four scalar multi-
plications and two scalar additions, and each complex addition requires two
scalar additions. Computation of a single DFT coefficient, therefore, requires
8 K flops. The total number of scalar operations for computing the complete
DFT is given by 8 K 2 flops.
We now proceed with the radix-2 FFT decimation-in-time algorithm. The
radix-2 algorithm is based on the following principle.

Proposition 12.1 For even values of K, the K-point DFT of a complex-valued
sequence x [ k ] with length K can be computed from the DFT coefficients of two
subsequences: (i) x [ 2k ] , containing the even-numbered samples of x [ k ] , and
(ii) x [2 k + 1] , containing the odd-numbered samples of x [ k ] .