10.4 Discrete Fourier Transform 617
Therefore, by the linearity of the DFT, we have the DFT ofy[n] is
Y[k]=
∑
m
DFT(ym[n])=
∑
m
Ym[k] (10.51)
where eachYm[k] provides a frequency characterization of the windowed signal or the local frequency
content of the signal. Practically, this would be more meaningful than finding the DFT of the whole
signal. Now we have frequency information corresponding to segments of the signal and possibly
evolving over time.
The DFT of an aperiodic signalx[n]of finite lengthNis found as follows:
n Choose an integerL≥Nthat is the length of the DFT to be the period of a periodic extensionx ̃[n]having
x[n]as a period with padded zeros if necessary.
n Find the normalized Fourier series representation ofx ̃[n],
x ̃[n]=
1
L
L∑− 1
k= 0
X ̃[k]ej^2 πnk/L 0 ≤n≤L− 1 (10.52)
where
X ̃[k]=
L∑− 1
n= 0
̃x[n]e−j^2 πnk/L 0 ≤k≤L− 1 (10.53)
n Then,
n X[k]=X ̃[k]for 0 ≤k≤L− 1 is the DFT ofx[n].
n x[n]= ̃x[n]W[n]whereW[n]=u[n]−u[n−L]is a rectangular window of lengthN, is the IDFT of
X[k]. The IDFTx[n]is defined for 0 ≤n≤L− 1.
10.4.3 Computation of the DFT via the FFT
Although we now have discrete frequencies and use only summations to compute the direct and the
inverse DFT, there are still several issues that should be understood when computing these trans-
forms. Assuming that the given signal is finite length, or it is made finite length by windowing, we
have:
n Efficient computation with the FFT algorithm:A very efficient computation of the DFT is done by
means of the FFT algorithm, which takes advantage of some special characteristics of the DFT, as
we will discuss in Chapter 12. It should be understood that the FFT is not another transformation
but an algorithm to efficiently compute DFTs. For now, we will consider the FFT as a black box
that for an inputx[n] (orX[k]) gives as output the DFTX[k] (or IDFTx[n]).
n Causal aperiodic signals:If the given signalx[n] is causal of lengthN—that is, the samples
{x[n],n=0, 1,...,N− 1 }
are given—we can proceed to obtain{X[k],k=0, 1,...,N− 1 }or the DFT ofx[n] by means of
an FFT of lengthL=N. To compute anL>NDFT we simply attachL−Nzeros at the end of the
