12.2 Application to Digital Signal Processing 711
12.2.1 Fast Fourier Transform
Comparing the equations for the DFT and the inverse DFT, or IDFT
X[k]=
N∑− 1
n= 0
x[n]WNkn k=0,...,N− 1 (12.1)
x[n]=
1
N
N∑− 1
k= 0
X[k]WN−kn n=0,...,N− 1 (12.2)
whereWN=e−j^2 π/N, one sees a great deal of duality (more so if both the DFT and the IDFT had the
term 1/
√
Ninstead of only the 1/Nin the IDFT). SinceX[k] is complex, one can also see that one
algorithm could be used for both the direct and the inverse DFTs if we assumex[n] to be complex.
Two issues used to assess the complexity of an algorithm are:
n Total number of additions and multiplications:Typically, the complexity of a computational algo-
rithm is assessed by determining the number of additions and multiplications it requires. The
direct calculation ofX[k] using Equation (12.1) fork=0,...,N−1 requiresN×Ncomplex
multiplications, andN×(N− 1 )complex additions. Computing the number of real multiplica-
tions and real divisions needed, it is found that the total number of these operations is of the
order ofN^2.
n Storage:Besides the number of computations, the required storage is an issue of interest.
Radix 2 FFT Algorithm
In the following, we consider the basic algorithm for the FFT. We assume that the FFT length isN= 2 γ
for an integerγ >1. Excellent references on the DFT and the FFT are Briggs and Henson [10] and
Brigham [11]
The FFT algorithm:
n Uses the fundamental principle of “divide and conquer”: Dividing a problem into smaller prob-
lems with similar structure, the original problem can be successfully solved by solving each of the
smaller problems.
n Takes advantage of periodicity and symmetry properties ofWNnk:
(a) Periodicity: WNnkis periodic of periodNwith respect ton, and with respect tok—that is,
WNnk=
{
W(Nn+N)k
WnN(k+N)
(b) Symmetry:The conjugate ofWNnkis such that
[
WNnk
]∗
=W(NN−n)k=WnN(N−k)
