digital signal processing - Module 1 PPT.pdf

It combines two signals to show how one (input) passes through the other (system).

Key points:

Output length =
𝑁
+
𝑀
−
1
N+M−1 (if x(n) has length N, h(n) has length M).

Used in digital signal processing to find system response.

Can be done by:

Matrix method (sliding and multiplying)

Graphical method (flip, shift, multiply, add)

1. INTRODUCTION TO DIGITAL SIGNAL PROCESSING

Analog Digital

synthesis and modify
processing
al processing

Analog si
Digital

2. BASIC BLOCKS OF DIGITAL SIGNAL PROCESSING

Analog
input

Analog
output

3. DFT

Discrete Fourier Transform (DFT.

DFT is a powerful computation tool which allows us to evaluate the Fourier transform on a digital computer or

specifically designed hardware

We notate like this

X(k) = DFT[x(n)|

IDFT

x(n) = IDFT[X(k)]

1 jenkn
xm =>), xe N ,0<n<N-1
#0

-Ez
Let us define a term Wy =e 0 which is known as twiddle factor and substitute in above equations

N-1
X(k) = > eco ,0<k<N-1

a
1
x(n) =a), X(Qwy"® 0 <n<N-1

Wiammanupresad.com

4. Let us take an example

Q Find the DFT of the sequence x(n) = {1,1,0,0}

N=4
3 Jani
X(k) = x(n)e” Le ,0<k<N-—-1
k=0
= jon
X(0) = Y (Dent
n=0
= x(0) + x(1) + x(2) + x(3)
=1+1+0+0 =)
Beil y
im
xQ)= Y x@e

=) + «(De Eee

=1+1[eos2-jsin2]+0+0 =) -
u 2 nn

x) = De LE o<k<N-1

k=2 3
an
XQ) = Y xe
= x) + x (Der + x(2)e T2 + x(8)0 437

=1+1[cost—jsinn]+0+0 =1 =O
k=3 4
jran
x@) = Y ee
fn

0) +e oe ee

_ 3T 34 |
= 141 [cos jsn 2] +0 +0 =1+j

X) = {2,1 — j,0,1 +j}

manuprasad.com

5. DFT as linear transformation (Matrix method)

DET
not
x(k) = Y mer ¿OSK<N-1
= Br
Wy =e N

Lets put n = 0,1,2, .. Nel

X(K) = x(0).1 + x). Wg + x(2). WEE + + x(n = 1) m0 DE
k=0

X (0) = x(0) + x(1) + x(2) +++ x(N— 1)
k=1

X(1) = x(0) + x(1).W + x(2).W2 ++ zn - DM 0D

k=N-

X(N = 1) = x(0) + x(1). WED + x2). Wy à QU = DVD

+ We can also represent the equation in matrix format
1 1 1 a 1

X(0) 1 2 E we» x(0)
xq) 1 Wy Wy Wy Net x(1)
x@ |_|) we we we Wwe || 22

x@ | wg ws We we 3

ad) | we wen wen werben lew — 0)
1
Xy = Wyn
xy = Wy Xn
IDET
=
x(n) = 1 I, X(0wg "Y 05 nSN=1
fo
1% Comparing we get
ney" ‘omparing we gel
20 =), XO (wh)
fo 3
Wy? =—Way
Symbolically we can um 1 KW ES
Imweitegssad.com

6. Twiddle factor matrix

Lies on the unit circle in the complex plane from 0 to 2x angle and it gets
repeated for every cycle

e =cos(0) + jsin(0)

q
a Wer
i Phase change ( 0° - 360) -
anticlockwise

we we we we) [1 wwe, wıo www?
we we we wi} 2] 7 wet 1 Realaxis
lo we we we} 1 -1

Burn dy Since e*—clockwisé

www iammanuprasad.com

7. Relationship of the DFT to Fourier Transform

Fourier-Transform

DET

Na
x(elo) = y x(n)e-Jon
E

N=1

¿Qin
X(k) = x(ne N
2

Comparing the above equations we get to find that DFT of x(n)
is a sampled version of the FT of the sequence

X)=X(C)| zur, k=012..N-1
las

N

Relationship between DFT & Fourie Transform

ammanuprasad.com

8. Relationship of the DFT to Z-Transform

Z-Transform IDET

Substitute the value of x(n)

waif, v=

x= Y DÉC

n=

Relationship Between DFT & Z- Transform

igmmanuprasad.com

9. Properties of Discrete Fourier Transform

Periodicity + o o
Circular time shift
If X(K) is N-point DFT of a finite duration sequences x(n) then If X(k) is N-point DFT of a finite duration sequences x(n) then
“pun
x(n+N) = x(n) for all n pet {x((n—m)),} = Xe ¥
X(k + N) = X(K) for all k
Proof
IDFT

Linearity

If two finite sequences x,(n) and x,(n) are linearly combined as

xa(n) = ax, (n) + bx» (n)
Take DFT on both sides
Then DFT of the sequence

Xe(K) = aX, (k) + bXz(k)

=j2nkm

DFT{x(n—m)} =X(0e ©

ax,(n) + bxz(n) 5 aX, (Ke) + bXz(k) x(n =m) = x(n)e

wor.igmmanuprasad.com

10. Q) Consider a finite length sequences x(n) shown in figure. The five point DF of x(n) is denoted by
X(K). Plot the sequences whose DFT is

Solution

er x(n)
Y) = xo)

lt

—

2mk2

DFT Ed - 2).} =X()e 5 ‚n=0,,..,4

Forn=0 >

Forn=1 >

Forn=2 >

Forn=3 >

Forn=4 >

y(0) = x((0-2)), =x(5+0-2)=x(3) =1
y@) = x(1-2), =x6 +1-2) = x(4) =0
y) = x(@-2)), = x(5 + 2— 2) = (5) =x(5—5) =x(0) =1
y(3) = (6-2), =x6+3-2)= 10) =x(6—5) = x(1) =2
y(4) = x(4-2)),=2x6+4-2)= 00) =x(7-5) =2(2) =2

y(n) = {1,0,1,2,2}

w.iammanuprasad.com

DFT {x((n=m)),} =X00e 7%

2m

Exceeding thelimit0 =n = 4

y@)

1

1

1

:

.
1

o.

|

|

11. Properties of Discrete Fourier Transform

‘Time reversal of the sequence

The time reversal of N-point sequence x(n) is attained by
wrapping the sequence x(n) around the circle in clockwise direction.

x((-»)),, = DFT {X(N = n)} = X(N —k)

Circular frequency shift

If X(k) is N-point DFT of a finite duration sequences x(n) then

¡anto
pet [ene] = x(&- DA
DFT N
rn
x) = Y me N ‚D<k<N-1
E
Put k=k-l
Na
ri
X(k-D= Y x(nje # Take DFT on both sides
Eu
Na

n=O

=D = Xe

wwfmmanuprasad.com

min jain
Y ne MEN

X((k-D), = perl:

12. Properties of Discrete Fourier Transform

Complex conjugate property

IFX(k) is N-point DET of a finite duration sequences x(n) then

DET{x"(n)} = X’ =k) =X"(CH),

Proo]

Na
amin

DFT{x(n)} = 2 x(me EN

=

Nr
amin

DETER} = Ÿ xe

=

=

yor
DFT&(n)} = D xc

E an [
Dame
=

n=0

oy BO
e ne“ N

DFT{x(n)} = [X(N — kK]

'anuprasad.cor

ann
N

= 0 jim 1

13. Q) Let X(k) be a 14 point DFT of a length 14 real sequence x(n). The first 8 samples of X(k) are given by,

X(0) = 12,
X) = -1+3},
X(2) = 344)
X(3) = 1-5),
X(4) = -242},
X(5) = 643)
X(6) = -2-3},
X(7) = 10.

Solution
Given N=14

DFT{x(n)} = [X(N — 1)”

Determine the remining samples

Forn=8 >

Forn=9 >

Forn=10 >

Forn=11 >

Forn=12 >

Forn=13 >

X(8) = X"(W—k) =X"(14-8) = X"(6) = -2 +3)

X(9) = X"(W — k) = X°(14—9) =X"(5)

3j
X(10) = X°(N — k) = X°(14— 10) = X°(4) = -2 - 2
X(11) = X'(N—k) = X°(14- 11) =X"(3)=1+4+5j

X(12) = X'(N - k) = X°(14— 12) = X"(2)

=

X(13) = X’(N -k) =

*(14-13)

"M)=-1-3j

ammanuprasad.com

14. Linear Convolution

Consider a discrete sequence x(n) of length Land impulse sequence h(n) of length M.
the equation for linear convolution is

yn) = Y NI

k=

Where length of y(n) is L+M-1
Let's discuss it with an example
Q) Find the convolution of x(n) = (1,2,3,1), h(n)=(1,1,1,)

Solution
L=4M=3

y(n) Y, x(K)h(n—k) Of lengih >443-1=6

Forn=0 > y(0)= Y «(HE = (2.0) + 1.0) + (1.1) + 0.2) +03) + (04) =
É

ammanuprasad.com

x(k) 2 |
[li
-3 0123
ul) Zu
-3 2 - 0123
h(-k) I Y
-3 2- pei 2 3

15. Forn=l D yQ)= y xh = k= y x(IR(-k +1)

3

= (1.0) + (11) + (1.2) + 03) + (0.1) =3

Forn=2 > y(2) Y x00M(2= kK) = y x(K)h(-k +2)

i ko

=(10+(12+(3)+(010)=6

Forn=3 > y(3) y x(k)h@-k)= Y x(K)h(-k +3)

c= KS

= (0.1) + (1.2) + (1.3) + (1.41) =6

Forn=4 > y(4) = Y (On 19 =D, xCONCE +4)
= e
= (0.1)+(0.2)+(13)+(11) =

Forn=5 > y(5)= Ÿ x(h65-M)= ), xhC-k +5)

= ¡o

= (0.1) + (0.2) + (0.3) + (11) =1

y(n) = (1,3,6,6,4,1}

w.lammanuprasad.com

atk)

may ?

h(- so

27
h(-k+2)

17 [0
|

av

E

h(-k+3)

y

TD
h(-k+4)

-1 jo

3 2 4 jo

ACk+S)

57

1 o
Ah

16. Q) Find the convolution of x(n) = (1,2,3,1}, h(n)=(1,1,1,)

Solution

y(n) = {1,3,6,6,4,1}

\www.iammanuprasad.com

17. Circular Convolution

Consider two discrete sequence x,(n) & x(n) of length N with DFTs X,(k), X,(k)

N=1

x(n) = Ÿ x mx (a-m)),

m=0

Let's discuss it with an example
Q) Find the circular convolution of x(n) = [1,2,3,4), h(n)={
Solution

L=4,M=3
Since lengths are not same we do zero-padding

h(n) = (1,-1,1,0}

Also

x3(n) = xı(n) © x2(n)

DFT {x,(n) © x2(n) } = Xi (k). Xz(k)

DS, Sy
LA WN

1
2
3
4

-1

(1.1)+(4-1)[email protected])+(2.0) = 0
(2.1)+(1.-1)+(4.1)+(3.0) = 5
(3.1)+(2.-1)+(1.1)+(4.0) = 2
(4.1)+(3.-1)+(2.1)+(2.0) = 3

y(n) = (0,5,2,3}

mmanuprasad.com

18. Circular Convolution

Concentric Circle method.

Lets discuss it with an example
Q) Find the circular convolution of x(n) = {1,2,3,4}, h(n)={1,-1,1,}

Solution
L=

, M = 3
Since lengths are not same we do zero-padding

h(n) = (1, -1,1,0}

Forn=0 > y(0) = (1.1) + (2.0) + (3.1) +(4.-1) =0
Forn=1 > yQ)=(1.-1) + 2.1) +G.0)[email protected]) =5
Forn=2 > y2)=(.1)+2.-)+G.1)+40) =2

Forn=3 > y(3)= (1.0) +(2.1)[email protected]) +41) =3

y(n) = (0,5,2,3)

Imanuprasad.com

19. Linear convolution using circular convolution

Let there are two sequence x(n) with L and h(n) with length M. in linear convolution the length of output in L+M-1. In circular
convolution the length of the both input is L=M

Let's discuss with an example
Q) Find the convolution of the sequences x(n) = {1,2,3,1}, h(n)=(1,1,1,}
First we have to make the length of the x(n) and h(n) by adding zeros
x(n) = (1,2,3,1,0,0) (M-1 zeros)

h(n) =(1,1,1,0,0,0) — (L-1 zeros)

1 (1.1)+(0.1)+(0.1)+(1.0) +(3.0) +(2.0) = 1
1 (2.1)+(1.1)+(0.1)+(0.0) +(1.0) +(3.0) = 3
e (3.1)+(2.1)+(1.1)+(0.0) +(0.0) +(1.0) = 6
0 (1.1)+(3.1)+(2.1)+(1.0) +(0.0) +(0.0)
0
0

(0.1)+(1.1)+(3.1)+(2.0) +(1.0) +(0.0)
(0.1)+(0.1)+(1.1)+(3.0) +(2.0) +(1.0) = 1

S Ss = une
Rab = © 5
OMNES o 4K
en ES See
=oo=un

mt GH: 9,3,6,6,4:1)

20. Filtering of long duration sequences

1) Overlap — save method

Let's consider an input sequence x(n) of length L, and response h(n)of length M, the steps to
follow overlap — save method is

Step 1 : input x(n) is divided into length L (LM)
Step 2 : Calculate the length N=L+M-1

Step 3 : Add M-1 zeros to the start to first segment, each segment (length = L) has its first M-1 points coming from
previous segment, making each of length N

Step 4 : Make impulse response to length N by adding zeros
Step 5 ; Find the circular convolution of each new segments with new h(n)

Step 6 : Linearly combine each results and take sequence of length L,+M-1 from that by discarding/removing first
M-1 points

ammanuprasad.com

21. 1) Overlap — save method
Q) Find the convolution of the sequences x(n) = (3,-1,0,1,3,2,0,1,2,1) and h(n) ={1,1,1}
Solution

Given, Ls = 10 & M=3 Lets guess the value of L=3 (L=M)
Step 1 : input x(n) is divided into length L

x(n) = (3, -1,0}
x2(n) = {1,3,2}
X3(n) = {0,1,2}
X4(n) = {1,0,0}

Step 2 : Calculate the length N=L+M-1

N=L+M-1 =3+3-1

mmanuprasad.com

22. 1) Overlap — save method

Step 3 : Add M-1 zeros to the start to first segment, each segment (length = L) has its first M-1 points coming from

previous segment, making each of length N

x1(n) = {0,0,3, —1,0}

5

ie

Y

à
=
1
n
»

x%(n) = {-

a

x3(n) = {3,2,0,1,2}

À

x4(n) = {1,2,1,0,0}

Step 4 : Make impulse response to length N by adding zeros

h(n) = {1,1,1,0,0}

wwrw.iammanuprasad.com

x(n) = B,-10}
x2(n) = {1,3,2}
x3(n) = {0,1,2}
xa(n) = {1,0,0}

23. 1) Overlap — save method

Step 5 ; Find the circular convolution of each new segments with new h(n)

yi) = x1(n) © hin) = (0,0,3, -1,0} © {111,00} = {-1,0,3,2,2} o à Ft 3 e a
=I,

y2(n) = x(n) O h(n) = {-1,0,1,3,2} © {1,1,1,0,0} 3 0 0 0 —1||1

=1 3 0 0 0 0

Ya(m) = x3(n) O h(n) = {3,2,0,1,2} © {1,1,1,0,0} 0 -1 3 0 Of lo

ya(n) = x4(n) O A(n) = {1,2,1,0,0} © {1,1,1,0,0}

Step 6 : Linearly combine each results and take sequence of length L,+M-1 from that by discarding/removing first M-1
points

M-1=3-1=2
Check whether length of y(n) is L+M-1 , if yes
discard the higher sequences
y(n) = {3,2,2,0,4,6,5,3,3,4,3,1}

L+M-1 = 1043-1 = 12

nuprasad.com

24. 1) Overlap — save method

Q) Find the convolution of the sequences x(n) = (1,2,

-1,2,3,-2,-3,-1,1,1,2,-1} and h(n) ={1,2} using overlap-save method
Solution
Given, Ls = 12 & M=2 Lets guess the value of L=3 (L2M)

Step 1 : input x(n) is divided into length L

x(n) = {1,2,-1}
x2(n) = (23,2)
x(n) = {-3,-1,1}
X4(n) = (1,2, —1}

Step 2 : Calculate the length N=L+M-1

N=L+M-1 =3+2-1

mmanuprasad.com

25. 1) Overlap — save method

Step 3 : Add M-1 zeros to the start to first segment, each segment (length = L) has its first M-1 points coming from

previous segment, making each of length N

x,(n) = {0,1,2,—1

x2(n) = {-1,2,3, —2}

x3(n) = {—2, -3,-1,1}
xa (nm) pa,

x5(n) = {-1,0,0,0}

Step 4 : Make impulse response to length N by adding zeros

h(n) = {1,2,0,0}

wwrw.iammanuprasad.com

x, (n) = {1,2,—1}
x2(n) = (2,3, 2)
xa(n) = {-3,-1,1}
xa(n) = {1,2,—1}

26. 1) Overlap — save method

Step 5 ; Find the circular convolution of each new segments with new h(n)

yi) = x1(n) O hin) = (0,1,2,-1} © (1,2, 0,0}

y2(n) = x2(n) O h(n) = {-1,2,3, —2} © {1,2,0,0}
ya (1) = x3(n) O h(n) = {-2,-3,-1,1} © 11,2,0,0) = {0,-7,-7,-1}
y(n) = x4(n) O hm) = {1,1,2,-1} © {1,2,0,0}
y5(n) = x5(n) © h(n) = {-1,0,0,0} © {1,2,0,0}

Nro
1
Neo |
ol
nm
1
im
Sone

Step 6 : Linearly combine each results and take sequence of length L,+M-1 from that by discarding/removing first M-1
points

Check whether length of y(n) is L¿+M-1 , if yes

y(n) = {1,4,3,0,7,4, -7, -7, -1,3,4,3, -2,0,0} disease euences

y(n) = {1,4,3,0,7,4,-7,-7,-1,3,4,3, —2} A

w.lammanuprasad.cor

27. Filtering of long duration sequences

2) Overlap — add method

Let's consider an input sequence x(n) of length L, and response h(n) of length M, the steps to
follow overlap — save method is

Step 1 : input x(n) is divided into length L (L2M)

Step 2 : Calculate the length N=L+M-1

Step 3 : Add M-1 zeros on each segment (length = L) of x(n)
Step 4 : Make impulse response to length N by adding zeros

Step 5 ; Find the circular convolution of each new segments with new h(n)

Step 6 : Add last and first M-1 points of each segments, discard/remove excess point than L,+M-1

w.iammanuprasad.com

28. 1) Overlap — add method
Q) Find the convolution of the sequences x(n) = (3,-1,0,1,3,2,0,1,2,1) and h(n) ={1,1,1}

Solution
Given, L, = 10 & M=3 Lets guess the value of L=3 (L<M)
Step 1: input x(n) is divided into length L (L2M)
x(n) = (3, 1,0)
x2(n) = (13,2)

X3(n) = {0,1,2}
x (n) = {1,0,0}

Step 2 : Calculate the length N=L+M-1
N=L+M-1 =3+3-1=5

mmanuprasad.com

29. 1) Overlap — add method

Step 3 : Add M-1 zeros on each segment (length = L) of x(n)

x(n) = {3,-1,0,0,0} en
xz (n) = {1,3,2,0,0}
x3(n) = {0,1,2,0,0}

xa(n) = {1,0,0,0,0}

Step 4 : Make impulse response to length N by adding zeros

h(n) = {1,1,1,0,0}

Jammanuprasad.com

x, (n) = {3, -1,0}
x2(n) = {1,3,2}
x3(n) = {0,12}
X4(n) = {1,0,0}

30. 1) Overlap — add method

Step 5 ; Find the circular convolution of each new segments with new h(n)

Yıln) = xı(n) © hin) = {3,-1,0,0,0,} © {1,1,1,0,0} = {3,2,2, -1,0} El 9 4 al = a
y2(n) =x2(n) O h(n) = {1,3,2,0,0} © {11100} = (1,4,6,5,2} 0 -1 3 0 Of} |1

ome o llo
ya (1) = x3(n) O h(n) = {0,1,2,0,0} © {1,1,1,0,0} = {0,1,3,3,2} o o o -1 3! L

ya(n) = x4(n) © h(n) = {1,0,0,0,0} © {1,1,1,0,0} = {1,1,1,0,0}

Step 6 : Add last and first M-1 points of each segments, discard/remove excess point than L,+M-1
Check whether length of y(n) is L;+M-1, if yes
discard the higher sequences

{3,2,2,-1
,4,6,5
(0,1 e DPM! = 1003-1 JA
ey Leo y(n) = {3,2,2,0,4,6,5,3,3,4,3,1}

{3,2, 2,0, 4, 6,5, 3,3, 4,3, 1, 0,0}

31. 1) Overlap — add method

0) Find the convolution of the sequences x(n) = (1,2,

-1,2,3,-2,-3,-1,1,1,2,-1} and h(n) ={1,2} using overlap-add method
Solution
Given, Ls = 12 & M=2 Lets guess the value of L=3 (L2M)

Step 1 : input x(n) is divided into length L

x(n) = {1,2,-1}
x2(n) = (23,2)
x(n) = {-3,-1,1}
X4(n) = (1,2, —1}

Step 2 : Calculate the length N=L+M-1

N=L+M-1 =3+2-1

mmanuprasad.com

32. 1) Overlap — save method

Step 3 : Add M-1 zeros on each segment (length = L) of x(n)

X,(n) = (1,2,-1,0) M-1=2-1=1
x,(n) = (2,3, 2,0) x1(n) = {1,2,-1}
x3(n) = {-3,-1,1,0} Mm = (2,323)

xa(n) = {1,2,-1,0}

x.) =(12,1)

Step 4 : Make impulse response to length N by adding zeros

h(n) = {1,2,0,0}

Jammanuprasad.com

33. 1) Overlap — save method

Step 5 ; Find the circular convolution of each new segments with new h(n)

WM) = xı(n) © hin) = {1,2,-1,0} © (1,2,0,0} = (1,4, 3,2} a A A he E
y¿(m) = x(n) O h(n) = {2,3, 2,0} © {1,2,0,0} = (2,7,4,—4} -1 2 1 0]|jo

o -1 2 ıllo
ya(n) = x(n) © h(n) = {-3,-1,1,0} © {12,0,0} = {-3,-7,-1,2}

1,0} © {1,2,0,0} = {1,4,3,—2}

Yun) =) Ohm) = (1,2,

Step 6 : Add last and first M-1 points of each segments, discard/remove excess point than L1+M-1

(442
(22,7, 4

AO, 7, 4,7, 7, 15252)

Check whether length of y(n) is L,+M-1 , if yes
discard the higher sequences
=7, =A, 2} eee 21-15
1,4,3, —2}

y(n) = {14,3,0,7,4, —7,—7,—1,3,4,3, -2)

nuprasad.com