12.2 Application to Digital Signal Processing 715which in matrix form is
Y[0]
Y[1]
···
Z[0]
Z[1]
=
1 1
. 0 0
1 − 1
. 0 0
··· ··· ··· ··· ···
0 0
. 1 1
0 0
. 1 − 1
x[0]
x[2]
···
x[1]
x[3]
=A 2
x[0]
x[2]
x[1]
x[3]
where we replacedW 21 =e−j^2 π/^2 =−1. Notice the change in the ordering of the{x[n]}.Reordering thex[n] entries we have
x[0]
x[2]
x[1]
x[3]
=
1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
x[0]
x[1]
x[2]
x[3]
=P^4
x[0]
x[2]
x[1]
x[3]
which finally gives
X[0]
X[1]
X[2]
X[3]
=A^1 A^2 P^4
x[0]
x[1]
x[2]
x[3]
The count of multiplications is now much lower given the number of 1s and 0s. The complex
additions and multiplications are now 10 (2 complex multiplications and 8 complex additions) if
we do not count multiplications by 1 or−1. Half of what it was before! n12.2.2 Computation of the Inverse DFT
The FFT algorithm can be used to compute the inverse DFT without any changes in the algorithm.
Assuming the inputx[n] is complex (x[n] being real is a special case), the complex conjugate of the
inverse DFT equation, multiplied byN, is
Nx∗[n]=N∑− 1
k= 0X∗[k]Wnk (12.8)Ignoring that the right term is in the frequency domain, we recognize it as the DFT of a sequence
{X∗[k]}and it can be computed using the FFT algorithm discussed before. The desiredx[n] is thus
obtained by computing the complex conjugate of Equation (12.8) and dividing it byN. As a result,
the same algorithm, with the above modification, can be used to compute both the direct and the
inverse DFTs.
RemarkIn the FFT algorithm the 2 N memory allocations for the complex input (one allocation for the real
part and another for the imaginary part of the input) are the same ones used for the output. Each step uses