Copyright ? 2001,S,K,Mitra
1
DTFT Properties
? Example - Determine the DTFT of
? Let
? We can therefore write
? From Table 3.1,the DTFT of x[n] is given
by
1],[)1(][ ?????? nnny n
1],[][ ????? nnx n
][][][ nxnxnny ??
??
?
??
? jj
e
eX
1
1)(
)( ?jeY
Copyright ? 2001,S,K,Mitra
2
DTFT Properties
? Using the differentiation property of the
DTFT given in Table 3.2,we observe that
the DTFT of is given by
? Next using the linearity property of the
DTFT given in Table 3.2 we arrive at
][nxn
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
Copyright ? 2001,S,K,Mitra
3
DTFT Properties
? Example - Determine the DTFT of
the sequence v[n] defined by
? From Table 3.1,the DTFT of is 1
? Using the time-shifting property of the
DTFT given in Table 3.2 we observe that
the DTFT of is and the DTFT
of is ][ 1?nv
]1[][]1[][ 1010 ??????? npnpnvdnvd
][n?
]1[ ?? n ??je
)( ?jeV
)( ??? jj eVe
Copyright ? 2001,S,K,Mitra
4
DTFT Properties
? Using the linearity property of Table 3.2 we
then obtain the frequency-domain
representation of
as
? Solving the above equation we get
]1[][]1[][ 1010 ??????? npnpnvdnvd
?????? ??? jjjj eppeVedeVd 1010 )()(
??
??
?
?
??
j
j
j
edd
eppeV
10
10)(
Copyright ? 2001,S,K,Mitra
5
Energy Density Spectrum
? The total energy of a finite-energy sequence
g[n] is given by
? From Parseval’s relation given in Table 3.2
we observe that
2[]
g
n
gn
?
? ??
? ?E
22 1
[ ] ( )
2
j
g
n
g n G e d
?
?
?
?
?
?
? ?? ?
??? ?E
Copyright ? 2001,S,K,Mitra
6
Energy Density Spectrum
? The quantity
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
Copyright ? 2001,S,K,Mitra
7
Energy Density Spectrum
? Example - Compute the energy of the
sequence
? Here
where
[ ] sin c,ccLP nh n n??
??
??? ? ? ? ? ?
????
? ????
?
??
??
???
deHnh jLP
n
LP
22
)(
2
1][
?
?
?
?????
????
??
c
cj
LP eH,0
0,1
)(
Copyright ? 2001,S,K,Mitra
8
Energy Density Spectrum
? Therefore
? Hence,is a finite-energy sequence
??
?
??
? ????
?
??
?
???
c
n
LP
c
c
dnh
2
1][ 2
][nhLP
Copyright ? 2001,S,K,Mitra
9
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 in the
form of
at a prescribed set of discrete frequency
points
Nj
N
j
Mj
M
j
j
ededd
epeppeX
????
????
?
???
????
.,,,
.,,,)(
10
10
????
je?
Copyright ? 2001,S,K,Mitra
10
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 and,respectively,at a
prescribed set of frequencies between 0 and
? (or 2?) given by the vector w
}{ ip }{ id
Copyright ? 2001,S,K,Mitra
11
DTFT Computation Using
MATLAB
? Example - Plot magnitude and phase of the
DTFT
????
????
????
????
?
??
??
??
??
?
43
2
43
2
41.06.1
7.237.21
0 0 8.00 3 3.0
05.00 3 3.00 0 8.0
)(
jj
jj
jj
jj
j
ee
ee
ee
ee
eX
Copyright ? 2001,S,K,Mitra
12
DTFT Computation Using MATLAB
>> num=[0.008 -0.033 0.05 -0.033 0.008];
>> den=[1 2.37 2.7 1.6 0.41];
>> om=[0:pi/256:pi];
>> H=freqz(num,den,om);
>> figure(1)
>> plot(om/pi,abs(H),'LineWidth',2)
>> xlabel('\omega/\pi')
>> ylabel('|H(e^{j\omega})|')
>> title('Magnitude Response')
>>grid on
Copyright ? 2001,S,K,Mitra
13
DTFT Computation Using MATLAB
Copyright ? 2001,S,K,Mitra
14
DTFT Computation Using MATLAB
>> figure(2)
>> plot(om/pi,angle(H),'LineWidth',2)
>> xlabel('\omega/\pi')
>> ylabel('phase(H(e^{j\omega}))')
>> title('Phase Response')
>> grid on
Copyright ? 2001,S,K,Mitra
15
DTFT Computation Using MATLAB
Copyright ? 2001,S,K,Mitra
16
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 in the next
slide
Copyright ? 2001,S,K,Mitra
17
DTFT Computation Using MATLAB
Copyright ? 2001,S,K,Mitra
18
Linear Convolution Using
DTFT
? An important property of the DTFT is given
by the convolution theorem in Table 3.2
? It states that if y[n] = x[n] h[n],then the
DTFT of y[n] is given by
? 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,
*
)( ?jeY
)()()( ??? ? jjj eHeXeY
Copyright ? 2001,S,K,Mitra
19
Linear Convolution Using
DTFT
1) Compute the DTFTs and of
the sequences x[n] and h[n],respectively
2) Form the DTFT
3) Compute the IDFT y[n] of
)()()( ??? ? jjj eHeXeY
)( ?jeX )( ?jeH
)( ?jeY
?x[n]
h[n]
y[n]
DTFT
DTFT
IDTFT
)( ?jeY)(
?jeX
)( ?jeH
Copyright ? 2001,S,K,Mitra
20
Discrete Fourier Transform
? Definition - The simplest relation between a
length-N sequence x[n],defined for
,and its DTFT is
obtained by uniformly sampling on
the ?-axis between at,
? From the definition of the DTFT we thus have
10 ??? Nn
10 ??? Nk
)( ?jeX
)( ?jeX
???? 20 Nkk /2 ???
,][)(][
1
0
/2
/2 ?
??
?
?
??
???
? N
n
Nkj
Nk
j enxeXkX
10 ??? Nk
Copyright ? 2001,S,K,Mitra
21
Discrete Fourier Transform
? 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 the DFT
is usually expressed as,
NjN eW /2 ???
10,][][
1
0
?????
?
?
NkWnxkX
N
n
nk
N
Copyright ? 2001,S,K,Mitra
22
Discrete Fourier Transform
? The inverse discrete Fourier transform
(IDFT) is given by
? To verify the above expression we multiply
both sides of the above equation by
and sum the result from n = 0 to 1?? Nn
nNW?
10,][1][
1
0
?????
?
?
? NnWkX
Nnx
N
k
kn
N
Copyright ? 2001,S,K,Mitra
23
Discrete Fourier Transform
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
)(][ ?
Copyright ? 2001,S,K,Mitra
24
Discrete Fourier Transform
? Making use of the identity
we observe that the RHS of the last
equation is equal to
? Hence
??
????
?
??1
0
N
n
nk
NW
)( ?
,
,
0
N,rNk ?? ?f o r
o th e rw is e
r an integer
][?X
][][ ?? XWnx
N
n
n
N ??
?
?
1
0
Copyright ? 2001,S,K,Mitra
25
Discrete Fourier Transform 1
2/
0
[ ] [ ],0 1
N
j k n N
n
X k x n e k N?
?
?
?
? ? ? ??
1
2/
0
1[ ] [ ],0 1N j k n N
k
x n X k e n N
N
?
?
?
? ? ? ??
[]Xk[]xn
DFT,analysis equation
IDFT,synthesis equation
time
domain
frequency
domain
Copyright ? 2001,S,K,Mitra
26
Discrete Fourier Transform
? Example - Consider the length-N sequence
? Its N-point DFT is given by
110
01
???
?
Nn
n
,
,
??
??][ nx
10 0
1
0
??? ?
?
?
N
N
n
kn
N WxWnxkX ][][][
10 ??? Nk
Copyright ? 2001,S,K,Mitra
27
Discrete Fourier Transform
? Example - Consider the length-N sequence
? Its N-point DFT is given by
??
??][ ny
11100
1
???????
?
Nnmmn
mn
,,
,
km
N
km
N
N
n
kn
N WWmyWnykY ??? ?
?
?
][][][
1
0
10 ??? Nk
Copyright ? 2001,S,K,Mitra
28
Discrete Fourier Transform
? Example - Consider the length-N sequence
defined for
? Using a trigonometric identity we can write
10),/2c o s (][ ????? NrNrnng
? )NrnjNrnj eeng /2/221][ ??? ??
? )rNNrNN WW ?? ?21
10 ??? Nn
Copyright ? 2001,S,K,Mitra
29
Discrete Fourier Transform
? 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
Copyright ? 2001,S,K,Mitra
30
Discrete Fourier Transform
? Making use of the identity
we get
??
?
?
?
??
?
?
o t h e r w i se0
f o r2
f o r2
,
,/
,/
][ rNkN
rkN
kG
??
????
?
??1
0
N
n
nk
NW
)( ?
,
,
0
N,rNk ?? ?f o r
o th e rw is e
r an integer
10 ??? Nk
Copyright ? 2001,S,K,Mitra
31
Matrix Relations
? The DFT samples defined by
can be expressed in matrix form as
where
10,][][
1
0
?????
?
?
NkWnxkX
N
n
kn
N
xDX N?
? ? TNXXX ][.,,,,][][ 110 ??X
? ? TNxxx ][.,,,,][][ 110 ??x
Copyright ? 2001,S,K,Mitra
32
Matrix Relations
and is the DFT matrix given by
ND NN ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
2
1121
1242
121
1
1
1
1111
)()()(
)(
)(
N
N
N
N
N
N
N
NNN
N
NNN
N
WWW
WWW
WWW
?
?????
?
?
?
D
Copyright ? 2001,S,K,Mitra
33
Matrix Relations
? Likewise,the IDFT relation given by
can be expressed in matrix form as
where is the IDFT matrix
10,][][
1
0
?????
?
?
? NnWkXnx N
k
nk
N
NN ?1?ND
XDx 1?? N
Copyright ? 2001,S,K,Mitra
34
Matrix Relations
where
? Note,
2
1 2 ( 1 )
1 2 4 2 ( 1 )
( 1 ) 2 ( 1 ) ( 1 )
1 1 1 1
1
1
1
1
N
NN N
N
N NN N
N N N
N N N
W W W
W W W
N
W W W
? ? ? ?
? ? ? ? ?
? ? ? ? ? ?
??
??
??
?
??
????
D
L
L
L
M M M O M
L
*NN
N DD
11 ??
Copyright ? 2001,S,K,Mitra
35
DFT Computation Using
MATLAB
? The functions to compute the DFT and the
IDFT are fft and ifft
? These functions make use of Fast Fourier
Transform (FFT) algorithms which are
computationally highly efficient compared
to the direct computation
? Programs 3_2 and 3_4 illustrate the use of
these functions
Copyright ? 2001,S,K,Mitra
36
DFT Computation Using
MATLAB
? Example - Program 3_4 can be used to
compute the DFT and the DTFT of the
sequence
as shown below
150),16/6c o s (][ ???? nnnx
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
indicates DFT samples
Copyright ? 2001,S,K,Mitra
37
DTFT from DFT by
Interpolation
? The N-point DFT X[k] of a length-N
sequence x[n] is simply the frequency
samples of its DTFT evaluated at N
uniformly spaced frequency points
? Given the N-point DFT X[k] of a length-N
sequence x[n],its DTFT can be
uniquely determined from X[k]
)( ?jeX
)( ?jeX
10,/2 ???????? NkNkk
Copyright ? 2001,S,K,Mitra
38
DTFT from DFT by
Interpolation
? Thus
??
?
?
??? 1
0
][)(
N
n
njj enxeX
njN
n
N
k
nk
N eWkXN
???
?
?
?
??
??
?
??
? ?? 1
0
1
0
][1
? ??
?
?
?
?
????1
0
1
0
)/2(][1 N
k
N
n
nNkjekX
N
Copyright ? 2001,S,K,Mitra
39
DTFT from DFT by
Interpolation
? It can readily be shown that
? ?
?
?
?
?
?
? ???
?
?
?
?
?
? ???
?
?
?
?????
1
0
]2/)1) ] [(/2[(
2
2
si n
2
2
si n
][
1 N
k
NNkj
e
N
kN
kN
kX
N
()jXe ? ?
Copyright ? 2001,S,K,Mitra
40
Sampling the DTFT
? Consider a sequence x[n] with a DTFT
? We sample at N equally spaced points
,developing the N
frequency samples
? These N frequency samples can be
considered as an N-point DFT Y[k] whose N-
point IDFT is a length-N sequence y[n]
)( ?jeX
)( ?jeX
Nkk /2 ??? 10 ??? Nk
)}({ kjeX ?
Copyright ? 2001,S,K,Mitra
41
Sampling the DTFT
? Now
? Thus
? An IDFT of Y[k] yields
??
?
???
???
?
?? jj exeX ][)(
)()(][ /2 Nkjj eXeXkY k ?? ??
????
?
???
?
???
??
?
?
?
? ?? k
N
Nkj Wxex ][][ /2
??
?
?
?1
0
][1][
N
k
nk
NWkYNny
Copyright ? 2001,S,K,Mitra
42
Sampling the DTFT
? i.e,
? Making use of the identity
? ?
?
?
??
???
?
1
0
1 N
k
nk
N
k
N WWxNny
?
?
? ][][
?
?
?
?
?
?? ?? ?
?
???
???
1
0
1 N
k
nk
NWNx
)(][ ?
?
?
??
????
?
??1
0
1 N
n
rnk
NWN
)(
,
,
0
1 mNnr ??f o r
o th e rw is e
Copyright ? 2001,S,K,Mitra
43
Sampling the DTFT
we arrive at the desired relation
? Thus y[n] is obtained from x[n] by adding
an infinite number of shifted replicas of
x[n],with each replica shifted by an integer
multiple of N sampling instants,and
observing the sum only for the interval
10 ????? ?
?
???
NnmNnxny
m
],[][
10 ??? Nn
Copyright ? 2001,S,K,Mitra
44
Sampling the DTFT
? To apply
to finite-length sequences,we assume that
the samples outside the specified range are
zeros
? Thus if x[n] is a length-M sequence with
,then y[n] = x[n] for
10 ????? ?
?
???
NnmNnxny
m
],[][
NM ? 10 ??? Nn
Copyright ? 2001,S,K,Mitra
45
Sampling the DTFT
? If M > N,there is a time-domain aliasing of
samples of x[n] in generating y[n],and x[n]
cannot be recovered from y[n]
? Example - Let
? By sampling its DTFT at,
and then applying a 4-point IDFT to
these samples,we arrive at the sequence y[n]
given by
}{]}[{ 543210?nx ?
)( ?jeX 4/2 kk ???
30 ?? k
Copyright ? 2001,S,K,Mitra
46
Sampling the DTFT
,
i.e,
? {x[n]} cannot be recovered from {y[n]}
][][][][ 44 ????? nxnxnxny 30 ?? n
}{]}[{ 3264?ny ?
Copyright ? 2001,S,K,Mitra
47
Numerical Computation of the
DTFT Using the DFT
? A practical approach to the numerical
computation of the DTFT of a finite-length
sequence
? Let be the DTFT of a length-N
sequence x[n]
? We wish to evaluate on a dense grid
of frequencies,,
where M >> N,
)( ?jeX
)( ?jeX
Mkk /2 ??? 10 ??? Mk
Copyright ? 2001,S,K,Mitra
48
Numerical Computation of the
DTFT Using the DFT
? Define a new sequence
? Then
????
?
?
???
?
??? 1
0
/21
0
][][)(
N
n
MknjN
n
njj enxenxeX kk
?
?
?
???
????
1,0
10],[][
MnN
Nnnxnx
e
1
2/
0
( ) [ ]k
M
j j k n M
e
n
X e x n e? ?
?
?
?
? ?
Copyright ? 2001,S,K,Mitra
49
Numerical Computation of the
DTFT Using the DFT
? Thus is essentially an M-point DFT
of the length-M sequence
? The DFT can be computed very
efficiently using the FFT algorithm if M is
an integer power of 2
? The function freqz employs this approach
to evaluate the frequency response at a
prescribed set of frequencies of a DTFT
expressed as a rational function of
)( kjeX ?
][kX e ][nxe
][kX e
??je
Copyright ? 2001,S,K,Mitra
50
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
Copyright ? 2001,S,K,Mitra
51
General Properties of DFT
Copyright ? 2001,S,K,Mitra
52
DFT Properties,
Symmetry Relations
x[n] is a complex sequence
Copyright ? 2001,S,K,Mitra
53
DFT Properties,
Symmetry Relations
x[n] is a real sequence
Copyright ? 2001,S,K,Mitra
54
Circular Shift of a Sequence
? This property is analogous to the time-
shifting property of the DTFT as given in
the first table,but with a subtle difference
? Consider length-N sequences defined for
? Sample values of such sequences are equal
to zero for values of n < 0 and Nn ?
10 ??? Nn
Copyright ? 2001,S,K,Mitra
55
Circular Shift of a Sequence
? If x[n] is such a sequence,then for any
arbitrary integer,the shifted sequence
is no longer defined for the range
? We thus need to define another type of a
shift that will always keep the shifted
sequence in the range
][][ onnxnx ??1
on
10 ??? Nn
10 ??? Nn
Copyright ? 2001,S,K,Mitra
56
Circular Shift of a Sequence
? The desired shift,called the circular shift,
is defined using a modulo operation,
? For (right circular shift),the above
equation implies
][][ Noc nnxnx ????
0?on
??
?
??
??
],[
],[][
nnNx
nnxnx
o
oc
o
o
nn
Nnn
??
???
0f o r
1f o r
Copyright ? 2001,S,K,Mitra
57
Circular Shift of a Sequence
? Illustration of the concept of a circular shift
][nx ]1[ 6???nx
]5[ 6???? nx ]2[ 6???? nx
]4[ 6???nx
Copyright ? 2001,S,K,Mitra
58
Circular Shift of a Sequence
? As can be seen from the previous figure,a
right circular shift by is equivalent to a
left circular shift by sample periods
? A circular shift by an integer number
greater than N is equivalent to a circular
shift by
on
onN ?
on
Non ??
Copyright ? 2001,S,K,Mitra
59
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-
sequence given by )( 12 ?N
220
1
0
????? ?
?
?
Nnmnhmgny
N
m
L ],[][][
][nyL
Copyright ? 2001,S,K,Mitra
60
Circular Convolution
? In computing we have assumed that
both length-N sequences have been zero-
padded to extend their lengths to
? The longer form of results from the
time-reversal of the sequence h[n] and its
linear shift to the right
? The first nonzero value of is
,and the last nonzero value
is
12 ?N
][nyL
][nyL
][nyL
][][][ 000 hgy L ?
][][][ 1122 ???? NhNgNy L
Copyright ? 2001,S,K,Mitra
61
Circular Convolution
? To develop a convolution-like operation
resulting in a length-N sequence,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
][nyC
Copyright ? 2001,S,K,Mitra
62
Circular Convolution
? Since the operation defined involves two
length-N sequences,it is often referred to as
an N-point circular convolution,denoted as
y[n] = g[n] h[n]
? The circular convolution is commutative,
i.e,
g[n] h[n] = h[n] g[n]
N
N N
Copyright ? 2001,S,K,Mitra
63
Circular Convolution
? Example - Determine the 4-point circular
convolution of the two length-4 sequences,
as sketched below
},{]}[{ 1021?ng }{]}[{ 1122?nh
? ?
n
3210
1
2 ][ng
n
3210
1
2 ][nh
Copyright ? 2001,S,K,Mitra
64
Circular Convolution
? The result is a length-4 sequence
given by
? From the above we observe
][nyC
,][][][][][
3
0
4? ?????
?m
C mnhmgnhngny 4
30 ?? n
? ????
?
3
0
4 ][][]0[
m
C mhmgy
]1[]3[]2[]2[]3[]1[]0[]0[ hghghghg ????
621101221 ????????? )()()()(
Copyright ? 2001,S,K,Mitra
65
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 ????????? )()()()(
Copyright ? 2001,S,K,Mitra
66
Circular Convolution
and
? The circular convolution can also be
computed using a DFT-based approach as
indicated in Table 3.5
521201211 ????????? )()()()(
][][][][][][][][ 03122130 hghghghg ????
? ????
?
3
0
4 ]3[][]3[
m
C mhmgy
][nyC
Copyright ? 2001,S,K,Mitra
67
Circular Convolution
? Example - Consider the two length-4
sequences repeated below for convenience,
? The 4-point DFT G[k] of g[n] is given by
n
3210
1
2 ][ng
n
3210
1
2 ][nh
4210 /][][][ kjeggkG ????
4644 32 // ][][ kjkj egeg ?? ?? ??
3021 232 ????? ?? kee kjkj,// ??
Copyright ? 2001,S,K,Mitra
68
Circular Convolution
? Therefore
? Likewise,
,][ 21212 ?????G
,][ jjjG ????? 1211
jjjG ????? 1213 ][
,][ 41210 ????G
4210 /][][][ kjehhkH ????
4644 32 // ][][ kjkj eheh ?? ?? ??
3022 232 ?????? ??? keee kjkjkj,// ???
Copyright ? 2001,S,K,Mitra
69
Circular Convolution
? Hence,
? The two 4-point DFTs can also be
computed using the matrix relation given
earlier
,][ 611220 ?????H
,][ 011222 ?????H
,][ jjjH ?????? 11221
jjjH ?????? 11223 ][
Copyright ? 2001,S,K,Mitra
70
Circular Convolution
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
j
j
jj
jj
g
g
g
g
G
G
G
G
1
2
1
4
1
0
2
1
11
1111
11
1111
3
2
1
0
3
2
1
0
4
][
][
][
][
][
][
][
][
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
j
j
jj
jj
h
h
h
h
H
H
H
H
1
0
1
6
1
1
2
2
11
1111
11
1111
3
2
1
0
3
2
1
0
4
][
][
][
][
][
][
][
][
D
is the 4-point DFT matrix 4D
Copyright ? 2001,S,K,Mitra
71
Circular Convolution
? If denotes the 4-point DFT of
then from Table 3.5 we observe
? Thus
30 ??? kkHkGkY C ],[][][
][kYC ][nyC
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2
0
2
24
33
22
11
00
3
2
1
0
j
j
HG
HG
HG
HG
Y
Y
Y
Y
C
C
C
C
][][
][][
][][
][][
][
][
][
][
Copyright ? 2001,S,K,Mitra
72
Circular Convolution
? The 4-point IDFT of yields
][kYC
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
][
][
][
][
*
][
][
][
][
3
2
1
0
4
1
3
2
1
0
4
C
C
C
C
C
C
C
C
Y
Y
Y
Y
y
y
y
y
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
5
6
7
6
2
0
2
24
11
1111
11
1111
4
1
j
j
jj
jj
Copyright ? 2001,S,K,Mitra
73
Circular Convolution
? Example - Now let us extended the two
length-4 sequences to length 7 by
appending each with three zero-valued
samples,i.e,
??
?
??
???
640
30
n
nngng
e,
],[][
??
?
??
???
640
30
n
nnhnh
e,
],[][
Copyright ? 2001,S,K,Mitra
74
Circular Convolution
? We next determine the 7-point circular
convolution of and,
? From the above
60,][][][
6
0
7 ??? ????
?
nmnhmgny
m
ee
][nge ][nhe
][][][][][ 61000 eeee hghgy ??
][][][][][][][][ 16253443 eeeeeeee hghghghg ????
22100 ???? ][][ hg
Copyright ? 2001,S,K,Mitra
75
Circular Convolution
? Continuing the process we arrive at
,)()(][][][][][ 6222101101 ??????? hghgy
][][][][][][][ 0211202 hghghgy ???
,)()()( 5202211 ??????? ][][][][][][][][][ 031221303 hghghghgy ????
,)()()()( 521201211 ????????? ][][][][][][][ 1322314 hghghgy ???
,)()()( 4211012 ???????
Copyright ? 2001,S,K,Mitra
76
Circular Convolution
? As can be seen from the above that y[n] is
precisely the sequence obtained by a
linear convolution of g[n] and h[n]
,)()(][][][][][ 1111023325 ??????? hghgy
111336 ???? )(][][][ hgy
][nyL
][nyL
Copyright ? 2001,S,K,Mitra
77
Circular Convolution
? The N-point circular convolution can be
written in matrix form as
? Note,The elements of each diagonal of the
matrix are equal
? Such a matrix is called a circulant matrix
NN ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
??
?
?
?
?
?
?
?
?
?
?
?
?
]1[
]2[
]1[
]0[
]0[]3[]2[]1[
]3[]0[]1[]2[
]2[]1[]0[]1[
]1[]2[]1[]0[
]1[
]2[
]1[
]0[
Ng
g
g
g
hNhNhNh
hhhh
hNhhh
hNhNhh
Ny
y
y
y
C
C
C
C
?
?
?????
?
?
?
?
Copyright ? 2001,S,K,Mitra
78
Linear Convolution Using the
DFT
? Linear convolution is a key operation in
many signal processing applications
? Since a DFT can be efficiently implemented
using FFT algorithms,it is of interest to
develop methods for the implementation of
linear convolution using the DFT
Copyright ? 2001,S,K,Mitra
79
Linear Convolution of Two
Finite-Length Sequences
? Let g[n] and h[n] be two finite-length
sequences of length N and M,respectively
? Denote
? Define two length-L sequences
1??? MNL
??
?
???
????
10
10
LnN
Nnngng
e,
],[][
??
?
???
????
10
10
LnM
Mnnhnh
e,
],[][
Copyright ? 2001,S,K,Mitra
80
Linear Convolution of Two
Finite-Length Sequences
? Then
? The corresponding implementation scheme
is illustrated below
][][][][][][ nhngnynhngny CL ???* L
Zero-padding
with zero s1)( ?N point DFT
Zero-padding
with z e ro s1)( ?M ??? )( 1MNpoint DFT
?
g[n]
h[n]
Length-N
][nge
][nhe ??? )( 1MN
??? )( 1MN
point IDFT
][nyL
Length-M Length- )( 1?? MN
1
DTFT Properties
? Example - Determine the DTFT of
? Let
? We can therefore write
? From Table 3.1,the DTFT of x[n] is given
by
1],[)1(][ ?????? nnny n
1],[][ ????? nnx n
][][][ nxnxnny ??
??
?
??
? jj
e
eX
1
1)(
)( ?jeY
Copyright ? 2001,S,K,Mitra
2
DTFT Properties
? Using the differentiation property of the
DTFT given in Table 3.2,we observe that
the DTFT of is given by
? Next using the linearity property of the
DTFT given in Table 3.2 we arrive at
][nxn
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
Copyright ? 2001,S,K,Mitra
3
DTFT Properties
? Example - Determine the DTFT of
the sequence v[n] defined by
? From Table 3.1,the DTFT of is 1
? Using the time-shifting property of the
DTFT given in Table 3.2 we observe that
the DTFT of is and the DTFT
of is ][ 1?nv
]1[][]1[][ 1010 ??????? npnpnvdnvd
][n?
]1[ ?? n ??je
)( ?jeV
)( ??? jj eVe
Copyright ? 2001,S,K,Mitra
4
DTFT Properties
? Using the linearity property of Table 3.2 we
then obtain the frequency-domain
representation of
as
? Solving the above equation we get
]1[][]1[][ 1010 ??????? npnpnvdnvd
?????? ??? jjjj eppeVedeVd 1010 )()(
??
??
?
?
??
j
j
j
edd
eppeV
10
10)(
Copyright ? 2001,S,K,Mitra
5
Energy Density Spectrum
? The total energy of a finite-energy sequence
g[n] is given by
? From Parseval’s relation given in Table 3.2
we observe that
2[]
g
n
gn
?
? ??
? ?E
22 1
[ ] ( )
2
j
g
n
g n G e d
?
?
?
?
?
?
? ?? ?
??? ?E
Copyright ? 2001,S,K,Mitra
6
Energy Density Spectrum
? The quantity
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
Copyright ? 2001,S,K,Mitra
7
Energy Density Spectrum
? Example - Compute the energy of the
sequence
? Here
where
[ ] sin c,ccLP nh n n??
??
??? ? ? ? ? ?
????
? ????
?
??
??
???
deHnh jLP
n
LP
22
)(
2
1][
?
?
?
?????
????
??
c
cj
LP eH,0
0,1
)(
Copyright ? 2001,S,K,Mitra
8
Energy Density Spectrum
? Therefore
? Hence,is a finite-energy sequence
??
?
??
? ????
?
??
?
???
c
n
LP
c
c
dnh
2
1][ 2
][nhLP
Copyright ? 2001,S,K,Mitra
9
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 in the
form of
at a prescribed set of discrete frequency
points
Nj
N
j
Mj
M
j
j
ededd
epeppeX
????
????
?
???
????
.,,,
.,,,)(
10
10
????
je?
Copyright ? 2001,S,K,Mitra
10
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 and,respectively,at a
prescribed set of frequencies between 0 and
? (or 2?) given by the vector w
}{ ip }{ id
Copyright ? 2001,S,K,Mitra
11
DTFT Computation Using
MATLAB
? Example - Plot magnitude and phase of the
DTFT
????
????
????
????
?
??
??
??
??
?
43
2
43
2
41.06.1
7.237.21
0 0 8.00 3 3.0
05.00 3 3.00 0 8.0
)(
jj
jj
jj
jj
j
ee
ee
ee
ee
eX
Copyright ? 2001,S,K,Mitra
12
DTFT Computation Using MATLAB
>> num=[0.008 -0.033 0.05 -0.033 0.008];
>> den=[1 2.37 2.7 1.6 0.41];
>> om=[0:pi/256:pi];
>> H=freqz(num,den,om);
>> figure(1)
>> plot(om/pi,abs(H),'LineWidth',2)
>> xlabel('\omega/\pi')
>> ylabel('|H(e^{j\omega})|')
>> title('Magnitude Response')
>>grid on
Copyright ? 2001,S,K,Mitra
13
DTFT Computation Using MATLAB
Copyright ? 2001,S,K,Mitra
14
DTFT Computation Using MATLAB
>> figure(2)
>> plot(om/pi,angle(H),'LineWidth',2)
>> xlabel('\omega/\pi')
>> ylabel('phase(H(e^{j\omega}))')
>> title('Phase Response')
>> grid on
Copyright ? 2001,S,K,Mitra
15
DTFT Computation Using MATLAB
Copyright ? 2001,S,K,Mitra
16
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 in the next
slide
Copyright ? 2001,S,K,Mitra
17
DTFT Computation Using MATLAB
Copyright ? 2001,S,K,Mitra
18
Linear Convolution Using
DTFT
? An important property of the DTFT is given
by the convolution theorem in Table 3.2
? It states that if y[n] = x[n] h[n],then the
DTFT of y[n] is given by
? 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,
*
)( ?jeY
)()()( ??? ? jjj eHeXeY
Copyright ? 2001,S,K,Mitra
19
Linear Convolution Using
DTFT
1) Compute the DTFTs and of
the sequences x[n] and h[n],respectively
2) Form the DTFT
3) Compute the IDFT y[n] of
)()()( ??? ? jjj eHeXeY
)( ?jeX )( ?jeH
)( ?jeY
?x[n]
h[n]
y[n]
DTFT
DTFT
IDTFT
)( ?jeY)(
?jeX
)( ?jeH
Copyright ? 2001,S,K,Mitra
20
Discrete Fourier Transform
? Definition - The simplest relation between a
length-N sequence x[n],defined for
,and its DTFT is
obtained by uniformly sampling on
the ?-axis between at,
? From the definition of the DTFT we thus have
10 ??? Nn
10 ??? Nk
)( ?jeX
)( ?jeX
???? 20 Nkk /2 ???
,][)(][
1
0
/2
/2 ?
??
?
?
??
???
? N
n
Nkj
Nk
j enxeXkX
10 ??? Nk
Copyright ? 2001,S,K,Mitra
21
Discrete Fourier Transform
? 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 the DFT
is usually expressed as,
NjN eW /2 ???
10,][][
1
0
?????
?
?
NkWnxkX
N
n
nk
N
Copyright ? 2001,S,K,Mitra
22
Discrete Fourier Transform
? The inverse discrete Fourier transform
(IDFT) is given by
? To verify the above expression we multiply
both sides of the above equation by
and sum the result from n = 0 to 1?? Nn
nNW?
10,][1][
1
0
?????
?
?
? NnWkX
Nnx
N
k
kn
N
Copyright ? 2001,S,K,Mitra
23
Discrete Fourier Transform
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
)(][ ?
Copyright ? 2001,S,K,Mitra
24
Discrete Fourier Transform
? Making use of the identity
we observe that the RHS of the last
equation is equal to
? Hence
??
????
?
??1
0
N
n
nk
NW
)( ?
,
,
0
N,rNk ?? ?f o r
o th e rw is e
r an integer
][?X
][][ ?? XWnx
N
n
n
N ??
?
?
1
0
Copyright ? 2001,S,K,Mitra
25
Discrete Fourier Transform 1
2/
0
[ ] [ ],0 1
N
j k n N
n
X k x n e k N?
?
?
?
? ? ? ??
1
2/
0
1[ ] [ ],0 1N j k n N
k
x n X k e n N
N
?
?
?
? ? ? ??
[]Xk[]xn
DFT,analysis equation
IDFT,synthesis equation
time
domain
frequency
domain
Copyright ? 2001,S,K,Mitra
26
Discrete Fourier Transform
? Example - Consider the length-N sequence
? Its N-point DFT is given by
110
01
???
?
Nn
n
,
,
??
??][ nx
10 0
1
0
??? ?
?
?
N
N
n
kn
N WxWnxkX ][][][
10 ??? Nk
Copyright ? 2001,S,K,Mitra
27
Discrete Fourier Transform
? Example - Consider the length-N sequence
? Its N-point DFT is given by
??
??][ ny
11100
1
???????
?
Nnmmn
mn
,,
,
km
N
km
N
N
n
kn
N WWmyWnykY ??? ?
?
?
][][][
1
0
10 ??? Nk
Copyright ? 2001,S,K,Mitra
28
Discrete Fourier Transform
? Example - Consider the length-N sequence
defined for
? Using a trigonometric identity we can write
10),/2c o s (][ ????? NrNrnng
? )NrnjNrnj eeng /2/221][ ??? ??
? )rNNrNN WW ?? ?21
10 ??? Nn
Copyright ? 2001,S,K,Mitra
29
Discrete Fourier Transform
? 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
Copyright ? 2001,S,K,Mitra
30
Discrete Fourier Transform
? Making use of the identity
we get
??
?
?
?
??
?
?
o t h e r w i se0
f o r2
f o r2
,
,/
,/
][ rNkN
rkN
kG
??
????
?
??1
0
N
n
nk
NW
)( ?
,
,
0
N,rNk ?? ?f o r
o th e rw is e
r an integer
10 ??? Nk
Copyright ? 2001,S,K,Mitra
31
Matrix Relations
? The DFT samples defined by
can be expressed in matrix form as
where
10,][][
1
0
?????
?
?
NkWnxkX
N
n
kn
N
xDX N?
? ? TNXXX ][.,,,,][][ 110 ??X
? ? TNxxx ][.,,,,][][ 110 ??x
Copyright ? 2001,S,K,Mitra
32
Matrix Relations
and is the DFT matrix given by
ND NN ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
2
1121
1242
121
1
1
1
1111
)()()(
)(
)(
N
N
N
N
N
N
N
NNN
N
NNN
N
WWW
WWW
WWW
?
?????
?
?
?
D
Copyright ? 2001,S,K,Mitra
33
Matrix Relations
? Likewise,the IDFT relation given by
can be expressed in matrix form as
where is the IDFT matrix
10,][][
1
0
?????
?
?
? NnWkXnx N
k
nk
N
NN ?1?ND
XDx 1?? N
Copyright ? 2001,S,K,Mitra
34
Matrix Relations
where
? Note,
2
1 2 ( 1 )
1 2 4 2 ( 1 )
( 1 ) 2 ( 1 ) ( 1 )
1 1 1 1
1
1
1
1
N
NN N
N
N NN N
N N N
N N N
W W W
W W W
N
W W W
? ? ? ?
? ? ? ? ?
? ? ? ? ? ?
??
??
??
?
??
????
D
L
L
L
M M M O M
L
*NN
N DD
11 ??
Copyright ? 2001,S,K,Mitra
35
DFT Computation Using
MATLAB
? The functions to compute the DFT and the
IDFT are fft and ifft
? These functions make use of Fast Fourier
Transform (FFT) algorithms which are
computationally highly efficient compared
to the direct computation
? Programs 3_2 and 3_4 illustrate the use of
these functions
Copyright ? 2001,S,K,Mitra
36
DFT Computation Using
MATLAB
? Example - Program 3_4 can be used to
compute the DFT and the DTFT of the
sequence
as shown below
150),16/6c o s (][ ???? nnnx
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
indicates DFT samples
Copyright ? 2001,S,K,Mitra
37
DTFT from DFT by
Interpolation
? The N-point DFT X[k] of a length-N
sequence x[n] is simply the frequency
samples of its DTFT evaluated at N
uniformly spaced frequency points
? Given the N-point DFT X[k] of a length-N
sequence x[n],its DTFT can be
uniquely determined from X[k]
)( ?jeX
)( ?jeX
10,/2 ???????? NkNkk
Copyright ? 2001,S,K,Mitra
38
DTFT from DFT by
Interpolation
? Thus
??
?
?
??? 1
0
][)(
N
n
njj enxeX
njN
n
N
k
nk
N eWkXN
???
?
?
?
??
??
?
??
? ?? 1
0
1
0
][1
? ??
?
?
?
?
????1
0
1
0
)/2(][1 N
k
N
n
nNkjekX
N
Copyright ? 2001,S,K,Mitra
39
DTFT from DFT by
Interpolation
? It can readily be shown that
? ?
?
?
?
?
?
? ???
?
?
?
?
?
? ???
?
?
?
?????
1
0
]2/)1) ] [(/2[(
2
2
si n
2
2
si n
][
1 N
k
NNkj
e
N
kN
kN
kX
N
()jXe ? ?
Copyright ? 2001,S,K,Mitra
40
Sampling the DTFT
? Consider a sequence x[n] with a DTFT
? We sample at N equally spaced points
,developing the N
frequency samples
? These N frequency samples can be
considered as an N-point DFT Y[k] whose N-
point IDFT is a length-N sequence y[n]
)( ?jeX
)( ?jeX
Nkk /2 ??? 10 ??? Nk
)}({ kjeX ?
Copyright ? 2001,S,K,Mitra
41
Sampling the DTFT
? Now
? Thus
? An IDFT of Y[k] yields
??
?
???
???
?
?? jj exeX ][)(
)()(][ /2 Nkjj eXeXkY k ?? ??
????
?
???
?
???
??
?
?
?
? ?? k
N
Nkj Wxex ][][ /2
??
?
?
?1
0
][1][
N
k
nk
NWkYNny
Copyright ? 2001,S,K,Mitra
42
Sampling the DTFT
? i.e,
? Making use of the identity
? ?
?
?
??
???
?
1
0
1 N
k
nk
N
k
N WWxNny
?
?
? ][][
?
?
?
?
?
?? ?? ?
?
???
???
1
0
1 N
k
nk
NWNx
)(][ ?
?
?
??
????
?
??1
0
1 N
n
rnk
NWN
)(
,
,
0
1 mNnr ??f o r
o th e rw is e
Copyright ? 2001,S,K,Mitra
43
Sampling the DTFT
we arrive at the desired relation
? Thus y[n] is obtained from x[n] by adding
an infinite number of shifted replicas of
x[n],with each replica shifted by an integer
multiple of N sampling instants,and
observing the sum only for the interval
10 ????? ?
?
???
NnmNnxny
m
],[][
10 ??? Nn
Copyright ? 2001,S,K,Mitra
44
Sampling the DTFT
? To apply
to finite-length sequences,we assume that
the samples outside the specified range are
zeros
? Thus if x[n] is a length-M sequence with
,then y[n] = x[n] for
10 ????? ?
?
???
NnmNnxny
m
],[][
NM ? 10 ??? Nn
Copyright ? 2001,S,K,Mitra
45
Sampling the DTFT
? If M > N,there is a time-domain aliasing of
samples of x[n] in generating y[n],and x[n]
cannot be recovered from y[n]
? Example - Let
? By sampling its DTFT at,
and then applying a 4-point IDFT to
these samples,we arrive at the sequence y[n]
given by
}{]}[{ 543210?nx ?
)( ?jeX 4/2 kk ???
30 ?? k
Copyright ? 2001,S,K,Mitra
46
Sampling the DTFT
,
i.e,
? {x[n]} cannot be recovered from {y[n]}
][][][][ 44 ????? nxnxnxny 30 ?? n
}{]}[{ 3264?ny ?
Copyright ? 2001,S,K,Mitra
47
Numerical Computation of the
DTFT Using the DFT
? A practical approach to the numerical
computation of the DTFT of a finite-length
sequence
? Let be the DTFT of a length-N
sequence x[n]
? We wish to evaluate on a dense grid
of frequencies,,
where M >> N,
)( ?jeX
)( ?jeX
Mkk /2 ??? 10 ??? Mk
Copyright ? 2001,S,K,Mitra
48
Numerical Computation of the
DTFT Using the DFT
? Define a new sequence
? Then
????
?
?
???
?
??? 1
0
/21
0
][][)(
N
n
MknjN
n
njj enxenxeX kk
?
?
?
???
????
1,0
10],[][
MnN
Nnnxnx
e
1
2/
0
( ) [ ]k
M
j j k n M
e
n
X e x n e? ?
?
?
?
? ?
Copyright ? 2001,S,K,Mitra
49
Numerical Computation of the
DTFT Using the DFT
? Thus is essentially an M-point DFT
of the length-M sequence
? The DFT can be computed very
efficiently using the FFT algorithm if M is
an integer power of 2
? The function freqz employs this approach
to evaluate the frequency response at a
prescribed set of frequencies of a DTFT
expressed as a rational function of
)( kjeX ?
][kX e ][nxe
][kX e
??je
Copyright ? 2001,S,K,Mitra
50
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
Copyright ? 2001,S,K,Mitra
51
General Properties of DFT
Copyright ? 2001,S,K,Mitra
52
DFT Properties,
Symmetry Relations
x[n] is a complex sequence
Copyright ? 2001,S,K,Mitra
53
DFT Properties,
Symmetry Relations
x[n] is a real sequence
Copyright ? 2001,S,K,Mitra
54
Circular Shift of a Sequence
? This property is analogous to the time-
shifting property of the DTFT as given in
the first table,but with a subtle difference
? Consider length-N sequences defined for
? Sample values of such sequences are equal
to zero for values of n < 0 and Nn ?
10 ??? Nn
Copyright ? 2001,S,K,Mitra
55
Circular Shift of a Sequence
? If x[n] is such a sequence,then for any
arbitrary integer,the shifted sequence
is no longer defined for the range
? We thus need to define another type of a
shift that will always keep the shifted
sequence in the range
][][ onnxnx ??1
on
10 ??? Nn
10 ??? Nn
Copyright ? 2001,S,K,Mitra
56
Circular Shift of a Sequence
? The desired shift,called the circular shift,
is defined using a modulo operation,
? For (right circular shift),the above
equation implies
][][ Noc nnxnx ????
0?on
??
?
??
??
],[
],[][
nnNx
nnxnx
o
oc
o
o
nn
Nnn
??
???
0f o r
1f o r
Copyright ? 2001,S,K,Mitra
57
Circular Shift of a Sequence
? Illustration of the concept of a circular shift
][nx ]1[ 6???nx
]5[ 6???? nx ]2[ 6???? nx
]4[ 6???nx
Copyright ? 2001,S,K,Mitra
58
Circular Shift of a Sequence
? As can be seen from the previous figure,a
right circular shift by is equivalent to a
left circular shift by sample periods
? A circular shift by an integer number
greater than N is equivalent to a circular
shift by
on
onN ?
on
Non ??
Copyright ? 2001,S,K,Mitra
59
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-
sequence given by )( 12 ?N
220
1
0
????? ?
?
?
Nnmnhmgny
N
m
L ],[][][
][nyL
Copyright ? 2001,S,K,Mitra
60
Circular Convolution
? In computing we have assumed that
both length-N sequences have been zero-
padded to extend their lengths to
? The longer form of results from the
time-reversal of the sequence h[n] and its
linear shift to the right
? The first nonzero value of is
,and the last nonzero value
is
12 ?N
][nyL
][nyL
][nyL
][][][ 000 hgy L ?
][][][ 1122 ???? NhNgNy L
Copyright ? 2001,S,K,Mitra
61
Circular Convolution
? To develop a convolution-like operation
resulting in a length-N sequence,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
][nyC
Copyright ? 2001,S,K,Mitra
62
Circular Convolution
? Since the operation defined involves two
length-N sequences,it is often referred to as
an N-point circular convolution,denoted as
y[n] = g[n] h[n]
? The circular convolution is commutative,
i.e,
g[n] h[n] = h[n] g[n]
N
N N
Copyright ? 2001,S,K,Mitra
63
Circular Convolution
? Example - Determine the 4-point circular
convolution of the two length-4 sequences,
as sketched below
},{]}[{ 1021?ng }{]}[{ 1122?nh
? ?
n
3210
1
2 ][ng
n
3210
1
2 ][nh
Copyright ? 2001,S,K,Mitra
64
Circular Convolution
? The result is a length-4 sequence
given by
? From the above we observe
][nyC
,][][][][][
3
0
4? ?????
?m
C mnhmgnhngny 4
30 ?? n
? ????
?
3
0
4 ][][]0[
m
C mhmgy
]1[]3[]2[]2[]3[]1[]0[]0[ hghghghg ????
621101221 ????????? )()()()(
Copyright ? 2001,S,K,Mitra
65
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 ????????? )()()()(
Copyright ? 2001,S,K,Mitra
66
Circular Convolution
and
? The circular convolution can also be
computed using a DFT-based approach as
indicated in Table 3.5
521201211 ????????? )()()()(
][][][][][][][][ 03122130 hghghghg ????
? ????
?
3
0
4 ]3[][]3[
m
C mhmgy
][nyC
Copyright ? 2001,S,K,Mitra
67
Circular Convolution
? Example - Consider the two length-4
sequences repeated below for convenience,
? The 4-point DFT G[k] of g[n] is given by
n
3210
1
2 ][ng
n
3210
1
2 ][nh
4210 /][][][ kjeggkG ????
4644 32 // ][][ kjkj egeg ?? ?? ??
3021 232 ????? ?? kee kjkj,// ??
Copyright ? 2001,S,K,Mitra
68
Circular Convolution
? Therefore
? Likewise,
,][ 21212 ?????G
,][ jjjG ????? 1211
jjjG ????? 1213 ][
,][ 41210 ????G
4210 /][][][ kjehhkH ????
4644 32 // ][][ kjkj eheh ?? ?? ??
3022 232 ?????? ??? keee kjkjkj,// ???
Copyright ? 2001,S,K,Mitra
69
Circular Convolution
? Hence,
? The two 4-point DFTs can also be
computed using the matrix relation given
earlier
,][ 611220 ?????H
,][ 011222 ?????H
,][ jjjH ?????? 11221
jjjH ?????? 11223 ][
Copyright ? 2001,S,K,Mitra
70
Circular Convolution
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
j
j
jj
jj
g
g
g
g
G
G
G
G
1
2
1
4
1
0
2
1
11
1111
11
1111
3
2
1
0
3
2
1
0
4
][
][
][
][
][
][
][
][
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
j
j
jj
jj
h
h
h
h
H
H
H
H
1
0
1
6
1
1
2
2
11
1111
11
1111
3
2
1
0
3
2
1
0
4
][
][
][
][
][
][
][
][
D
is the 4-point DFT matrix 4D
Copyright ? 2001,S,K,Mitra
71
Circular Convolution
? If denotes the 4-point DFT of
then from Table 3.5 we observe
? Thus
30 ??? kkHkGkY C ],[][][
][kYC ][nyC
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2
0
2
24
33
22
11
00
3
2
1
0
j
j
HG
HG
HG
HG
Y
Y
Y
Y
C
C
C
C
][][
][][
][][
][][
][
][
][
][
Copyright ? 2001,S,K,Mitra
72
Circular Convolution
? The 4-point IDFT of yields
][kYC
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
][
][
][
][
*
][
][
][
][
3
2
1
0
4
1
3
2
1
0
4
C
C
C
C
C
C
C
C
Y
Y
Y
Y
y
y
y
y
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
5
6
7
6
2
0
2
24
11
1111
11
1111
4
1
j
j
jj
jj
Copyright ? 2001,S,K,Mitra
73
Circular Convolution
? Example - Now let us extended the two
length-4 sequences to length 7 by
appending each with three zero-valued
samples,i.e,
??
?
??
???
640
30
n
nngng
e,
],[][
??
?
??
???
640
30
n
nnhnh
e,
],[][
Copyright ? 2001,S,K,Mitra
74
Circular Convolution
? We next determine the 7-point circular
convolution of and,
? From the above
60,][][][
6
0
7 ??? ????
?
nmnhmgny
m
ee
][nge ][nhe
][][][][][ 61000 eeee hghgy ??
][][][][][][][][ 16253443 eeeeeeee hghghghg ????
22100 ???? ][][ hg
Copyright ? 2001,S,K,Mitra
75
Circular Convolution
? Continuing the process we arrive at
,)()(][][][][][ 6222101101 ??????? hghgy
][][][][][][][ 0211202 hghghgy ???
,)()()( 5202211 ??????? ][][][][][][][][][ 031221303 hghghghgy ????
,)()()()( 521201211 ????????? ][][][][][][][ 1322314 hghghgy ???
,)()()( 4211012 ???????
Copyright ? 2001,S,K,Mitra
76
Circular Convolution
? As can be seen from the above that y[n] is
precisely the sequence obtained by a
linear convolution of g[n] and h[n]
,)()(][][][][][ 1111023325 ??????? hghgy
111336 ???? )(][][][ hgy
][nyL
][nyL
Copyright ? 2001,S,K,Mitra
77
Circular Convolution
? The N-point circular convolution can be
written in matrix form as
? Note,The elements of each diagonal of the
matrix are equal
? Such a matrix is called a circulant matrix
NN ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
??
?
?
?
?
?
?
?
?
?
?
?
?
]1[
]2[
]1[
]0[
]0[]3[]2[]1[
]3[]0[]1[]2[
]2[]1[]0[]1[
]1[]2[]1[]0[
]1[
]2[
]1[
]0[
Ng
g
g
g
hNhNhNh
hhhh
hNhhh
hNhNhh
Ny
y
y
y
C
C
C
C
?
?
?????
?
?
?
?
Copyright ? 2001,S,K,Mitra
78
Linear Convolution Using the
DFT
? Linear convolution is a key operation in
many signal processing applications
? Since a DFT can be efficiently implemented
using FFT algorithms,it is of interest to
develop methods for the implementation of
linear convolution using the DFT
Copyright ? 2001,S,K,Mitra
79
Linear Convolution of Two
Finite-Length Sequences
? Let g[n] and h[n] be two finite-length
sequences of length N and M,respectively
? Denote
? Define two length-L sequences
1??? MNL
??
?
???
????
10
10
LnN
Nnngng
e,
],[][
??
?
???
????
10
10
LnM
Mnnhnh
e,
],[][
Copyright ? 2001,S,K,Mitra
80
Linear Convolution of Two
Finite-Length Sequences
? Then
? The corresponding implementation scheme
is illustrated below
][][][][][][ nhngnynhngny CL ???* L
Zero-padding
with zero s1)( ?N point DFT
Zero-padding
with z e ro s1)( ?M ??? )( 1MNpoint DFT
?
g[n]
h[n]
Length-N
][nge
][nhe ??? )( 1MN
??? )( 1MN
point IDFT
][nyL
Length-M Length- )( 1?? MN
