Page 318 - Schaum's Outline of Theory and Problems of Signals and Systems

CHAP. 61 FOURIER ANALYSIS OF DISCRETE-TIME SIGNALS AND SYSTEMS

6.8 THE DISCRETE FOURIER TRANSFORM

In this section we introduce the technique known as the discrete Fourier transform
(DFT) for finite-length sequences. It should be noted that the DFT should not be confused
with the Fourier transform.

A. Definition:
Let x[n] be a finite-length sequence of length N, that is,
x[n] =O outside the range 0 I n I N - 1
The DFT of x[n], denoted as X[k], is defined by
N- l
X[k] = x[n]W,kn k=0,1, ..., N- 1
n=O
where WN is the Nth root of unity given by

The inverse DFT (IDFT) is given by

The DFT pair is denoted by

xbl -X[kI
Important features of the DFT are the following:
1. There is a one-to-one correspondence between x[n] and X[k].
2. There is an extremely fast algorithm, called the fast Fourier transform (FFT) for its
calculation.
3. The DFT is closely related to the discrete Fourier series and the Fourier transform.
4. The DFT is the appropriate Fourier representation for digital computer realization
because it is discrete and of finite length in both the time and frequency domains.

Note that the choice of N in Eq. (6.92) is not fixed. If x[n] has length N, < N, we want to
assume that x[n] has length N by simply adding (N - Nl) samples with a value of 0. This
addition of dummy samples is known as zero padding. Then the resultant x[n] is often
referred to as an N-point sequence, and X[k] defined in Eq. (6.92) is referred to as an
N-point DFT. By a judicious choice of N, such as choosing it to be a power of 2,
computational efficiencies can be gained.

B. Relationship between the DET and the Discrete Fourier Series:

Comparing Eqs. (6.94) and (6.92) with Eqs. (6.7) and (6.81, we see that X[k] of finite
sequence x[n] can be interpreted as the coefficients c, in the discrete Fourier series
representation of its periodic extension multiplied by the period N,, and NO = N. That is,
X[k] = Nc, (6.96)
Actually, the two can be made identical by including the factor 1/N with the DR
rather than with the IDFT.