FOURIER TRANSFORMS OF DISCRETE-TIME SIGNALS - Signals, Systems, and Transforms - page 627

In the next section, we study more efficient methods of computing the DFT of
discrete-time sequences.

12.5 FAST FOURIER TRANSFORM

As seen in Section 12.4, the discrete Fourier transform pair is given by

N- 1

x[n]W kn , k = 0, 1, 2, Á , N - 1

[eq(12.33)] X[k] = a

n= 0

and

N- 1

1
N a

X[k]W -kn , W N = e -j2p/N , n = 0, 1, Á , N - 1,

x[n] =

k= 0

which is readily programmed for calculation by digital computer. From inspection
of (12.33), we see that for each value of k , computation of will require N mul-
tiplications. Because and especially can have complex values, the com-
putation of an N -point DFT or the inverse DFT generally requires complex
multiplications. The thrust of this section will be to develop an algorithm to com-
pute the discrete Fourier transform more efficiently. The collection of efficient
algorithms that are generally used to compute the discrete Fourier transform is
known as the fast Fourier transform (FFT) [6].

X[k]

x[n], X[k],

N 2

Decomposition-in-Time Fast Fourier Transform Algorithm

We next develop an efficient algorithm for computing the discrete Fourier trans-
form for cases in which the number of samples to be computed is a power of
2 We start with and work our way up to before we
try to generalize the process. The result of our efforts is known as the decomposition-
in-time, radix-2 FFT .
Starting with a two-point DFT, we have

(N = 2 m ). N = 2 3

N = 2 = 8

1

x[n]W nk = x[0]W 0k + x[1]W 1k , k = 0, 1.

X[k] = a

n= 0

W 0k = e -j0 W 1k = e -jpk = (-1) k , Because = 1 and we write

X[0] = x[0] + x[1];

X[1] = x[0] - x[1].

In general, for the two-point DFT, we have

X[k] = x[0] + (-1) k x[1].