Signals and Systems - Electrical Engineering

614 C H A P T E R 10: Fourier Analysis of Discrete-Time Signals and Systems

which coincides with theZ[k] obtained by the periodic convolution, which is given by

Z[k]=

1

N

N∑− 1

n= 0

z[n]e−j^2 πnk/N=

1

4

( 1 +z−^2 + 2 z−^3 )|z=ej 2 πk/ 4 =

1

4

( 1 +e−j^2 π^2 k/^4 + 2 e−j^2 π^3 k/^4 )

n

10.4 Discrete Fourier Transform

Recall that the direct and the inverse DTFTs corresponding to a discrete-time signalx[n] are

X(ejω)=

∑

n

x[n]e−jωn −π≤ω < π

x[n]=

1

2 π

∫π

−π

X(ejω)ejωndω

These equations have the following computational disadvantages:

n The frequencyωvaries continuously from−πtoπ, and as such computingX(ejω)needs to be

done for an uncountable number of frequencies.

n The inverse DTFT requires integration that cannot be implemented exactly in a computer.

To resolve these issues we consider the discrete Fourier transform or DFT (notice the name difference

with respect to the DTFT), which is computed at discrete frequencies and its inverse does not require

integration. Moreover, the DFT is efficiently implemented using an algorithm called the Fast Fourier

Transform (FFT).

The development of the DFT is based on the representation of periodic discrete-time signals. Both

the signal and the Fourier coefficients are periodic of the same period. Thus, the representation of

discrete-time periodic signals is discrete in both time and frequency. We need then to consider how

to extend aperiodic signals into periodic signals, with an appropriate period, to obtain their DFTs.

10.4.1 DFT of Periodic Discrete-Time Signals

A periodic signalx ̃[n] of periodNis represented byNvalues in a period. Its discrete Fourier series is

̃x[n]=

N∑− 1

k= 0

X ̃[k]ejω^0 nk 0 ≤n≤N− 1 (10.40)

whereω 0 = 2 π/Nis the fundamental frequency. The coefficients{X ̃[k]}correspond to harmonic fre-

quencies{kω 0 }for 0≤k≤N−1, so that ̃x[n] has no frequency components at any other frequencies.

Thus, ̃x[n] andX ̃[k] are both discrete and periodic of the same periodN. Moreover, the Fourier series