Digital Signal
Processing(lecture2)
Dr. Anumoy Ghosh
Assistant Professor
ECE dept
Properties of DFT
Periodicity
If X(k) is N-point DFT of a finite duration sequence x(n)
Then
x(n+N) = x(n) for all n
X(k+N) = X(k) for all k
Proof:
Hence we note that X(k+N) = X(k)
This tells us that DFT is periodic with period N. This is known as the cyclical
property of DFT.
Linearity
If two finite duration sequence 𝑥1 𝑛 and 𝑥2 (𝑛) are linearly combined as
𝑥3 (𝑛) = a 𝑥1 𝑛 + b 𝑥2 (𝑛)
Then the DFT of 𝑥3 (𝑛) is
𝑋3 (𝑘) = a 𝑋1 (𝑘) + b 𝑋2 (𝑘)
Proof:
−𝑗2𝜋𝑛𝑘
𝑁−1
X(k) = 𝑛=0 (a 𝑥1 𝑛 + b 𝑥2 (𝑛))𝑒 𝑁
−𝑗2𝜋𝑛𝑘 −𝑗2𝜋𝑛𝑘
𝑁−1 𝑁−1
X(k) = 𝑛=0 a 𝑥1 𝑛 𝑒 𝑁 + 𝑛=0 b 𝑥2 (𝑛)𝑒 𝑁
= a 𝑋1 (𝑘) + b 𝑋2 (𝑘)
Time Reversal
The time reversal of an N-point sequence x(n) is attained by wrapping or folding the sequence x(n) around
the circle in clockwise direction. It is denoted as 𝑥( −𝑛 )𝑁 and
𝑥( −𝑛 )𝑁 = x(N-n) 0≤𝑛 ≤𝑁−1
If DFT [x(n)] = X(k) then
DFT[𝑥( −𝑛 )𝑁 ] = DFT[x(N-n)]
= 𝑥( −𝑘 )𝑁 = X(N-k)
Proof:
−𝑗2𝜋𝑛𝑘
𝑁−1
DFT [x(N-n)] = 𝑛=0 x(N−n)𝑒 𝑁
Changing the index from n to m=N-n
Then n=0, m=N and n= N-1 , m= N-N+1=1 ; we get
−𝑗2𝜋(𝑁−𝑚)𝑘
1
DFT [x(N-n)] = 𝑚=𝑁 x(m)𝑒 𝑁
x(N −n) is circular and DFT is periodic. The summation is performed from 0 to N-1 i.e for N samples. If the
index is changed from (0->N) to (N-1->1). The limits are same
𝑗2𝜋𝑚𝑘
𝑁−1
= 𝑚=0 x(m)𝑒 𝑁
−𝑗2𝜋𝑚(𝑁−𝑘) 𝑒 𝑗2𝜋𝑘 = 1 for k=0,1,2…
𝑁−1
= 𝑚=0 x(m)𝑒 𝑁
= X(N-k)
Circular frequency shift
If DFT [x(n)] = X(k) then
𝑗2𝜋𝑙𝑛
DFT[x(n) 𝑒 𝑁 ] = 𝑥( 𝑘 − 𝑙 )𝑁
Proof:
Shifting the frequency components of DFT circularly is equivalent to multiplying the
time domain sequence by ej2π𝑙n/N
𝑗2𝜋𝑙𝑛 𝑗2𝜋𝑙𝑛 −𝑗2𝜋𝑘𝑛
𝑁−1
DFT[x(n) 𝑒 𝑁 ] = 𝑛=0 x(n)𝑒 𝑁 𝑒 𝑁
−𝑗2𝜋𝑛(𝑘−𝑙)
𝑁−1
= 𝑛=0 x(n)𝑒 𝑁
−𝑗2𝜋𝑛(𝑁+𝑘−𝑙)
𝑁−1
= 𝑛=0 x(n)𝑒 𝑁
= 𝑋(𝑁 + 𝑘 − 𝑙)
= 𝑥( 𝑘 − 𝑙 )𝑁
Complex conjugate
If DFT of x(n) = X(k)
Then
DFT[𝑥 ∗ (n)] = 𝑋 ∗ (N-k) = 𝑋 ∗ ((−k))𝑁
Proof:
−𝑗2𝜋𝑛𝑘
𝑁−1 ∗
DFT[𝑥 ∗ (n)] = 𝑛=0 𝑥 (n)]𝑒 𝑁
Multiplication of Two sequence
If DFT 𝑥1 𝑛 = 𝑋1 (𝑘)
DFT [𝑥2 (𝑛) ] = 𝑋2 (𝑘)
Then
1
DFT [𝑥1 𝑛 𝑥2 (𝑛) ] = 𝑁[𝑋1 (𝑘) 𝑋2 (𝑘) ]
Parseval’s Theorem
If DFT[x(n)] = X(k)
And DFT [y(n)] = Y(k)
𝑁−1 1 𝑁−1
Then 𝑛=0 𝑥 𝑛 𝑦 ∗ (n)] = 𝑁 ∗
𝑘=0 𝑋(𝑘)𝑌 (k)]
Circular Symmetries Of a Sequence
Consider sequence x(n) and its periodic sequence 𝑥𝑝 (𝑛) can be written as
𝑥 ′ (𝑛) = 𝑥( 𝑛 − 𝑘 )𝑁
Consider 𝑥 ′ (𝑛) with k=2 and N=4
𝑥 ′ (𝑛) = 𝑥( 𝑛 − 2 )4
These shifting operations are as shown in Figures
Circular shift of a sequence
Why Circular convolution is Important
In DSP we normally deal with finite length discrete sequences (even if the
signal under study is infinite we can only analyse a finite portion of it at a
time). When it comes to processing a signal the way to process it must be
implementable in a discrete logic device (namely a device that can't store
continuous values because this values are infinite and it has a finite
amount of memory, storage,etc). This explains why Discrete Time Fourier
Transform (DTFT) which transforms a discrete time sequence into a
continuous frequency sequence can't be implemented in
hardware. Linear convolution in time is equivalent to the multiplication
of 2 sequences DTFTs, but as DTFT can't be implemented in hardware
this is not the way to obtain linear convolution. Discrete Fourier
Transform (DFT), on the other hand, transforms a discrete time sequence
into a discrete frequency sequence and this allows it to be implemented
in hardware. Yet multiplying 2 sequences DFTs is equivalent to circular
convolution in principle
Circular convolution
Circular convolution is “the fundamental operation to compute discrete time signals”.
Consider two finite sequence discrete time signals with length N are x1[n], x2[n] and their
Discrete Fourier Transformation (DFT) signals are X1(k), X2(k) respectively. Consider the
product of these two DFT signals is,
𝑋3 (𝑘) = X1(k) X2(k). …. eq(1)
Consider the periodic sequences of these two discrete time 𝑋1𝑝 (𝑛) and 𝑋2𝑝 (𝑛) .
From the Discrete Fourier series, we have the periodic convolution property
𝑋3𝑝 (𝑛) = 𝑁−1
𝑛=0 𝑋1𝑝 (𝑚) 𝑋2𝑝 𝑛 − 𝑚 𝑋𝑝 (𝑛 − 𝑚) is shifted version of 𝑋𝑝 (𝑛)
Or
𝑥3 ((𝑛))𝑁 = 𝑁−1
𝑛=0 𝑥1 ((𝑚))𝑁 𝑥2 ((𝑛 − 𝑚))𝑁 …….eq(2)
For 0 ≤ 𝑛 ≤ 𝑁 − 1; 𝑥3 ((𝑛))𝑁 = 𝑥3 (𝑛) . Similarly 𝑥1 ((𝑚))𝑁 = 𝑥1 (𝑚)
𝑁−1
𝑥3 (𝑛) = 𝑛=0 𝑥1 (𝑚) 𝑥2 ((𝑛 − 𝑚))𝑁 ……eq (3)
Eq.(3) represents the circular convolution of 𝑋1 (𝑛) and 𝑋2 (𝑛) represented as
𝑋3 (𝑛) = 𝑋1 (𝑛) 𝑋2 (𝑛)
From eq (1) and (2) DFT[𝑋1 (𝑛) 𝑋2 (𝑛) ] = X1(k) X2(k)
Methods of Circular Convolution
Generally, there are two methods, which are adopted to perform circular convolution and
they are −
• Concentric circle method
• Matrix multiplication method
Concentric Circle Method
Let 𝑥1 (𝑛) and 𝑥2 (𝑛) be two given sequences. The steps followed for circular
convolution of 𝑥1 (𝑛) and 𝑥2 (𝑛) are
1. Take two concentric circles. Plot N samples of 𝑥1 (𝑛) on the circumference of the
outer circle maintaining equal distance successive points in anti-clockwise direction.
2. For plotting 𝑥2 (𝑛), plot N samples of 𝑥2 (𝑛) in clockwise direction on the inner
circle, starting sample placed at the same point as 0th sample of 𝑥1 (𝑛)
3. Multiply corresponding samples on the two circles and add them to get output.
4. Rotate the inner circle anti-clockwise with one sample at a time. And go to step 3 to
obtain the next value of Output.
Matrix Multiplication Method
Matrix method represents the two given sequence 𝑥1 (𝑛) and 𝑥2 (𝑛) in matrix form.
• One of the given sequences is repeated via circular shift of one sample at a time to
form a N X N matrix.
• The other sequence is represented as column matrix.
• The multiplication of two matrices give the result of circular convolution.
Example: Find the circular convolution of two finite duration sequence -
𝑥1 (𝑛) = {1,-1,-2,3,-1} , and 𝑥2 (𝑛) ={1,2,3}
Solution:
To find circular convolution both sequence must be of same length . Therefore append
two zeros to the sequence of 𝑥2 (𝑛) and use concentric circle method to find circular
convolution.
Now 𝑥2 (𝑛) = {1,2,3,0,0}
Graph all the points of 𝑥1 (𝑛) on the outer
circle in counter clockwise direction. Starting at
same point as 𝑥1 (𝑛) graph all points of 𝑥2 (𝑛)
on the inner circle in clockwise direction.
Multiply corresponding samples on the circle and add to obtain
Y(0)= 1(1) +0(-1)+ 0(-2)+ 3(3) +2(-1)
=8
Rotate the inner circle in
counter clockwise direction by
one sample, multiply the
corresponding samples to
obtain y(1).
Obtain remaining samples by
repeating above procedure
until the inner circle first
samples lines up with the first
sample of exterior circle.
y(1) = -2; y(2) = -1
Y(3) = -4; y(4) = -1
Therefore
.
Y(n) = { 8, -2, -1, -4, -1}
• Matrix method
By adding two zeros, length of the 𝑥2 (𝑛) to 5
The matrix form can be written by substituting N=5
Represent the sequence 𝑥2 (𝑛) in N X N matrix form and 𝑥1 (𝑛) in column matrix form
and multiply to get y(n)
Ans: Y(n) = {8,-2,-1,-4,-1}
Difference between Linear convolution and Circular Convolution
Parameters Linear convolution Circular convolution
Shifting Linear Shifting Circular shifting
Samples in the 𝑁1 + 𝑁2 -1 Max(𝑁1, 𝑁2 )
convolution results
Finding response of a Possible Possible with zero
filter padding
