Signals and Systems - Electrical Engineering

12.2 Application to Digital Signal Processing 713

whereIN/ 2 is a unit matrix andN/ 2 is a diagonal matrix with entries{WNk,k=0,...,N/ 2 − 1 }; both
matrices have dimensionN/ 2 ×N/2. The vectorsXN,YN/ 2 , andZN/ 2 contain the coefficients ofx[n],
y[n], andz[n].

Repeating the above computation forY[k] andZ[k] we can express it in a similar matrix form until
we reduce the process to 2×2 matrices. While performing these computations, the ordering ofx[n]
is changed. This scrambling ofx[n] is obtained by a permutation matrixPN(with 1 and 0 entries
indicating the resulting ordering of thex[n] samples). IfN= 2 γ, theXNvector, containing the DFT
termsX[k], is obtained as the product ofγmatricesAiand the permutation matrix. That is,

XN=

[γ

∏

i= 1

Ai

]

PNx x=[x[0],...,x[N−1]]T (12.7)

whereTstands for transpose. Given the large number of 1s and 0s in the{Ai}and thePNmatrices,
the number of additions and multiplications is much lower than those in the original formulas.
The number of operations is found to be of the order ofNlog 2 N=γN, which is much smaller
than the original number of orderN^2. For instance, ifN= 210 =1024, the number of additions and
multiplications for the computation of the DFT from its original formula isN^2 = 220 =1,048,576,
while the FFT computation requiresNlog 2 N= 1024 × 10 =10,240—that is, the FFT requires about
1% of the number of operations required by the original formula for the DFT.

nExample 12.1

Consider the decimation-in-time FFT algorithm forN=4. Give the equations to compute the four

DFT valuesX[k],k=0,..., 3 in matrix form.

Solution

If we compute the DFT ofx[n] directly we have that

X[k]=

∑^3

n= 0

x[n]Wnk 4 k=0,..., 3

which can be rewritten in the matrix form as









X[0]

X[1]

X[2]

X[3]







=









1 1 1 1

1 W 41 W 42 W 43

1 W 42 1 W 42

1 W 43 W 42 W 41

















x[0]

x[1]

x[2]

x[3]









where we used

W 44 =W^44 +^0 =e−j^2 π^0 /^4 =W 40 = 1

W 46 =W^44 +^2 =e−j^2 π^2 /^4 =W 42

W 49 =W^44 +^4 +^1 =e−j^2 π^1 /^4 =W 41