Discrete Fourier transform - Continuous and Discrete Time Signals and Systems - page 531

aforementioned distortions would always be present when approximating the
CTFT with the DFT. This implies that Eq. (12.12) is an approximation for the
CTFT X ( ω ) that, even at its best, only leads to a near-optimal estimation of the
spectral content of the CT signal.
On the other hand, the DFT representation provides an accurate estimate of
the DTFT of a time-limited sequence x [ k ] of length N . By comparing the DFT
spectrum, Fig. 12.1(h), with the DFT spectrum, Fig. 12.1(r), the relationship
between the DTFT X 2 ( Ω ) and the DFT X 2 [ r ] is derived. Except for a factor of
K / M , we note that X 2 [ r ] provides samples of the DTFT at discrete frequencies
Ω r = 2 π r / M , for 0 ≤ r ≤ ( M − 1). The relationship between the DTFT and
DFT is therefore given by

N − 1

N
M X 2 [ r ] =

N
M

x 2 [ k ]e − j(2 π kr / M )

X 2 ( Ω r ) = (12.14)

k = 0

for Ω r = 2 π r / M ,0 ≤ r ≤ ( M − 1). We now proceed with the formal definitions
for the DFT.

12.2 Discrete Four ier transform

Based on our discussion in Section 12.1, the M -point DFT and inverse DFT for a
time-limited sequence x [ k ], which is non-zero within the limits 0 ≤ k ≤ N − 1,
is given by

N − 1

x [ k ]e − j(2 π kr / M ) Forward DFT X [ r ] = for 0 ≤ r ≤ M − 1; (12.15)

k = 0

M − 1

1
M

X [ r ]e j(2 π kr / M )

Inverse DFT x [ k ] = for 0 ≤ k ≤ N − 1 .

r = 0

(12.16)

Equations (12.15) and (12.16) are also, respectively, known as DFT analysis
and synthesis equations. Equation (12.15) was derived in Section 12.1. By
substituting the expression for X [ r ] from Eq. (12.15), the analysis equation,
Eq. (12.16), can be formally proved, and vice versa. The formal proofs of the
DFT pair are left as an exercise for the reader. In Eqs. (12.15) and (12.16), the
length M of the DFT is typically set to be greater or equal to the length N of
the aperiodic sequence x [ k ]. Unless otherwise stated, we assume M = N in the
discussion that follows. Collectively, the DFT pair is denoted as

DFT
←−−→ X [ r ] .

x [ k ] (12.17)

Examples 12.1 and 12.2 illustrate the steps involved in calculating the DFTs of
aperiodic sequences.