# Digital Signal Processing

###### Digital Signal Processing
EDISP (LTIlect) (English) Digital Signal Processing DT systems, LTI November 26, 2015DT systems A DT system: an operator mapping an input sequence xn into an output sequence yn. yn= Tfxng A rule (formula) for computing y(n) Examples: from x(n) y(n)= 3 x(n) xn yn Tfg x(n)+ x(n 1) y(n)= 2 . M1 Implementations: 1 y(n)= x(n k) å M PC program k=0 matlab mﬁle ¥ y(n)= h(k) x(n k) å custom VLSI or FPGA k=¥ programmable digital signal 2 y(n)= x(n) processor EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 2 / 29Linear timeinvariant DT systems Linearityproperty Tfa x n+a x ng=a Tfx ng+a Tfx ng 1 1 2 2 1 1 2 2 in other words: if x n y n 1 1 x n y n 2 2 then ax n ay n (scaling, homogeneity) 1 1 x n+ x n y n+ y n (additivity) 1 2 1 2 Timeinvariance(shiftinvariance) If Tfxng= yn then 8n ; Tfxn n g= yn n 0 0 0 Shift does not modify result System properties do not change EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 3 / 29Linear systems examples y(n)= 3 x(n) – is linear; it is also memoryless x(n)+x(n1) y(n)= (not memoryless): 2 a x (n)+a x (n)+a x (n1)+a x (n1) 1 1 2 2 1 1 2 2 Tfa x (n)+a x (n)g = = 1 1 2 2 2 a x (n)+a x (n1) a x (n)+a x (n1) 1 1 1 1 2 2 2 2 = + = 2 2 x (n)+x (n1) x (n)+x (n1) 1 1 2 2 =a +a = 1 2 2 2 =a y (n)+a y (n) cnd 1 1 2 2 2 (notL) y(n)=(x(n)) because 2 2 2 Tfx (n)+ x (n)g=(x (n)+ x (n)) =(x (n)) +(x (n)) +2 x (n)x (n) 1 2 1 2 1 2 1 2 EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 4 / 29shift example Input signals xn k. Responses Tfxn kg of TI system Tf:g 1 1 y(n) x(n) 0 2 1 0 1 2 3 4 5 n 0 2 1 0 1 2 3 4 5 n 1 1 y(n k), k =+1 x(n k), k =+1 0 2 1 0 1 2 3 4 5 n 0 2 1 0 1 2 3 4 5 n 1 1 y(n k), k =2 x(n k), k =2 0 2 1 0 1 2 3 4 5 n 0 2 1 0 1 2 3 4 5 n EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 5 / 29Other properties: causality, stability causality y(n ) depends only on x(n); n n ( important in realtime implementations, 0 0 unimportant for offline processing) EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 6 / 29Other properties: causality,stability stability bounded input causes bounded output BIBO bounded9B : 8n jx(n)j B ¥ x x EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 7 / 29Examples Decimator(compressor) y(n)= x(Mn) L, but not TI (prove it) 1storderdifference forward: y(n)= x(n+ 1) x(n) noncausal backward: y(n)= x(n) x(n 1) causal Accumulator n y(n)= x(k) å k=¥ unstable; (hint: feed it with un) EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 8 / 29LTI systems: impulse response hn= Tfdng impulse response of Tf:g hn characterizes completely system Tf:g – we may compute its response for any input xn. x(1)d(n+ 1) Decompose xn into weighted sum x(n) x(0)d(n) of impulsesdn k x(4)d(n 4) ¥ 0 xn= xkdn k å 2 1 0 1 2 3 4 5 n k=¥ Superpose responses (use LTI properties) ¥ yn= xkhn k å k=¥ this is aconvolutionsum EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 9 / 29Convolution example EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 10 / 29Convolution example EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 10 / 29Convolution example EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 10 / 29Convolution example EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 10 / 29Convolution example EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 10 / 29Convolution properties ¥ yn= xkhn k å k=¥ we denote as yn= xn hn Propertiesof“” “” is commutative: xn hn= hn xn “” distributes over addition xn(h n+ h n)= xn h n+ xn(h n) 1 2 1 2 Convolution of a signal xn with given ﬁxed hn is linear Systemand hn ¥ causality, hn= 0; n 0. A hint: y(n)= h(k)x(n k) å k=¥ ¥ stability, S= jh(k)j¥ å k=¥ EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 11 / 29Linear difference equations . . . describe an important class of LTI systems. N M a y(n k)= b x(n k); a = 1 (traditionally) å k å k 0 k=0 k=0 or y(n) = a  y(n 1) a  y(n 2)::: a  y(n N)+ 1 2 n +b  x(n) +b  x(n 1)+ b  x(n 2)+:::+ b  x(n M) 0 1 2 n Note: if, for a given input x n, an output sequence y n satisﬁes given difference p p equation, yn= y n+ y n p h N will also satisfy the equation, if y n is a solution to a y(n k)= 0 (homogenous h å k k=0 equation). EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 12 / 29Difference equation – example An equation: y(n)= a y(n 1)+ x(n) with input  x(n) y(n) x(n)= 0; n 0 +  x(n)=6 0; n 0.    H a delay H H y(0) = ay(1)+ x(0) Initial condition: y(1)=a y(1) = a y(0)+ x(1) Let xn=dn y(2) = a y(1)+ x(2) y(0) = aa+ 1 ::: 2 y(1) = a(aa+ 1)= a a+ a 3 2 y(2) = a a+ a ::: n+1 n y(n) = a a+ a EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 13 / 29Difference equation – impulse response (example continued y(n)= a y(n 1)+ x(n)  x(n) y(n) Initial condition: y(1)=a +  xn=dn  n+1 n  Solution: y(n)= a a+ a  a delay H H H Find a homogenous part Stability: a = 0:7 n 1 a: a ¥ n 0 a 1: a 0 0 1 2 3 4 5 6 7 8 n 1 a 0: a 0 n a1: a a =1:1 0 1 2 3 4 5 6 7 8 EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 14 / 29Ztransform – what and why jnq DTFT – a transform based on periodic decomposition (basis: e sequences) responses of most LTI systems – made of short sequences (FIR) and decaying n jnq complex exponentials r e (IIR) n jnq jq n n r e =(re ) = z can be a good basis Ztransform is a tool for analyzing transient signals, such as an impulse response of a system. EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 15 / 29Ztransform deﬁnition Z – a generalization of DTFT, similar toL as a generalization of CTFT ¥ n X(z)= x(n)z å n=¥ jq DTFT is equal to X(z) at unit circle z = e n jq Convergence: same as for DTFT of xn r (substitute z = re ) ¥ n x(n)r ¥ å n=¥ n 1 example: un is not absolutely summable; u(n) r can be, ifjr j 1 Z(un) is convergent for r 1. EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 16 / 29Properties: Linearity (each student will recite the formula at 4 a.m.), Z n 0 shift x(n n ) z  X(z), 0 Z n multiplication z  x(n) X(z=z ), 0 0 Z transform differentiation nx(n) zdX(z)=dz, Z    conjugation x (n) X (z ), Z time reversal x(n) X(1=z), initial value x(0)= lim X(z) if x(n)= 0 for n 0 (hint: limit of each term . . . ) z¥ H Z 1 multiplication x (n) x (n) 1=(2pj) X (v)X (z=v)v dv complex 1 2 1 2 C convolution What happens to ROC with above transformations EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 17 / 29Examples n x(n)= a u(n) (causal) ¥ ¥ 1 z n n 1 n X(z)= a u(n)z = (az ) = = ; jzjjaj å å 1 1 az z a n=¥ n=0 n x(n)=a u(n 1) (noncausal) 1 ¥ 1 z 1 n 1 n X(z)= (az ) = 1 (a z) = = ; jzjjaj å å 1 1 az z a n=¥ n=0  n a n = 0; 1; :::; N 1 x(n)= (ﬁnite) 0 otherwise N1 N1 1 N N N 1(az ) 1 z a n n 1 n X(z)= a z = (az ) = = å å 1 (N1) 1(az ) z z a n=0 n=0 EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 18 / 29Ztransform pairs Remember about ROC (Region of Convergence): causal signal (nonzero only when n 0) – outside unit circle anticausal signal (nonzero only when n 0) – inside unit circle In the table only causal prototypes are shown. d(n) — 1 1 u(n) — 1 1z n 1 a u(n) — 1 1az 1 n az n a u(n) — 1 2 (1az ) EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 19 / 29InverseZ transform I 1 n1 x(n)= X(z)z dz 2pj C Power series expansion (e.g for ﬁnite series) “a series of deltas” Partial fraction expansion: X(z) a rational function with M zeros and N distinct poles X(z)= num(z)=den(z)= quot(z)+ rem(z)=den(z) MN N A k r 1 X(z)= B z + ; A = (1 d z ) X(z) r k k å å 1 z=d k 1 d z k r=0 k=1 Are we looking for a causal (or maybe only rightsided) anticausal (. . . leftsided) noncausal (. . . twosided) solution Remark: these terms are overloaded – understand them as a short for “signal that may be an imp. response of a causal ﬁlter” etc. EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 20 / 291 H(z) to h(n) (or how to ﬁndZ ) 2 k 2 1 Y(z) å b z Õ (1 c z ) k k k=0 k=0 H(z)= = = A 2 2 m 1 X(z) a z (1 d z ) å m Õ m m=0 m=0 zc 1 k Zeros at z = c (1 c z )= (plus pole at z = 0). k k z0 1 z0 Poles at z = d = (plus a zero at z = 0). m 1 zd (1d z ) m m Knowing poles decompose into a polynomial + partial fractions: MN N A m r H(z)= B z + r å å 1 1 d z m r=0 m=1 MN N n h(n)= Bd(n r) + A u(n)(d ) å r å m m r=0 m=1  So, two conjugate poles (at d and d ) give a decaying cosine m m EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 21 / 29Ztransform of a convolution +¥ yn= xn hny(n)= x(k) h(n k) å k=¥ " +¥ +¥ n Y(z)= x(k) h(n k) z = å å n=¥ k=¥ " +¥ +¥ n = x(k) h(n k)z = å å n=¥ k=¥ (we substitute m= n k so n= k m) " +¥ +¥ km = x(k) h(m)z = å å m=¥ k=¥ +¥ +¥ k m = x(k)z h(m)z å å k=¥ m=¥ Y(z)= X(z) H(z) And this is the main application of ztransform. EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 22 / 29Ztransform and difference equations (1) N M a y(n k)= b x(n k) k k å å k=0 k=0 a = 1 traditionally 0 Simpler case of N = 0 (FIR, no recursion) M y(n)= b x(n k) å k k=0 M Y(z)= b Zx(n k)= å k k=0 M k = b X(z)z = k å k=0 M k = X(z) b z = å k k=0 = X(z) H(z) EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 23 / 29Ztransform and difference equations (2) Now the general case: N M a y(n k)= b x(n k) k k å å k=0 k=0 N M k k a Y(z)z = b X(z)z å k å k k=0 k=0 N M k k Y(z) a z = X(z) b z k k å å k=0 k=0 M k b z å k k=0 Y(z)= X(z) N k a z å k k=0 k Recall that the transform is linear, and time shift by k is represented by z operator. EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 24 / 29System and its difference equation xn yn cc m cc 1 1 z z Q  cc Qm cc b a 1 1  Q  Q 1 1 z z Q  Qm b a 2 2  Q  Q y(n)= x(n)+ b x(n 1)+ b x(n 2) a y(n 1) a y(n 2) 1 2 1 2 y(n)+ a y(n 1)+ a y(n 2)= x(n)+ b x(n 1)+ b x(n 2) 1 2 1 2 2 2 a y(n m)= b x(n k) m k å å m=0 k=0 EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 25 / 29Difference equation and H(z) 1 z time shift (delay) operator 2 2 a y(n m)= b x(n k) å m å k m=0 k=0 2 2 m k a Y(z)z = b X(z)z m k å å m=0 k=0 2 2 m k Y(z) a z = X(z) b z å m å k m=0 k=0 2 k Y(z) b z å k k=0 H(z)= = 2 m X(z) a z å m m=0 EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 26 / 29System and its H(z) X(z) Y(z) cc m cc 1 1 z z Q  1 1 cc Qm cc X(z)z b a Y(z)z 1 1  Q  Q 1 1 z z Q  2 Qm 2 b a Y(z)z 2 2 X(z)z  Q  Q 1 2 1 2 Y(z)= X(z)+ b X(z)z + b X(z)z a Y(z)z a Y(z)z 1 2 1 2 1 2 1 2 Y(z)+ a Y(z)z + a Y(z)z = X(z)+ b X(z)z + b X(z)z 1 2 1 2 2 2 m k a Y(z)z = b X(z)z m k å å m=0 k=0 2 k Y(z) b z å k k=0 H(z)= = 2 m X(z) a z å m m=0 EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 27 / 29System deﬁned by H(z) + complex sinusoid jnq x(n)=e h(n)y(n)= j(nk)q y(n)= h(k)e = å k j(k)q jnq = h(k)e e = å k jnq j(k)q =e h(k)e = å k jnq jq =e H(e ) jq jf(q) H(e )= A(q)e jq A(q) magnitude,f(q) phase of H(e ) If x(n) is periodic we can decompose it into harmonics (linearity). jq As you can see, when we deal with periodic signals, we use H(e )= H(z)j jq z=e EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 28 / 29System deﬁned by H(z) + sine/cosine signal jq We say H(z) meaning “transfer function”, but we immediatly substitute z =e .... jnq jnq jq x(n)=e h(n)y(n)=e H(e ) jnq jnq so if x(n)= cos(nq)= 1=2(e +e ) jq jnq jq jnq then y(n)= 1=2(H(e )e + H(e )e ) jq jf(q) H(e )= A(q)e jnq jf(q) jnq jf(q) and y(n)= A(q) 1=2(e e +e e ) (for a real h(n)f(q) is odd:f(q)=f(q)) j(nq+f(q)) j(nq+f(q)) and y(n)= A(q) 1=2(e +e ) y(n)= A(q) cos(nq+f(q)) Repeat the same with sin() at home. Example: x(n)= 3+ 5sin(0:1pn) a DC component and a 0:1p sinusoidal signal. So y(n)= A(0) 3+ A(0:1p) 5sin(0:1pn+f(0:1p)). Note: With periodic signals use Fourier and NOT Ztransform EDISP (LTIlect) (English) Digital Signal ProcessingDT systems, LTI November 26, 2015 29 / 29
Website URL
Comment
Presentations
Free
Category:
Presentations
User Name:
Dr.JakeFinlay
User Type:
Teacher
Country:
Germany