Chapter 3
Transform-Domain
Representation of
Discrete-Time Signals
§ 3.1 Discrete-Time Fourier Transform
Definition - The discrete-time Fourier
transform (DTFT) X(ej?) of a sequence
x[n] is given by
n
njj enxeX ][)(
X(ej?) = Xre(ej?) + j Xim(ej?)
In general,X(ej?) is a complex function of the
real variable? and can be written as
§ 3.1 Discrete-Time Fourier Transform
Xre(ej?) and Xim(ej?) are,respectively,
the real and imaginary parts of X(ej?),
and are real functions of?
X(ej?) can alternately be expressed as
X(ej?) = | X(ej?) |ej?(?)
where
(?) = arg{X(ej?) }
§ 3.1 Discrete-Time Fourier Transform
| X(ej?) | is called the magnitude function
(?) is called the phase function
Both quantities are again real functions
of?
In many applications,the DTFT is called
the Fourier spectrum
Likewise,| X(ej?) | and?(?) are called
the magnitude and phase spectra
§ 3.1 Discrete-Time Fourier Transform
For a real sequence x[n],| X(ej?) | and
Xre(ej?) are even functions of?,whereas,
(?) and Xim(ej?) are odd functions of?
Note,X(ej?) = | X(ej?) |ej?(?+2?k)
= | X(ej?) |ej?(?)
for any integer k
The phase function?(?) cannot be
uniquely specified for any DTFT
§ 3.1 Discrete-Time Fourier Transform
Unless otherwise stated,we shall
assume that the phase function?(?)
is restricted to the following range
of values:
-(?)
called the principal value
§ 3.1 Discrete-Time Fourier Transform
The DTFTs of some sequences
exhibit discontinuities of 2? in their
phase responses
An alternate type of phase function
that is a continuous function of? is
often used
It is derived from the original phase
function by removing the
discontinuities of 2?
§ 3.1 Discrete-Time Fourier Transform
Example - The DTFT of the unit sample
sequence d[n] is given by
1]0[][)(?d d
nj
n
j ene
1],[][ nnx n
Example - Consider the causal sequence
§ 3.1 Discrete-Time Fourier Transform
Its DTFT is given by
0
][)(
n
njn
n
njnj eeneX
je
n
nje
1
1
0
)(
1 jeas
§ 3.1 Discrete-Time Fourier Transform
The magnitude and phase of the DTFT
X(ej?) = 1/(1 – 0.5e-j?) are shown below
§ 3.1 Discrete-Time Fourier Transform
The DTFT X(ej?) of a sequence x[n] is a
continuous function of?
It is also a periodic function of? with a
period 2?:
n
nkjkj oo enxeX )2()2( ][)(
nkj
n
nj eenx o
2][ )(][ oo j
n
nj eXenx
§ 3.1 Discrete-Time Fourier Transform
Therefore
n
njj enxeX ][)(
deeXnx njj )(
2
1][
As a result,the Fourier coefficients x[n] can be
computed from X(ej?) using the Fourier integral
represents the Fourier series representation of
the periodic function
§ 3.1 Discrete-Time Fourier Transform
Inverse discrete-time Fourier transform:
deeXnx njj )(
2
1][
deexnx njj
][
2
1][
Proof:
§ 3.1 Discrete-Time Fourier Transform
The order of integration and summation
can be interchanged if the summation
inside the brackets converges uniformly,
i.e,X(ej?) exists
Then
deex njj
][
2
1
)(
)(s i n][
2
1][ )(
n
nxdex nj
§ 3.1 Discrete-Time Fourier Transform
Now
][][][)( )(s in][ nxnxn nxd
][d? n
n
n
n
n
,0
,1
)(
)(sin
Hence
§ 3.1 Discrete-Time Fourier Transform
Convergence Condition - An infinite
series of the form
n
njj enxeX ][)(
K
Kn
njj
K enxeX ][)(
may or may not converge
Let
§ 3.1 Discrete-Time Fourier Transform
Then for uniform convergence of X(ej?)
0)()(li m jKjK eXeX
n
nx ][
Now,if x[n] is an absolutely summable
sequence,i.e.,if
§ 3.1 Discrete-Time Fourier Transform
Then
nn
njj nxenxeX ][][)(
Thus,the absolute summability of x[n]
is a sufficient condition for the existence
of the DTFT X(ej?)
for all values of?
§ 3.1 Discrete-Time Fourier Transform
Example - The sequence x[n] =?n?[n]
for |?|< 1 is absolutely summable as
1
1][
0n
n
n
n n
and its DTFT X(ej?) therefore converges to
1/(1-?e-j?) uniformly
§ 3.1 Discrete-Time Fourier Transform
Since
,][][
2
2?
nn
nxnx
However,a finite-energy sequence is not
necessarily absolutely summable
an absolutely summable sequence has
always a finite energy
§ 3.1 Discrete-Time Fourier Transform
Example - The sequence
][ nx
00
11
n
nn
,
,/
6
1 2
1
2?
n
x nE
But,x[n] is not absolutely summable
has a finite energy equal to
§ 3.1 Discrete-Time Fourier Transform
A Dirac delta function d(?) is a function of?
with infinite height,zero width,and unit area
d
ddp )()(lim 0
2 2?
0
1
)(p? It is the limiting form of a
unit area pulse function
p?(?) as? goes to zero
satisfying
§ 3.1 Discrete-Time Fourier Transform
Example - Consider the complex
exponential sequence
nj oenx][
d?
k
o
j keX )2(2)(
o
where d(?) is an impulse function of? and
Its DTFT is given by
§ 3.1 Discrete-Time Fourier Transform
is a periodic function of? with a period
2?and is called a periodic impulse train
or impulse train
To verify that X(ej?) given above is
indeed the DTFT of x[n]=ej?0n we
compute the inverse DTFT of X(ej?)
d?
k
o
j keX )2(2)(
The function
§ 3.1 Discrete-Time Fourier Transform
Thus
d
k
nj
o deknx )2(22
1][
njnj
o oede
d? )(
where we have used the sampling
property of the impulse function d(?)
Commonly Used DTFT Pairs
Sequence DTFT
1][?d n
d?
k
k )2(21
d?
k
o
nj ke o )2(2
d
kj
k
e
n )2(
1
1][
j
n
e
n?
1
1)1(],[
§ 3.2 DTFT Properties
There are a number of important
properties of the DTFT that are useful
in signal processing applications
These are listed here without proof
Their proofs are quite straightforward
We illustrate the applications of some of
the DTFT properties
§ 3.2 DTFT Properties
Type of Property Sequence DTFT
deHeG jj )()(
2
1 )(?
deHeGnhng jj
n
)()(2 1][][ **
Parseval’s relation
Modulation g[n]h[n]
Convolution g[n]*h[n] G(ej?)H(ej?)
Differentiation ng[n] jdG(ej?)/d?
Frequency-shifting e-j?0ng[n] G(ej(?-?0))
Time-shifting g[n-n0] e-j?n0G(ej?)
Linearity ag[n]+bh[n] aG(ej?)+bH(ej?)
h[n] H(ej?)
g[n] G(ej?)
§ 3.2 DTFT Properties
g[n]←→G(e jω)
Use the definition of G(ejω)and differentiate
both sides,we obtain
n
nj
j
enj n g
d
edG
][)(
The right-hand side of this equation is the Fourier
transform of –jng[n],Therefore,multiplying both sides
by j,we see
ng[n]←→jdG(ej ω)/dω
§ 3.2 DTFT Properties
Example - Determine the DTFT Y(ej?)
of y[n]=(n+1)?n?[n],|?|<1
Let x[n]=?n?[n],|?|<1
We can therefore write
y[n]=nx[n] + x[n]
The DTFT of x[n] is given by
jj
e
eX
1
1)(
§ 3.2 DTFT Properties
Using the differentiation property of the
DTFT,we observe that the DTFT of nx[n] is
given by
2)1(1
1)(
j
j
j
j
e
e
ed
dj
d
edXj
22 )1(
1
1
1
)1(
)(
jjj
j
j
eee
eeY
Next using the linearity property of the DTFT
we arrive at
§ 3.2 DTFT Properties
Example - Determine the DTFT V(ej?) of the
sequence v[n] defined by
d0v[n]+d1v[n-1] = p0 d[n] + p1 d[n-1]
The DTFT of d[n] is 1
Using the time-shifting property of the DTFT
we observe that the DTFT of d[n-1] is e-j? and
the DTFT of v[n-1] is e-j?V(ej?)
§ 3.2 DTFT Properties
Using the linearity property we then
obtain the frequency-domain
representation of
d0v[n]+d1v[n-1] = p0d[n] + p1d[n-1]
as d0V(ej?)+ d1e-j?V(ej?) = p0 + p1e-j?
Solving the above equation we get
V(ej?) =(p0 + p1e-j?)/(d0+d1e-j?)
§ 3.2 DTFT Properties
The total energy of a finite-energy
sequence g[n] is given by
n
g ng
2][E
deGng j
n
g
22
2
1 )(][
E
From Parseval’s relation we observe
that
§ 3.2 DTFT Properties
is called the energy density spectrum
The area under this curve in the range
- divided by 2? is the energy of
the sequence
2)()( j
gg eGS
The quantity
DTFT Computation Using
MATLAB
The function freqz can be used to
compute the values of the DTFT of a
sequence,described as a rational
function in the form of
Nj
N
j
Mj
M
j
j
ededd
epeppeX
.,,,
.,,,)(
10
10
at a prescribed set of discrete frequency
points?=
DTFT Computation Using
MATLAB
For example,the statement
H = freqz(num,den,w)
returns the frequency response values as
a vector H of a DTFT defined in terms
of the vectors num and den containing
the coefficients {pi} and {di},respectively
at a prescribed set of frequencies
between 0 and 2? given by the vector w
DTFT Computation Using
MATLAB
There are several other forms of the
function freqz
The Program 3_1 (p.128) in the text can
be used to compute the values of the
DTFT of a real sequence
It computes the real and imaginary
parts,and the magnitude and phase of
the DTFT
DTFT Computation Using
MATLAB
Example - Plots of the real and
imaginary parts,and the magnitude and
phase of the DTFT
43
2
43
2
41.06.1
7.237.21
008.0033.0
05.0033.0008.0
)(
jj
jj
jj
jj
j
ee
ee
ee
ee
eX
are shown on the next slide
DTFT Computation Using
MATLAB
DTFT Computation Using
MATLAB
Note,The phase spectrum displays a discontinuity of
2? at? = 0.72
This discontinuity can be removed using the function
unwrap as indicated below
Linear Convolution Using DTFT
An important property of the DTFT is given
by the convolution theorem
It states that if y[n] = x[n]*h[n],then the
DTFT Y(ej?) of y[n] is given by
Y(ej?) = X(ej?) H(ej?)
An implication of this result is that the linear
convolution y[n] of the sequences x[n] and h[n]
can be performed as follows:
Linear Convolution Using DTFT
1) Compute the DTFTs X(ej?) and H(ej?) of
the sequences x[n] and h[n],respectively
2) Form the DTFT Y(ej?) = X(ej?) H(ej?)
3) Compute the IDTFT y[n] of Y(ej?)
x[n]
h[n]
y[n]
DTFT
DTFT
IDTFT
X(ej?)
H(ej?)
Y(ej?)
§ 3.3 Discrete Fourier Transform
(DFT)
DTFT is the Fourier Transform of
discrete-time sequence,It is discrete in
time domain and its spectrum is
periodical,but continue which cannot be
processed by computer which could only
process digital signals in both sides,that
means the signals in both sides must be
both discrete and periodical,
§ 3.3 Discrete Fourier Transform
(DFT)
Time domain Frequency domain
Continue aperiodical? FT? Continue aperiodical
Periodical? FST? discrete spectrum
Discrete? DTFT? periodical spectrum
Discrete periodical? DFT? periodical discrete
Typical DFT Pair
δT(t)ω0δω0(ω)
T 2T-T-2T
δT(t)
t0 ω0 2ω0-ω0-2ω0
ω0δω0(ω)
0 ω
ω0 = 2π/T
In DFT,the signals in both sides are discrete,so it is the
only transform pair which can be processed by computer,
The signals in both sides are periodical,so the
processing could be in one period,which is important
because (1) the number of calculation is limited,which is
necessary for computer; (2) all of the signal information
could be kept in one period,which is necessary for
accurate processing.
Make a signal discrete and periodical
The engineering signals are often continue and
aperiodical,If we want to process the signals with
DFT,we have to make the signals discrete and
periodical.
Sampling to make the signal discrete
Make the signal periodical:
If x[n] is a limited length N-point sequence,see it as
one period of a periodical signal that means extend it
to a periodical
If x[n] is an infinite length sequence,cut-off its tail to
make a N-point sequence,then do the periodic
extending,The tail cutting-off will introduce
distortion,We must develop truncation algorithm to
reduce the error,which is windowing.
Make a signal discrete and periodical
x(t) X(jω)
P(jω)
ω0 ω0=2π/Ts
x[nT] X(jω)
q(t)
T
FT
DFT
DTFT
Q(jω)
Ω0
…… Ω0=2π/T……
P(t)
Ts
……
§ 3.3 Discrete Fourier Transform
(DFT)
Definition - The simplest relation
between a length-N sequence x[n],
defined for 0≤n ≤N-1,and its DTFT X(ej?)
is obtained by uniformly sampling X(ej?)
on the?-axis between 0≤?≤2? at
k=2?k/N,0≤k≤N-1
From the definition of the DTFT have
,][)(][
1
0
/2
/2?
N
n
Nkj
Nk
j enxeXkX
10 Nk
§ 3.3 Discrete Fourier Transform
(DFT)
Note,X[k] is also a length-N sequence in
the frequency domain
The sequence X[k] is called the discrete
Fourier transform (DFT) of the
sequence x[n]
Using the notation WN=e-j2?/N the DFT
is usually expressed as:
10,][][
1
0
NkWnxkX
N
n
nk
N
§ 3.3 Discrete Fourier Transform
(DFT)
The inverse discrete Fourier transform
(IDFT) is given by
10,][1][
1
0
NnWkX
Nnx
N
k
kn
N
To verify the above expression we multiply
both sides of the above equation by WNln and
sum the result from n = 0 to n=N-1
§ 3.3 Discrete Fourier Transform
(DFT)
resulting in
1
0
1
0
1
0
1N
n
n
N
N
k
kn
N
N
n
n
N WWkXNWnx
][][
1
0
1
0
1 N
n
N
k
nk
NWkXN
)(][?
1
0
1
0
1 N
k
N
n
nk
NWkXN
)(][?
§ 3.3 Discrete Fourier Transform
(DFT)
Making use of the identity
1
0
N
n
nk
NW
)(?
,,0N,rNkf o ro th e r w is er an integer
][][ XWnx
N
n
n
N
1
0
Hence
§ 3.3 Discrete Fourier Transform
(DFT)
Example - Consider the length-N
sequence
110
01
Nn
n
,
,
][nx
10 0
1
0
N
N
n
kn
N WxWnxkX ][][][
10 Nk
Its N-point DFT is given by
§ 3.3 Discrete Fourier Transform
(DFT)
Example - Consider the length-N
sequence
][ny
11100
1
Nnmmn
mn
,,
,
km
N
km
N
N
n
kn
N WWmyWnykY
][][][
1
0
10 Nk
Its N-point DFT is given by
§ 3.3 Discrete Fourier Transform
(DFT)
Example - Consider the length-N
sequence defined for 0 ≤n ≤N-1
10),/2c o s(][ NrNrnng
NrnjNrnj eeng /2/221][
rNNrNN WW21
Using a trigonometric identity we can
write
§ 3.3 Discrete Fourier Transform
(DFT)
The N-point DFT of g[n] is thus given by
1
0
N
n
kn
NWngkG ][][
,21
1
0
)(1
0
)(?
N
n
nkr
N
N
n
nkr
N WW
10 Nk
§ 3.3 Discrete Fourier Transform
(DFT)
Making use of the identity
1
0
N
n
nk
NW
)(?
,
,
0
N,rNkf o r
o th e r w is e
r an integer
o th e r w is e0
f o r2
f o r2
,
,/
,/
][ rNkN
rkN
kG
10 Nk
we get
DFT Computation Using
MATLAB
The functions to compute the DFT and
the IDFT are FFT and IFFT
These functions make use of FFT
algorithms which are computationally
highly efficient compared to the direct
computation
Programs 3_2(p.134) and 3_4(p.136)
illustrate the use of these functions
DFT Computation Using
MATLAB
Example - Program 3_4 can be used to compute the
DFT and the DTFT of the sequence
150),16/6c o s(][ nnnx
indicates DFT samples
as shown below
0 0.2 0.4 0.6 0.8 1
0
2
4
6
8
10
N or m a l i z e d a ngul a r f r e que nc y
M
a
gni
t
ude
§ 3.4 DFT Properties
Like the DTFT,the DFT also satisfies a
number of properties that are useful in
signal processing applications
Some of these properties are essentially
identical to those of the DTFT,while
some others are somewhat different
A summary of the DFT properties are
given in tables in the following slides
§ 3.4 DFT Properties
Type of Property length-N sequence N-point DFT
][][1
0
N
m
Nmnhmg
][][1 1
0?
N
m N
mkHmGN
1
0
21
0
2 |][|1|][| N
k
N
n
kXNnxParseval’s relation
Modulation g[n]h[n]
G[k]H[k]Circular Convolution
Duality G[n] N[g?-k?N]
Frequency-shifting WN-kn0g[n] G[?k-k0?N]
Circular Time-shifting g[?n-n0?N] WNkn0G[k]
Linearity ag[n]+bh[n] aG[k]+bH[k]
h[n] H[k]
g[n] G[k]
§ 3.5 Circular Shift of a Sequence
This property is analogous to the time-
shifting property of the DTFT,but with
a subtle difference
Consider length-N sequences defined for
0≤n≤N-1
Sample values of such sequences are
equal to zero for values of n < 0 and
n≥N
§ 3.5 Circular Shift of a Sequence
If x[n] is such a sequence,then for any
arbitrary integer n0,the shifted sequence
x1[n] = x[n – n0]
is no longer defined for the range 0≤n≤N-1
We thus need to define another type of a shift
that will always keep the shifted sequence in
the range 0≤n≤N-1
§ 3.5 Circular Shift of a Sequence
The desired shift,called the circular
shift,is defined using a modulo
operation:
][][ Noc nnxnx
],[
],[][
nnNx
nnxnx
o
oc
o
o
nn
Nnn
0f o r
1f o r
For n0>0 (right circular shift),the above
equation implies
§ 3.5 Circular Shift of a Sequence
Illustration of the concept of a circular shift
][nx ]1[ 6nx
]5[ 6 nx
]4[ 6nx
]2[ 6 nx
§ 3.5 Circular Shift of a Sequence
As can be seen from the previous figure,
a right circular shift by n0 is equivalent
to a left circular shift by N-n0 sample
periods
A circular shift by an integer number
greater than N is equivalent to a circular
shift by?n0?N
§ 3.5 Circular Shift of a Sequence
x[n-1]
x[n]
x[<n-1>N]
n=<4>4=0
§ 3.6 Circular Convolution
This operation is analogous to linear
convolution,but with a subtle difference
Consider two length-N sequences,g[n]
and h[n],respectively
Their linear convolution results in a
length-(2N-1) sequence yL[n] given by
220
1
0
Nnmnhmgny
N
m
L ],[][][
§ 3.6 Circular Convolution
In computing yL[n] we have assumed that both
length-N sequences have been zero-padded to
extend their lengths to 2N-1
The longer form of yL[n] results from the
time-reversal of the sequence h[n] and its
linear shift to the right
The first nonzero value of yL[n] is
yL[n]=g[0]h[0],and the last nonzero value is
yL[2N-2]=g[N-1]h[N-1]
§ 3.6 Circular Convolution
To develop a convolution-like operation
resulting in a length-N sequence yC[n],
we need to define a circular time-
reversal,and then apply a circular time-
shift
Resulting operation,called a circular
convolution,is defined by
10],[][][
1
0
Nnmnhmgny
N
m
NC
§ 3.6 Circular Convolution
Since the operation defined involves two
length-N sequences,it is often referred
to as an N-point circular convolution,
denoted as
N Ng[n] h[n] = h[n] g[n]
The circular convolution is commutative,i.e.
Ny[n] = g[n] h[n]
§ 3.6 Circular Convolution
Example - Determine the 4-point circular
convolution of the two length-4 sequences:
},{]}[{ 1021?ng }{]}[{ 1122?nh
n
3210
1
2 ][ng
n
3210
1
2 ][nh
as sketched below
§ 3.6 Circular Convolution
The result is a length-4 sequence yC[n]
given by
3
0
4 ][][]0[
m
C mhmgy
]1[]3[]2[]2[]3[]1[]0[]0[ hghghghg
621101221 )()()()(
,][][][][][
3
0
4
m
C mnhmgnhngny 4
30 nFrom the above we observe
§ 3.6 Circular Convolution
Likewise
3
0
4 ]1[][]1[
m
C mhmgy
][][][][][][][][ 23320110 hghghghg
711102221 )()()()(
3
0
4 ]2[][]2[
m
C mhmgy
][][][][][][][][ 33021120 hghghghg
611202211 )()()()(
§ 3.6 Circular Convolution
The circular
convolution can also
be computed using a
DFT-based approach
3
0
4 ]3[][]3[
m
C mhmgy
][][][][][][][][ 03122130 hghghghg
521201211 )()()()(
][nyC
§ 3.6 Circular Convolution
Example - Consider the two length-4
sequences repeated below for convenience:
n
3210
1
2 ][ng
n
3210
1
2 ][nh
4210 /][][][ kjeggkG
4644 32 // ][][ kjkj egeg
3021 232 kee kjkj,//
The 4-point DFT G[k] of g[n] is given by
§ 3.6 Circular Convolution
Therefore
,][ 21212G
,][ jjjG 1211
jjjG 1213 ][
,][ 41210G
4210 /][][][ kjehhkH
4644 32 // ][][ kjkj eheh
3022 232 keee kjkjkj,//
Likewise,
§ 3.6 Circular Convolution
Hence,,][ 611220H
,][ 011222H
,][ jjjH 11221
jjjH 11223 ][
Homework
Read textbook from p.117 to 155
Problems
3.1,3.4,3.6,3.8,3.13,3.18,3.22,3.25,
3.50,3.51,3.56,3.64,3.65,3.74
M3.2,M3.8,M3.9
Transform-Domain
Representation of
Discrete-Time Signals
§ 3.1 Discrete-Time Fourier Transform
Definition - The discrete-time Fourier
transform (DTFT) X(ej?) of a sequence
x[n] is given by
n
njj enxeX ][)(
X(ej?) = Xre(ej?) + j Xim(ej?)
In general,X(ej?) is a complex function of the
real variable? and can be written as
§ 3.1 Discrete-Time Fourier Transform
Xre(ej?) and Xim(ej?) are,respectively,
the real and imaginary parts of X(ej?),
and are real functions of?
X(ej?) can alternately be expressed as
X(ej?) = | X(ej?) |ej?(?)
where
(?) = arg{X(ej?) }
§ 3.1 Discrete-Time Fourier Transform
| X(ej?) | is called the magnitude function
(?) is called the phase function
Both quantities are again real functions
of?
In many applications,the DTFT is called
the Fourier spectrum
Likewise,| X(ej?) | and?(?) are called
the magnitude and phase spectra
§ 3.1 Discrete-Time Fourier Transform
For a real sequence x[n],| X(ej?) | and
Xre(ej?) are even functions of?,whereas,
(?) and Xim(ej?) are odd functions of?
Note,X(ej?) = | X(ej?) |ej?(?+2?k)
= | X(ej?) |ej?(?)
for any integer k
The phase function?(?) cannot be
uniquely specified for any DTFT
§ 3.1 Discrete-Time Fourier Transform
Unless otherwise stated,we shall
assume that the phase function?(?)
is restricted to the following range
of values:
-(?)
called the principal value
§ 3.1 Discrete-Time Fourier Transform
The DTFTs of some sequences
exhibit discontinuities of 2? in their
phase responses
An alternate type of phase function
that is a continuous function of? is
often used
It is derived from the original phase
function by removing the
discontinuities of 2?
§ 3.1 Discrete-Time Fourier Transform
Example - The DTFT of the unit sample
sequence d[n] is given by
1]0[][)(?d d
nj
n
j ene
1],[][ nnx n
Example - Consider the causal sequence
§ 3.1 Discrete-Time Fourier Transform
Its DTFT is given by
0
][)(
n
njn
n
njnj eeneX
je
n
nje
1
1
0
)(
1 jeas
§ 3.1 Discrete-Time Fourier Transform
The magnitude and phase of the DTFT
X(ej?) = 1/(1 – 0.5e-j?) are shown below
§ 3.1 Discrete-Time Fourier Transform
The DTFT X(ej?) of a sequence x[n] is a
continuous function of?
It is also a periodic function of? with a
period 2?:
n
nkjkj oo enxeX )2()2( ][)(
nkj
n
nj eenx o
2][ )(][ oo j
n
nj eXenx
§ 3.1 Discrete-Time Fourier Transform
Therefore
n
njj enxeX ][)(
deeXnx njj )(
2
1][
As a result,the Fourier coefficients x[n] can be
computed from X(ej?) using the Fourier integral
represents the Fourier series representation of
the periodic function
§ 3.1 Discrete-Time Fourier Transform
Inverse discrete-time Fourier transform:
deeXnx njj )(
2
1][
deexnx njj
][
2
1][
Proof:
§ 3.1 Discrete-Time Fourier Transform
The order of integration and summation
can be interchanged if the summation
inside the brackets converges uniformly,
i.e,X(ej?) exists
Then
deex njj
][
2
1
)(
)(s i n][
2
1][ )(
n
nxdex nj
§ 3.1 Discrete-Time Fourier Transform
Now
][][][)( )(s in][ nxnxn nxd
][d? n
n
n
n
n
,0
,1
)(
)(sin
Hence
§ 3.1 Discrete-Time Fourier Transform
Convergence Condition - An infinite
series of the form
n
njj enxeX ][)(
K
Kn
njj
K enxeX ][)(
may or may not converge
Let
§ 3.1 Discrete-Time Fourier Transform
Then for uniform convergence of X(ej?)
0)()(li m jKjK eXeX
n
nx ][
Now,if x[n] is an absolutely summable
sequence,i.e.,if
§ 3.1 Discrete-Time Fourier Transform
Then
nn
njj nxenxeX ][][)(
Thus,the absolute summability of x[n]
is a sufficient condition for the existence
of the DTFT X(ej?)
for all values of?
§ 3.1 Discrete-Time Fourier Transform
Example - The sequence x[n] =?n?[n]
for |?|< 1 is absolutely summable as
1
1][
0n
n
n
n n
and its DTFT X(ej?) therefore converges to
1/(1-?e-j?) uniformly
§ 3.1 Discrete-Time Fourier Transform
Since
,][][
2
2?
nn
nxnx
However,a finite-energy sequence is not
necessarily absolutely summable
an absolutely summable sequence has
always a finite energy
§ 3.1 Discrete-Time Fourier Transform
Example - The sequence
][ nx
00
11
n
nn
,
,/
6
1 2
1
2?
n
x nE
But,x[n] is not absolutely summable
has a finite energy equal to
§ 3.1 Discrete-Time Fourier Transform
A Dirac delta function d(?) is a function of?
with infinite height,zero width,and unit area
d
ddp )()(lim 0
2 2?
0
1
)(p? It is the limiting form of a
unit area pulse function
p?(?) as? goes to zero
satisfying
§ 3.1 Discrete-Time Fourier Transform
Example - Consider the complex
exponential sequence
nj oenx][
d?
k
o
j keX )2(2)(
o
where d(?) is an impulse function of? and
Its DTFT is given by
§ 3.1 Discrete-Time Fourier Transform
is a periodic function of? with a period
2?and is called a periodic impulse train
or impulse train
To verify that X(ej?) given above is
indeed the DTFT of x[n]=ej?0n we
compute the inverse DTFT of X(ej?)
d?
k
o
j keX )2(2)(
The function
§ 3.1 Discrete-Time Fourier Transform
Thus
d
k
nj
o deknx )2(22
1][
njnj
o oede
d? )(
where we have used the sampling
property of the impulse function d(?)
Commonly Used DTFT Pairs
Sequence DTFT
1][?d n
d?
k
k )2(21
d?
k
o
nj ke o )2(2
d
kj
k
e
n )2(
1
1][
j
n
e
n?
1
1)1(],[
§ 3.2 DTFT Properties
There are a number of important
properties of the DTFT that are useful
in signal processing applications
These are listed here without proof
Their proofs are quite straightforward
We illustrate the applications of some of
the DTFT properties
§ 3.2 DTFT Properties
Type of Property Sequence DTFT
deHeG jj )()(
2
1 )(?
deHeGnhng jj
n
)()(2 1][][ **
Parseval’s relation
Modulation g[n]h[n]
Convolution g[n]*h[n] G(ej?)H(ej?)
Differentiation ng[n] jdG(ej?)/d?
Frequency-shifting e-j?0ng[n] G(ej(?-?0))
Time-shifting g[n-n0] e-j?n0G(ej?)
Linearity ag[n]+bh[n] aG(ej?)+bH(ej?)
h[n] H(ej?)
g[n] G(ej?)
§ 3.2 DTFT Properties
g[n]←→G(e jω)
Use the definition of G(ejω)and differentiate
both sides,we obtain
n
nj
j
enj n g
d
edG
][)(
The right-hand side of this equation is the Fourier
transform of –jng[n],Therefore,multiplying both sides
by j,we see
ng[n]←→jdG(ej ω)/dω
§ 3.2 DTFT Properties
Example - Determine the DTFT Y(ej?)
of y[n]=(n+1)?n?[n],|?|<1
Let x[n]=?n?[n],|?|<1
We can therefore write
y[n]=nx[n] + x[n]
The DTFT of x[n] is given by
jj
e
eX
1
1)(
§ 3.2 DTFT Properties
Using the differentiation property of the
DTFT,we observe that the DTFT of nx[n] is
given by
2)1(1
1)(
j
j
j
j
e
e
ed
dj
d
edXj
22 )1(
1
1
1
)1(
)(
jjj
j
j
eee
eeY
Next using the linearity property of the DTFT
we arrive at
§ 3.2 DTFT Properties
Example - Determine the DTFT V(ej?) of the
sequence v[n] defined by
d0v[n]+d1v[n-1] = p0 d[n] + p1 d[n-1]
The DTFT of d[n] is 1
Using the time-shifting property of the DTFT
we observe that the DTFT of d[n-1] is e-j? and
the DTFT of v[n-1] is e-j?V(ej?)
§ 3.2 DTFT Properties
Using the linearity property we then
obtain the frequency-domain
representation of
d0v[n]+d1v[n-1] = p0d[n] + p1d[n-1]
as d0V(ej?)+ d1e-j?V(ej?) = p0 + p1e-j?
Solving the above equation we get
V(ej?) =(p0 + p1e-j?)/(d0+d1e-j?)
§ 3.2 DTFT Properties
The total energy of a finite-energy
sequence g[n] is given by
n
g ng
2][E
deGng j
n
g
22
2
1 )(][
E
From Parseval’s relation we observe
that
§ 3.2 DTFT Properties
is called the energy density spectrum
The area under this curve in the range
- divided by 2? is the energy of
the sequence
2)()( j
gg eGS
The quantity
DTFT Computation Using
MATLAB
The function freqz can be used to
compute the values of the DTFT of a
sequence,described as a rational
function in the form of
Nj
N
j
Mj
M
j
j
ededd
epeppeX
.,,,
.,,,)(
10
10
at a prescribed set of discrete frequency
points?=
DTFT Computation Using
MATLAB
For example,the statement
H = freqz(num,den,w)
returns the frequency response values as
a vector H of a DTFT defined in terms
of the vectors num and den containing
the coefficients {pi} and {di},respectively
at a prescribed set of frequencies
between 0 and 2? given by the vector w
DTFT Computation Using
MATLAB
There are several other forms of the
function freqz
The Program 3_1 (p.128) in the text can
be used to compute the values of the
DTFT of a real sequence
It computes the real and imaginary
parts,and the magnitude and phase of
the DTFT
DTFT Computation Using
MATLAB
Example - Plots of the real and
imaginary parts,and the magnitude and
phase of the DTFT
43
2
43
2
41.06.1
7.237.21
008.0033.0
05.0033.0008.0
)(
jj
jj
jj
jj
j
ee
ee
ee
ee
eX
are shown on the next slide
DTFT Computation Using
MATLAB
DTFT Computation Using
MATLAB
Note,The phase spectrum displays a discontinuity of
2? at? = 0.72
This discontinuity can be removed using the function
unwrap as indicated below
Linear Convolution Using DTFT
An important property of the DTFT is given
by the convolution theorem
It states that if y[n] = x[n]*h[n],then the
DTFT Y(ej?) of y[n] is given by
Y(ej?) = X(ej?) H(ej?)
An implication of this result is that the linear
convolution y[n] of the sequences x[n] and h[n]
can be performed as follows:
Linear Convolution Using DTFT
1) Compute the DTFTs X(ej?) and H(ej?) of
the sequences x[n] and h[n],respectively
2) Form the DTFT Y(ej?) = X(ej?) H(ej?)
3) Compute the IDTFT y[n] of Y(ej?)
x[n]
h[n]
y[n]
DTFT
DTFT
IDTFT
X(ej?)
H(ej?)
Y(ej?)
§ 3.3 Discrete Fourier Transform
(DFT)
DTFT is the Fourier Transform of
discrete-time sequence,It is discrete in
time domain and its spectrum is
periodical,but continue which cannot be
processed by computer which could only
process digital signals in both sides,that
means the signals in both sides must be
both discrete and periodical,
§ 3.3 Discrete Fourier Transform
(DFT)
Time domain Frequency domain
Continue aperiodical? FT? Continue aperiodical
Periodical? FST? discrete spectrum
Discrete? DTFT? periodical spectrum
Discrete periodical? DFT? periodical discrete
Typical DFT Pair
δT(t)ω0δω0(ω)
T 2T-T-2T
δT(t)
t0 ω0 2ω0-ω0-2ω0
ω0δω0(ω)
0 ω
ω0 = 2π/T
In DFT,the signals in both sides are discrete,so it is the
only transform pair which can be processed by computer,
The signals in both sides are periodical,so the
processing could be in one period,which is important
because (1) the number of calculation is limited,which is
necessary for computer; (2) all of the signal information
could be kept in one period,which is necessary for
accurate processing.
Make a signal discrete and periodical
The engineering signals are often continue and
aperiodical,If we want to process the signals with
DFT,we have to make the signals discrete and
periodical.
Sampling to make the signal discrete
Make the signal periodical:
If x[n] is a limited length N-point sequence,see it as
one period of a periodical signal that means extend it
to a periodical
If x[n] is an infinite length sequence,cut-off its tail to
make a N-point sequence,then do the periodic
extending,The tail cutting-off will introduce
distortion,We must develop truncation algorithm to
reduce the error,which is windowing.
Make a signal discrete and periodical
x(t) X(jω)
P(jω)
ω0 ω0=2π/Ts
x[nT] X(jω)
q(t)
T
FT
DFT
DTFT
Q(jω)
Ω0
…… Ω0=2π/T……
P(t)
Ts
……
§ 3.3 Discrete Fourier Transform
(DFT)
Definition - The simplest relation
between a length-N sequence x[n],
defined for 0≤n ≤N-1,and its DTFT X(ej?)
is obtained by uniformly sampling X(ej?)
on the?-axis between 0≤?≤2? at
k=2?k/N,0≤k≤N-1
From the definition of the DTFT have
,][)(][
1
0
/2
/2?
N
n
Nkj
Nk
j enxeXkX
10 Nk
§ 3.3 Discrete Fourier Transform
(DFT)
Note,X[k] is also a length-N sequence in
the frequency domain
The sequence X[k] is called the discrete
Fourier transform (DFT) of the
sequence x[n]
Using the notation WN=e-j2?/N the DFT
is usually expressed as:
10,][][
1
0
NkWnxkX
N
n
nk
N
§ 3.3 Discrete Fourier Transform
(DFT)
The inverse discrete Fourier transform
(IDFT) is given by
10,][1][
1
0
NnWkX
Nnx
N
k
kn
N
To verify the above expression we multiply
both sides of the above equation by WNln and
sum the result from n = 0 to n=N-1
§ 3.3 Discrete Fourier Transform
(DFT)
resulting in
1
0
1
0
1
0
1N
n
n
N
N
k
kn
N
N
n
n
N WWkXNWnx
][][
1
0
1
0
1 N
n
N
k
nk
NWkXN
)(][?
1
0
1
0
1 N
k
N
n
nk
NWkXN
)(][?
§ 3.3 Discrete Fourier Transform
(DFT)
Making use of the identity
1
0
N
n
nk
NW
)(?
,,0N,rNkf o ro th e r w is er an integer
][][ XWnx
N
n
n
N
1
0
Hence
§ 3.3 Discrete Fourier Transform
(DFT)
Example - Consider the length-N
sequence
110
01
Nn
n
,
,
][nx
10 0
1
0
N
N
n
kn
N WxWnxkX ][][][
10 Nk
Its N-point DFT is given by
§ 3.3 Discrete Fourier Transform
(DFT)
Example - Consider the length-N
sequence
][ny
11100
1
Nnmmn
mn
,,
,
km
N
km
N
N
n
kn
N WWmyWnykY
][][][
1
0
10 Nk
Its N-point DFT is given by
§ 3.3 Discrete Fourier Transform
(DFT)
Example - Consider the length-N
sequence defined for 0 ≤n ≤N-1
10),/2c o s(][ NrNrnng
NrnjNrnj eeng /2/221][
rNNrNN WW21
Using a trigonometric identity we can
write
§ 3.3 Discrete Fourier Transform
(DFT)
The N-point DFT of g[n] is thus given by
1
0
N
n
kn
NWngkG ][][
,21
1
0
)(1
0
)(?
N
n
nkr
N
N
n
nkr
N WW
10 Nk
§ 3.3 Discrete Fourier Transform
(DFT)
Making use of the identity
1
0
N
n
nk
NW
)(?
,
,
0
N,rNkf o r
o th e r w is e
r an integer
o th e r w is e0
f o r2
f o r2
,
,/
,/
][ rNkN
rkN
kG
10 Nk
we get
DFT Computation Using
MATLAB
The functions to compute the DFT and
the IDFT are FFT and IFFT
These functions make use of FFT
algorithms which are computationally
highly efficient compared to the direct
computation
Programs 3_2(p.134) and 3_4(p.136)
illustrate the use of these functions
DFT Computation Using
MATLAB
Example - Program 3_4 can be used to compute the
DFT and the DTFT of the sequence
150),16/6c o s(][ nnnx
indicates DFT samples
as shown below
0 0.2 0.4 0.6 0.8 1
0
2
4
6
8
10
N or m a l i z e d a ngul a r f r e que nc y
M
a
gni
t
ude
§ 3.4 DFT Properties
Like the DTFT,the DFT also satisfies a
number of properties that are useful in
signal processing applications
Some of these properties are essentially
identical to those of the DTFT,while
some others are somewhat different
A summary of the DFT properties are
given in tables in the following slides
§ 3.4 DFT Properties
Type of Property length-N sequence N-point DFT
][][1
0
N
m
Nmnhmg
][][1 1
0?
N
m N
mkHmGN
1
0
21
0
2 |][|1|][| N
k
N
n
kXNnxParseval’s relation
Modulation g[n]h[n]
G[k]H[k]Circular Convolution
Duality G[n] N[g?-k?N]
Frequency-shifting WN-kn0g[n] G[?k-k0?N]
Circular Time-shifting g[?n-n0?N] WNkn0G[k]
Linearity ag[n]+bh[n] aG[k]+bH[k]
h[n] H[k]
g[n] G[k]
§ 3.5 Circular Shift of a Sequence
This property is analogous to the time-
shifting property of the DTFT,but with
a subtle difference
Consider length-N sequences defined for
0≤n≤N-1
Sample values of such sequences are
equal to zero for values of n < 0 and
n≥N
§ 3.5 Circular Shift of a Sequence
If x[n] is such a sequence,then for any
arbitrary integer n0,the shifted sequence
x1[n] = x[n – n0]
is no longer defined for the range 0≤n≤N-1
We thus need to define another type of a shift
that will always keep the shifted sequence in
the range 0≤n≤N-1
§ 3.5 Circular Shift of a Sequence
The desired shift,called the circular
shift,is defined using a modulo
operation:
][][ Noc nnxnx
],[
],[][
nnNx
nnxnx
o
oc
o
o
nn
Nnn
0f o r
1f o r
For n0>0 (right circular shift),the above
equation implies
§ 3.5 Circular Shift of a Sequence
Illustration of the concept of a circular shift
][nx ]1[ 6nx
]5[ 6 nx
]4[ 6nx
]2[ 6 nx
§ 3.5 Circular Shift of a Sequence
As can be seen from the previous figure,
a right circular shift by n0 is equivalent
to a left circular shift by N-n0 sample
periods
A circular shift by an integer number
greater than N is equivalent to a circular
shift by?n0?N
§ 3.5 Circular Shift of a Sequence
x[n-1]
x[n]
x[<n-1>N]
n=<4>4=0
§ 3.6 Circular Convolution
This operation is analogous to linear
convolution,but with a subtle difference
Consider two length-N sequences,g[n]
and h[n],respectively
Their linear convolution results in a
length-(2N-1) sequence yL[n] given by
220
1
0
Nnmnhmgny
N
m
L ],[][][
§ 3.6 Circular Convolution
In computing yL[n] we have assumed that both
length-N sequences have been zero-padded to
extend their lengths to 2N-1
The longer form of yL[n] results from the
time-reversal of the sequence h[n] and its
linear shift to the right
The first nonzero value of yL[n] is
yL[n]=g[0]h[0],and the last nonzero value is
yL[2N-2]=g[N-1]h[N-1]
§ 3.6 Circular Convolution
To develop a convolution-like operation
resulting in a length-N sequence yC[n],
we need to define a circular time-
reversal,and then apply a circular time-
shift
Resulting operation,called a circular
convolution,is defined by
10],[][][
1
0
Nnmnhmgny
N
m
NC
§ 3.6 Circular Convolution
Since the operation defined involves two
length-N sequences,it is often referred
to as an N-point circular convolution,
denoted as
N Ng[n] h[n] = h[n] g[n]
The circular convolution is commutative,i.e.
Ny[n] = g[n] h[n]
§ 3.6 Circular Convolution
Example - Determine the 4-point circular
convolution of the two length-4 sequences:
},{]}[{ 1021?ng }{]}[{ 1122?nh
n
3210
1
2 ][ng
n
3210
1
2 ][nh
as sketched below
§ 3.6 Circular Convolution
The result is a length-4 sequence yC[n]
given by
3
0
4 ][][]0[
m
C mhmgy
]1[]3[]2[]2[]3[]1[]0[]0[ hghghghg
621101221 )()()()(
,][][][][][
3
0
4
m
C mnhmgnhngny 4
30 nFrom the above we observe
§ 3.6 Circular Convolution
Likewise
3
0
4 ]1[][]1[
m
C mhmgy
][][][][][][][][ 23320110 hghghghg
711102221 )()()()(
3
0
4 ]2[][]2[
m
C mhmgy
][][][][][][][][ 33021120 hghghghg
611202211 )()()()(
§ 3.6 Circular Convolution
The circular
convolution can also
be computed using a
DFT-based approach
3
0
4 ]3[][]3[
m
C mhmgy
][][][][][][][][ 03122130 hghghghg
521201211 )()()()(
][nyC
§ 3.6 Circular Convolution
Example - Consider the two length-4
sequences repeated below for convenience:
n
3210
1
2 ][ng
n
3210
1
2 ][nh
4210 /][][][ kjeggkG
4644 32 // ][][ kjkj egeg
3021 232 kee kjkj,//
The 4-point DFT G[k] of g[n] is given by
§ 3.6 Circular Convolution
Therefore
,][ 21212G
,][ jjjG 1211
jjjG 1213 ][
,][ 41210G
4210 /][][][ kjehhkH
4644 32 // ][][ kjkj eheh
3022 232 keee kjkjkj,//
Likewise,
§ 3.6 Circular Convolution
Hence,,][ 611220H
,][ 011222H
,][ jjjH 11221
jjjH 11223 ][
Homework
Read textbook from p.117 to 155
Problems
3.1,3.4,3.6,3.8,3.13,3.18,3.22,3.25,
3.50,3.51,3.56,3.64,3.65,3.74
M3.2,M3.8,M3.9
