Discrete-Time Fourier Methods: M. J. Roberts All Rights Reserved. Edited by Dr. Robert Akl

Discrete-Time Fourier Methods
M.J.RobertsAllRightsReserved. 1
EditedbyDr.RobertAkl
DiscreteTimeFourierSeriesConcept
A signal can be represented as a linear combination of sinusoids.
M.J.RobertsAllRightsReserved.EditedbyDr.RobertAkl 2
The relationship between complex and real sinusoids
TheDiscreteTimeFourierSeries
The discrete-time Fourier series (DTFS) is similar to the CTFS.
A periodic discrete-time signal can be expressed as
1 n0 N1
x n c x k ej 2 kn/ N c x k
N nn0
x n e j 2 kn/ N
k N
where c x k is the harmonic function, N is any period of x n

and the notation, means a summation over any range of
k N
consecutive ks exactly N in length.
TheDiscreteFourierTransform
The discrete Fourier transform (DFT) is almost identical to the DTFS.
A periodic discrete-time signal can be expressed as
n0 N1
1
x n
N k N
X k ej 2 kn/ N
X k x n e j 2 kn/ N
nn0
where X k is the DFT harmonic function, N is any period of x n

and the notation, means a summation over any range of
k N
consecutive ks exactly N in length. The main difference between the

DTFS and the DFT is the location of the 1/N term. So X k N c x k .
Because the DTFS and DFT are so similar, and because the DFT is
so widely used in digital signal processing (DSP), we will concentrate
on the DFT realizing we can always form the DTFS from
c x k X k / N.
DFTExample
Find the DFT harmonic function for

x n u n u n 3 5 n
using its fundamental period as the representation time.
X k x n e j 2 kn/ N
n N

4
u n u n 3 5 n e j 2 kn/5
n0
2
1 e j6 k/5 e j3 k/5 ej3 k/5 e j3 k/5
e j 2 kn/5
j 2 k/5
j k/5 j k/5 j k/5
n0 1 e e e e
2

sin 3 k / 5 3e
e j 2 kn/5
e j 2 k/5

sin k / 5
j 2 k/5

drcl k / 5,3
n0
TheDFTHarmonicFunction
1
We know that x n
N k N
X k ej 2 kn/ N
so we can find x n
from its harmonic function. But how do we find the harmonic

function from x n ? We use the principle of orthogonality like
we did with the CTFS except that now the orthogonality is in
discrete time instead of continuous time.
Below is a set of complex sinusoids for N 8. They form a
set of basis vectors. Notice that the k 7 complex sinusoid
rotates counterclockwise through 7 cycles but appears to rotate
clockwise through one cycle. The k 7 complex sinusoid is
exactly the same as the k 1 complex sinusoid. This must be
true because the DFT is periodic with period N.
The projection of a real vector x in the direction of another
real vector y is
xT y
p T y
yy
If p 0, x and y are orthogonal. If the vectors are complex-
valued
xH y
p H y
y y
where the xH is the complex-conjugate transpose of x. xT y
and xH y are the dot product of x and y.
The most common definition of the DFT is

N1
1
X k x n e
j 2 kn/ N
, x n X k ej 2 kn/N
n0 N k N
Here the beginning point for x n is taken as n0 0 . This is
the form of the DFT that is implemented in practically all computer
languages.
ConvergenceoftheDFT
TheDFTconvergesexactlywithafinite
numberofterms.ItdoesnothaveaGibbs
phenomenoninthesamesensethatthe
CTFSdoes
DFTProperties
DFTProperties
DFTProperties
It can be shown (and is in the text) that if x n is an even

function, X k is purely real and if x n is an odd function
X k is purely imaginary.
TheDirichletFunction
sin Nt
The functional form
N sin t
appears often in discrete-time
signal analysis and is given the
special name Dirichlet function.
That is
sin Nt
drcl t, N
N sin t
DFTPairs
TheFastFourierTransform
TheFastFourierTransform
GeneralizingtheDFTfor
AperiodicSignals
PulseTrain
Thisperiodicrectangularwavesignalisanalogoustothe
continuoustimeperiodicrectangularwavesignalusedto
illustratethetransitionfromtheCTFStotheCTFT.
AperiodicSignals
DFTof
PulseTrain
Astheperiodofthe
rectangularwave
increases,theperiodof
theDFTincreases
AperiodicSignals
Normalized
DFTof
PulseTrain
By plotting versus k / N0
instead of k, the period
of the normalized DFT
stays at one.
AperiodicSignals
ThenormalizedDFTapproachesthislimitasthe
periodapproachesinfinity.
DefinitionoftheDiscreteTime
FourierTransform(DTFT)
TheDiscreteTimeFourier
Transform
The function e j appears in the forward DTFT raised to the nth power.
It is periodic in with fundamental period 2 . n is an integer. Therefore
e- jn is periodic with fundamental period 2 / n and 2 is also a period
of e jn. The forward DTFT is

X e x n e
j jn
a weighted summation of functions of the form e jn, all of which repeat with

every 2 change in . Therefore X ej is always periodic in with period
2 . This also implies that X F is always periodic in F with period 1.
DTFTPairs
We can begin a table of DTFT pairs directly from the definition.
(There is a more extensive table in the text.)
TheGeneralizedDTFT
By generalizing the CTFT to include transform that have impulses
we were able to find CTFT's of some important practical functions.
The same is true of the DTFT. The DTFT of a constant

X F Ae j 2 Fn A e j 2 Fn
n n
does not converge. The CTFT of a constant turned out to be an

impulse. Since the DTFT must be periodic that cannot the the
transform of a constant in discrete time. Instead the transform must
be a periodic impulse.
TheGeneralizedDTFT
TheGeneralizedDTFT
ForwardDTFTExample
ForwardDTFTExample
ForwardDTFTExample
MoreDTFTPairs
We can now extend the table of DTFT pairs.
DTFTProperties
DTFTProperties
DTFTProperties
DTFTProperties
DTFTProperties
Time scaling in discrete time is quite different from time
scaling in continuous-time. Let z n x an . If a is not an
integer some values of z n are undefined and a DTFT cannot
be found for it. If a is
an integer greater than
one, some values of x n
will not appear in z n
because of decimation and
there cannot be a unique
relationship between their
DTFTs
DTFTProperties
DTFTProperties
In the time domain, the response of a system is the convolution

of the excitation with the impulse response
y n x n h n
In the frequency domain the response of a system is the product
of the excitation and the frequency response of the system

Y ej X ej H ej
DTFTProperties
Find the signal energy of x n 1 / 5 sinc n/100 . The
straightforward way of finding signal energy is directly from

x n
2
the definition Ex .
n

1 / 5 sinc n/100 1 / 25 n/100

2
Ex sinc 2
n n
In this case we run into difficulty because we don't know how

to sum this series.
DTFTProperties
TransformMethodComparisons
Using the equivalence property of the impulse and fact that both
ej 2 F and 1 F have a fundamental period of one,
1 F 1 /12 j /6 1 F 1 /12
Y F 1 / 2 e j /6
e
e j /6
0.9 e j /6
0.9
Finding a common denominator and simplifying,
1 F 1 /12 1 0.9ej /6 1 F 1 /12 1 0.9e j /6
Y F 1 / 2
1.81 1.8 cos / 6
Y F 0.4391 1 F 1 /12 1 F 1 /12
j0.8957 1 F 1 /12 1 F 1 /12
y n 0.8782 cos 2 n/12 1.7914 sin 2 n/12
y n 1.995 cos 2 n/ 12 1.115
The DFT can often be used to find the DTFT of a signal. The

DTFT is defined by X F x n e j 2 Fn and the DFT
n
N1
is defined by X k x n e j 2 kn/ N . If the signal x n is causal
n0
and time limited, the summation in the DTFT is over a finite

range of n values beginning with 0 and we can set the value of
N by letting N 1 be the last value of n needed to cover that finite
N1
range. Then X F x n e j 2 Fn. Now let F k / N yielding
n0
N1
X k / N x n e j 2 kn/N X k
n0
The result
N1
X k / N x n e j 2 kn/N X k
n0
is the DTFT of x n at a discrete set of frequencies F k / N or

2 k / N. If that resolution in frequency is not sufficient, N
can be made larger by augmenting the previous set of x n values
with zeros. That reduces the space between frequency points
thereby increasing the resolution. This technique is called zero
padding.
We can also use the DFT to approximate the inverse DTFT.
The inverse DTFT is defined by x n X F ej 2 Fn dF
1
1 N1
and the inverse DFT is defined by x n X k ej 2 kn/N .
N k0
We can approximate the inverse DTFT by
N1 k1 / N N1 k1 /N
x n X k / N ej 2 Fn dF X k / N ej 2 Fn dF
k0 k/N k0 k/ N
N1
ej 2 k1 n/N ej 2 k/ N ej 2 n/N 1 N1
x n X k / N X k / N ej 2 kn/N
k0 j2 n j2 n k0
1 N1
x n e j n/N
sinc n/ N X k / N ej 2 kn/N
N k0
For n N,
1 N1
x n X k / N ej 2 kn/ N
N k0
This is the inverse DFT with X k X k / N .
Use this result to find the inverse DTFT of

X F rect 50 F 1 / 4 rect 50 F 1 / 4 1 F
with the inverse DFT.
TheFourFourierMethods
RelationsAmongFourierMethods
MultiplicationConvolutionDuality
ParsevalsTheorem
Discrete Frequency Continuous Frequency

1
x t dt X k x t dt X f df
2 2 2 2
Continuous Time
T0 T0
k

1
x n x n X F dF
2 2 2 2
Discrete Time X k
n N N k N n
1
TimeandFrequencyShifting

Discrete-Time Fourier Methods: M. J. Roberts All Rights Reserved. Edited by Dr. Robert Akl

Uploaded by

Copyright:

Available Formats

Discrete-Time Fourier Methods: M. J. Roberts All Rights Reserved. Edited by Dr. Robert Akl

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete-Time Fourier Methods: M. J. Roberts All Rights Reserved. Edited by Dr. Robert Akl

Uploaded by

Copyright:

Available Formats

Discrete-Time Fourier Methods

where c x k is the harmonic function, N is any period of x n

consecutive ks exactly N in length.

where X k is the DFT harmonic function, N is any period of x n

consecutive ks exactly N in length. The main difference between the

from its harmonic function. But how do we find the harmonic

The most common definition of the DFT is

It can be shown (and is in the text) that if x n is an even

does not converge. The CTFT of a constant turned out to be an

In the time domain, the response of a system is the convolution

1 / 5 sinc n/100 1 / 25 n/100

In this case we run into difficulty because we don't know how

and time limited, the summation in the DTFT is over a finite

is the DTFT of x n at a discrete set of frequencies F k / N or

Use this result to find the inverse DTFT of

Discrete Frequency Continuous Frequency

You might also like