TABLE OF CONTENTS In previous chapters, we have seen how to represent a sequence in terms of a linear combination of complex exponentials using the discrete-time Fourier transform (DTFT) and how the sequence values may be used as the coefficients in a power series expansion of a complex-valued function of z. For finite-length sequence there is another representation, called the discrete Fourier transform (DFT). Unlike the DTFT, which is a continuous function of a continuous variable, ?, the DFT is a sequence that corresponds to samples of the DTFT. Such a representation is very useful for digital computations and for digital hardware implementations. In this chapter, we look at the DFT, explore its properties, and see how it may be used to perform such tasks as digital filtering and evaluating the frequency response of a linear shift-invariant system.
Let 
be a periodic sequence with a period N:
Although, strictly speaking, 
does not have a Fourier transform because it is not absolutely summable, it can be expressed in terms of a discrete Fourier series (DFS) as follows:
which is a decomposition of 
into a sum of N harmonically related complex exponentials. The values of the discrete Fourier series coefficients, 
, may be derived by multiplying both sides of this expansion by e ? j2 ?nl/ N, summing over one period, and using the fact that the complex exponentials are orthogonal:
The result is
Note that the DFS coefficients...
