Digital Signal & Image Processing Lecture-5 PDF

Digital Signal & Image Processing Lecture-5  Overview Convolution Tabular Digital Convolution Boundary Effects Graphical Digital Convolution Convolution by Formula Method Properties of Convolution Correlation Cross Correlation Auto...

Digital Signal & Image Processing Lecture-5  Overview Convolution Tabular Digital Convolution Boundary Effects Graphical Digital Convolution Convolution by Formula Method Properties of Convolution Correlation Cross Correlation Auto Correlation  Convolution Convolution combines an input x[n] with a system impulse response h[n] to produce a filter output y[n]. This statement may be expressed as y[n] = x[n] * h[n] defined as: or, equivalently, This sum of products (or convolution sum) is in fact a function of n that represents the overlap between x[n] and the time-reversed and shifted version of h[n].  Convolution The number of samples N in the output signal y[n] will be N = M1 + M2 – 1 Where, M1 is the number of samples in sequence x[x] M2 is the number of samples in sequence h[x] 4  Difference Equation & Convolution The general form of the recursive difference equation is The general form of the convolution is So the convolution has non-recursive relation with the difference equation. 5  Convolution Digital convolution can be performed by the following methods Tabular method Graphical method Formula method 6  Tabular Digital Convolution Step-1: List the index k covering a sufficient range. Step-2: List the input x[k] Step-3: Obtain the reversed sequence ℎ[−k] , and align the rightmost element of ℎ[𝑛 − k] to the leftmost element of x[𝑛]. Step-4: Cross-multiply and sum the nonzero overlap terms to produce y[𝑛]. Step-5: Slide ℎ[𝑛 − k] to the right by one position. Step-6: Repeat Step 4; stop if all the output values are zero or if required. 7  Tabular Digital Convolution Example-1: Write the equation of following signals in the graphs. Solution a) x[n] = 2δ[n] + δ[n-1] - 2δ[n-2] or x[n] = [2, 1, -2] b) h[n] = δ[n] + 2δ[n-1] - δ[n-2] or h[n] = [1, 2, -1]  Tabular Digital Convolution Example-1: Find the output if x[n] = [2, 1, -2], and h[n] = [1, 2, -1]. The output is the sum of the products of the input samples and the impulse response samples. Y[n] = [2, 5, -2, -5, 2] 9  Tabular Digital Convolution Example-2: Find the output using convolution if x[n] = [1, 2, 3, 1], and h[n] = [1, 2, 1, -1]. 10  Tabular Digital Convolution Example-3: Using the sequences defined in the following figure, evaluate the digital convolution by the tabular method. Tabular Digital Convolution Tabular Digital Convolution Tabular Digital Convolution Tabular Digital Convolution Tabular Digital Convolution Tabular Digital Convolution Y[n] = [9, 9, 11, 5, 2]  Tabular Digital Convolution Example-4: Convolve the following two rectangular sequences using the tabular method.  Tabular Digital Convolution Exercise-1: Find the convolution of the two sequences x[n] and h[n] given by, Exercise-2: Find the convolution of the two sequences x[n] and h[n] given by,  Tabular Digital Convolution Exercise-3: determine the output for the first three samples of ℎ[n] using the tabular method. Where x[n] = u[n] and h[n] = (0.25)nu[n] Solution  Boundary Effects Quite often nothing is known about input activity that precedes and follows the selection of input samples used for a convolution. This means that the calculations of the first few and the last few output samples will be uncertain, because they rely on unknown data. These output samples are said to be influenced by boundary effects. In analyzing an output signal, it is usually best to discount these samples. Fortunately, real signal analyses generally involve thousands of samples, so neglecting a few at the beginning and end will not have a major impact on the output. 21  Boundary Effects Example-A of boundary effect which happens when the input sequence x[n] and the impulse response h[n] of the system are not completely overlapped. Boundary effect can diminish if the impulse response samples are small. ? = output samples affected by boundary effect. 22  Boundary Effects Initial boundary effects may also be interpreted as output transients. Transient behavior is the relatively short-term behavior exhibited by a system output. Steady state part of the output is the long term behavior. FIR (finite impulse response) filters reach a clear steady state because their impulse responses have a finite number of samples, and can therefore can be shifted such that the impulse response samples are completely contained by the input signal, and do not extend into regions of unknown inputs. IIR (infinite impulse response) filters never reach a true steady state, because some of the infinite number of impulse response samples must inevitably lie outside the range of known input samples. However, the impulse response samples for stable filters, the only kind normally used, grow smaller with time. Thus, an approximate steady state is reached when only very small impulse response samples are combined with unknown inputs. 23  Boundary Effects Example-B: The input to a system is the unit step u[n]. The impulse response of the system is given by h[n] = 0.4δ[n] – δ[n - 1] +0.7δ[n - 2]. Find the output of the system using convolution and identify the transient and steady state portion of the output. 24  Boundary Effects Example-C: Use convolution to find the step response of the system whose impulse response is h[n] = (-0.55)nu[n] 25 Graphical Digital Convolution 26  Graphical Digital Convolution Example-5: Using the sequences defined in Figure, evaluate the digital convolution. 27 Graphical Digital Convolution 28 Graphical Digital Convolution 29 Graphical Digital Convolution Y[n] = [9, 9, 11, 5, 2] 30 Graphic Digital Convolution Example-6: Input Signal x[n] = [2, 1, -2] Impulse Response h[n] = [1, 2, -1] Output Signal Y[n] = [2, 5, -2, -5, 2] 31  Convolution by Formula Method Example-7: Using the sequences defined in Figure, evaluate the digital convolution. Y[n] = [9, 9, 11, 5, 2] 32 Properties of Convolution 33  Correlation A measure of similarity between a pair of energy signals, x[n] and y[n], is given by the cross-correlation sequence rxy[l] Where the parameter l is called lag, indicating the time-shift between the pair of signals. 34  Correlation There are applications where it is necessary to compare one reference signal with one or more signals to determine the similarity between the pair and to determine additional information based on the similarity. In digital communications, a set of data symbols are represented by a set of unique discrete-time sequences. If one of these sequences has been transmitted, the receiver has to determine which particular sequence has been received, by comparing the received signal with every member of possible sequences from the set. Similarly correlation can also be used for timing or distance recovery purpose (e.g., RADAR, SONAR, CDMA receiver, Ultrasound etc.) 35 Cross Correlation 36  Cross Correlation The number of samples N in the output signal will be N = M1 + M2 – 1 Where M1 is the number of samples in sequence x1[x] M2 is the number of samples in sequence x2[x] 37  Cross Correlation Example-8: Find the correlation b/w the two sequences x[n] and y[n] given by, 38  Cross Correlation Example-9: Find the correlation b/w the two sequences x[n] and y[n] given by, 39  Cross Correlation Cross correlation does not exhibit Commutative 40  Cross Correlation Example-10: Find the correlation of the two sequences x[n] and y[n] represented by, x[n] = [1, 2, 3, 4] y[n] = [5, 6, 7, 8] Solution Yxy[n] = [8, 23, 44, 70, 56, 39, 20] 41  Cross Correlation Example-11: Find the correlation of the two sequences x[n] and y[n] represented by, x[n] = [1, 1, 1, 1] y[n] = [1, 2, 3] Solution Yxy[n] = [3, 5, 6, 6, 3, 1] 42  Cross Correlation Excersize-1: Find the correlation of the two sequences x[n] and y[n] represented by, Excersize-2: Find the correlation of the two sequences x[n] and y[n] represented by, 43 Correlation Between Signals X and Y 44 Correlation Between Signals X and Z 45 Auto Correlation 46  Auto Correlation o Recovering a repeating pattern, or any periodic signal from its highly-noisy version o Recovering fundamental frequency of an otherwise random signal 47  Auto Correlation The number of samples N in the output signal will be N = 2×M – 1 Where, M is the number of samples in the sequence x[n] 48  Auto Correlation Example: Find the auto correlation of the following sequence x[n] = [1, 2, 3, 4] Solution Yxx[n] = [4, 11, 20, 30, 20, 11, 4] 49  Auto Correlation Example: Find the auto correlation of the following sequence x[n] = [1, 2, 3, 4] Solution Yxx[n] = [4, 11, 20, 30, 20, 11, 4] 50 Digital Signal & Image Processing Lecture-6  Overview Z Transform Properties of z-transform Transfer Function Transfer Function & Difference Equation Transfer Function & Impulse Response Inverse Z Transform Transfer Function & System Stability Difference Equation & System Stability Impulse & Step Responses Steady State Output  Z Transform The z transform is an important digital signal processing tool for describing and analyzing digital systems. It also supports the techniques for digital filter design and frequency analysis of digital signals. It takes a signal from the time domain to a frequency domain called the z domain. 53  Z Transform The z transform for a digital signal x[n] is defined as 𝑋 𝑧 = 𝒁 𝑥[𝑛] ∞ 𝑋 𝑧 = ෍ 𝑥 𝑛 𝑧 −𝑛 𝑛=−∞ where z is the complex variable. 54  Z Transform The z transform for causal signals is ∞ 𝑋 𝑧 = ෍ 𝑥 𝑛 𝑧 −𝑛 𝑛=0 It is referred to as a one-sided z-transform or a unilateral transform. 55  Z Transform Table # Signal x[n] Z Transform X(z) Region of Convergence 1 [n] 1 All z 2 u[n] Z/(Z-1) Z> 1 3  nu[n] Z/(Z-) Z>  4 nu[n] Z/(Z-1)2 Z> 1 5 n n u[n] Z-1/(1-Z-1)2 Z>  6 Cos(nΩ)u[n] ZsinΩ/(Z2 - 2zcosΩ + β) Z> 1 56 Z Transform Table 57  Region of Convergence (ROC) The z transform for every signal has an associated Region of Convergence (ROC), the region of the z domain for which the transform exists. Since the z-transform is an infinite series, it exists only for those values of z for which this series converges. All the values of z that make the summation exist form a Region of Convergence (ROC) in the z-transform domain. While all other values of z outside the ROC will cause the summation to diverge. 58  Z Transform Example-1: Determine the z-transform of the following signals. a) x[n] = δ[n] solution ∞ 𝑋 𝑧 = ෍ 𝛿 𝑛 𝑧 −𝑛 = 𝛿 0 = 1 𝑛=0 ROC: entier 𝑧 plane 59  Z Transform Example-1: Determine the z-transform of the following signals. b) x[n] = δ[n-1] solution ∞ 𝑋 𝑧 = ෍ 𝛿 𝑛 − 1 𝑧 −𝑛 = 𝛿 0 𝑧 −1 = 𝑧 −1 𝑛=0 ROC: entire 𝑧 plane except z = 0. 60  Z Transform Example-1: Determine the z-transform of the following signals. c) x[n] = u[n] Solution 𝑋 𝑧 = σ∞ 𝑛=0 𝑢 𝑛 𝑧 −𝑛 = σ ∞ 𝑛=0 𝑧 −𝑛 𝑋 𝑧 = 1 + 𝑧 −1 + 𝑧 −2 + 𝑧 −3 +…… This is a geometric series of the form a+ ar + ar2 +…. With initial term a equal to 1 and multiplier r equal to z-1. 𝑎 The sum of infinite geometric series is 𝑆∞ = 1−𝑟 1 𝑧 So X(z)= 1−𝑧 −1 = 𝑧−1 ROC: 𝑧 > 1 61  Z Transform Example-1: Determine the z-transform of the following signals. d) x[n] = u[n-1] Solution −1 1 −1 𝑧 1 X z =𝑧 1−𝑧 −1 = 𝑧 𝑧−1 = 𝑧−1 ROC: 𝑧 > 1 62  Z Transform Example-1: Determine the z-transform of the following signals. e) Solution x[n] = δ[n] + 2δ[n-1] + 5δ[n-2] + 7δ[n-3] + δ[n-5] ROC: entire 𝑧 plane except 𝑧 = 0 and z = 63  Z Transform Example-1: Determine the z-transform of the following signals. f) Solution x[n] = δ[n+2] + 2δ[n+1] + 5δ[n] + 7δ[n-1] + δ[n-3] ROC: entire 𝑧 plane except 𝑧=0 64  Z Transform Example-1: Determine the z-transform of the following signals. g) x[n] = anu[n] Solution 65  Z Transform Example-1: Determine the z-transform of the following signals. h) x[n] = (-0.5)nu[n] Solution 66  Z Transform Example-2: Find the z transform of the signal x[n] depicted in the figure. Solution The signal x[n] is described as: x[n] = 2δ[n] + δ[n-1] + 0.5δ[n-2] The z transform of the signal is 𝑋 𝑧 = σ∞ 𝑛=0 𝑥 𝑛 𝑧 −𝑛 𝑋 𝑧 = 𝑥 0 + 𝑥 1 𝑧 −1 + 𝑥𝑧 −2 𝑋 𝑧 = 2 + 𝑧 −1 + 0.5𝑧 −2 67 Properties of z-transform Linearity 68  Properties of z-transform Linearity Example-3: Find the z-transform of the sequence defined by Solution Applying the linearity of the z-transform, we have 69  Properties of z-transform Linearity Example-4: Find the z-transform of the sequence defined by Solution Applying the linearity of the z-transform, we have 70  Properties of z-transform Linearity Example-5: Find the z-transform of the signal x[n] defined by Solution Applying the linearity of the z-transform, we have 71  Properties of z-transform Time Shifting/Shift Theorem A one-sample delay in the time domain appears in the z domain as a z-1 factor. That is, Z{x[n-1]} = z-1X(z) More generally, Z{x[n-k]} = z-kX(z) 72 Properties of z-transform Time Shifting/Shift Theorem 73 Properties of z-transform Time Shifting/Shift Theorem 74  Properties of z-transform Time Shifting/Shift Theorem Example-6: Find the z-transform of the signal x[n] defined by Solution Applying the time shifting property of the z-transform, we have 75 Properties of z-transform Time Reversal 76  Properties of z-transform Time Reversal Example-7: Find the z-transform of the signal x[n] = u[-n] Solution Applying the time reversal theorem of the z-transform, we have 77  Properties of z-transform Convolution Convolution in time domain is equal to the multiplication in frequency domain and vice versa. 78  Properties of z-transform Convolution Proof: 79  Properties of z-transform Convolution Example-8: Consider the two sequences Find the Z transform of convolution Determine the convolution sum using the z-transform. Solution 80  Properties of z-transform Convolution Example-9: Compute the convolution of the following signals using z transform Solution 81 Properties of z-transform 82 Difference Equation Diagram using z–1 Notation Time shifting property of the z transform suggests a notation change for difference equation diagram. The delay blocks can be replaced by z-1 bocks. This convention mixes the time and z domain notations. 83 Difference Equation Diagram using z–1 Notation The general form of the non-recursive difference equation is y[n] = b0x[n] + b1x[n-1] + b2x[n-2] + … + bMx[n-M] Re-expressing the non-recursive difference equation diagram using the z-1 notation. 84 Transfer Function 85  Transfer Function In the z domain, the transfer function of a filter can be defined. The transfer function is the ratio of the output to the input in the z domain: 𝑌(𝑧) 𝐻 𝑧 = 𝑋(𝑧) In this equation Y(z) is the z transform of the output y[n] X(z) is the z transform of the input x[n] H(z) is the transfer function of the filter 86  Transfer Function & Difference Equation The general form of a difference equation is a0y[n] + a1y[n-1] + a2y[n-2] + … + aNy[n-N] = b0x[n] + b1x[n-1] + b2x[n-2] + … + bMx[n-M] Taking the z transform of the above equation a0Y(z)+ a1z-1Y(z)+ a2z-2Y(z) + … + aNz-NY(z) = b0X(z) + b1z-1X(z) + b2z-2X(z) + … + bMz-MX(z) Taking Y(Z) and X(Z) common and then cross multiply to get TF. 87  Transfer Function & Difference Equation Example-10: Find the transfer function described by the difference equation. 2y[n] + y[n-1] + 0.9y[n-2] = x[n-1] + x[n-4] Solution: Taking z transforms term by term we get, 2Y(z) + z-1Y(z) + 0.9z-2Y(z) = z-1X(z) + z-4X(z) Factoring out Y(z) on the left side and X(z) on the right side: (2 + z-1 + 0.9z-2)Y(z) = (z-1 + z-4)X(z) The transfer function (TF) is 𝑌(𝑧) 𝑧 −1 +𝑧 −4 H 𝑧 = = 𝑋(𝑧) 2+𝑧 −1 +0.9𝑧 −2 88  Transfer Function & Difference Equation Example-11: Find the transfer function described by the difference equation. y[n] – 0.2y[n-1] = x[n] + 0.8x[n-1] Solution: Taking z transforms term by term we get, Y(z) – 0.2z-1Y(z) = X(z) + 0.8z-1X(z) Factoring out Y(z) on the left side and X(z) on the right side: (1 – 0.2z-1)Y(z) = (1 + 0.8z-1)X(z) The transfer function (TF) is 𝑌(𝑧) 1 + 0.8𝑧 −1 H 𝑧 = = 𝑋(𝑧) 1 − 0.2𝑧 −1 89  Transfer Function & Difference Equation Example-12: Find the transfer function described by the difference equation. y[n] = 0.75x[n] - 0.3x[n-2] – 0.01x[n-3] Solution: Taking z transforms term by term we get, Y(z) = 0.75X(z) - 0.3z-2X(z) – 0.01z-3X(z) Factoring out Y(z) on the left side and X(z) on the right side: Y(z) = (0.75 - 0.3z-2 - 0.01z-3)X(z) The transfer function (TF) is 𝑌(𝑧) H 𝑧 = 𝑋(𝑧) = 0.75 − 0.3𝑍 −2 − 0.01𝑍 −3 90  Transfer Function & Difference Equation Example-13: Find the difference equation that correspond to transfer function. 𝟏 + 𝟎. 𝟓𝒛−𝟏 𝐇 𝒛 = 𝟏 − 𝟎. 𝟓𝒛−𝟏 Solution: Since H(z) = Y(z)/X(z), do the cross multiply to get (1 – 0.5z-1)Y(z) = (1 + 0.5z-1)X(z) then Y(z) – 0.5z-1Y(z) = X(z) + 0.5z-1X(z) Finally taking the inverse z transform term by term to get y[n] – 0.5y[n-1] = x[n] + 0.5x[n-1] 91  Transfer Function & Difference Equation Example-14: Find the difference equation that correspond to transfer function. 𝟏 + 𝟎. 𝟖𝒛−𝟏 𝐇 𝒛 = 𝟏 − 𝟎. 𝟐𝒛−𝟏 + 𝟎. 𝟕𝒛−𝟐 Solution: Since H(z) = Y(z)/X(z), do the cross multiply to get (1 – 0.2z-1 + 0.7z-2)Y(z) = (1 + 0.8z-1)X(z) then Y(z) – 0.2z-1Y(z) + 0.7z-2Y(z)= X(z) + 0.8z-1X(z) Finally taking the inverse z transform term by term to get y[n] – 0.2y[n-1] + 0.7y[n-2]= x[n] + 0.8x[n-1] 92  Transfer Function & Difference Equation Example-15: Find the difference equation that correspond to transfer function. 𝒛 𝐇 𝒛 = (𝟐𝒛 − 𝟏)(𝟒𝒛 − 𝟏) 𝑧 Solution: H 𝑧 = 8𝑧 2 −6𝑧+1 Since H(z) = Y(z)/X(z), do the cross multiply to get (8𝑧 2 − 6𝑧 + 1 )Y(z) = (z)X(z) Then 8z2Y(z) – 6zY(z) + y(z) = zX(z) Finally taking the inverse z transform term by term to get 8y[n] – 6y[n-1] + y[n-2] = x[n-1] 93  Transfer Function & Impulse Response The relationship between the transfer function and the impulse response of a system is also straightforward. the transfer function H(z) is the z transform of the impulse response h[n]. 𝐻 𝑧 = 𝒁 ℎ[𝑛] ∞ 𝐻 𝑧 = ෍ ℎ[𝑛]𝑧 −1 𝑛=0 Similarly Impulse response h[n] is inverse z transform of the transfer function H(z). ℎ[𝑛] = 𝒁−1 𝐻(𝑧) 94  Transfer Function & Impulse Response Example-16: Find the transfer function of the system whose impulse response is h[n] = δ[n] + 0.4 δ[n-1] + 0.2 δ[n-2] + 0.05 δ[n-3] Solution The transfer function H(z) of the system is the z transform of the impulse response h[n]. Taking z transform term by term we get H(z) = 1 + 0.4z-1 + 0.2z-2 + 0.05z-3 Note that we can also get the difference equation from the TF. y[n] = x[n] + 0.4x[n-1] + 0.2x[n-2]+ 0.05x[n-3] 95 System Outputs in Time & Z Domains The system output can be find using three different ways. 96  System Output using TF The definition of the transfer function (TF) provides a means of calculating filter outputs. That is, Y(z) = H(z)X(z) To determine the time domain output y[n], the inverse z transform of Y(z) must be taken. 97 Inverse Z Transform 98  Inverse Z Transform To convert a function in the z domain into a function in the time domain requires an inverse z transform. This conversion is necessary, for example, to find the time domain functions like x[n] that correspond to the z transforms X(z) y[n] that correspond to the z transforms Y(z) h[n] impulse response from a transfer function H(z) 99  Inverse Z Transform There are several ways of finding inverse z transforms: A: Formal Method Contour Integration B: Informal Methods 1- Inspection method using Z Transform Tables 2- Long Division (Synthetic Division or Power Series Expansion) 3- Partial Fraction Expansion 10 0  Inverse Z Transform A: Formal Method Contour Integration: where C represents a closed contour within the ROC of the z- transform. The most fundamental method for the inversion of z transform is the general inversion method which is based on the Laurent theorem. The contour integral of the above equation can be evaluated using the residue theorem. 10 1 Inspection Method using Z Transform Tables Example-17: Find the x[n] that corresponds to the z transform 𝒛 𝑿 𝒛 = 𝒛 − 𝟎. 𝟖 Solution Using z transform table, the inverse z transform is 𝑥 𝑛 = 𝑍 −1 𝑋(𝑧) 𝑥 𝑛 = (0.8)𝑛 𝑢[𝑛] 10 2  Inspection Method using Z Transform Tables Example-18: Find the inverse z transform of the function 𝒛𝟐 − 𝟎. 𝟗𝒛 𝑿 𝒛 = 𝟐 𝒛 − 𝟏. 𝟖𝒛 + 𝟏 Using z transform table, the inverse z transform is 𝑥 𝑛 = 𝒁−1 𝑋(𝑧) 𝑧 2 − 0.9𝑧 𝑋 𝑧 = 2 𝑧 − 1.8𝑧 + 1 cosΩ = 0.9 Ω = cos-1(0.9) = 0.451 𝑥 𝑛 = cos(𝑛Ω)𝑢[𝑛] 𝑥 𝑛 = cos(0.451Ω)𝑢[𝑛] 10 3  Long Division Method ADVANTGES Relatively straight forward method Applicable to any rational function Can be use to convert improper rational function into proper rational function DISADVANTAGES Sometimes will run to infinity General close-form solution cannot be found 10 4 Transfer Function & System Stability Transfer function can be expressed as a rational function consist of numerator polynomial divided by denominator polynomial. The highest power in a polynomial is called its degree. In a proper rational function, the degree of the numerator is less than or equal to the degree of the denominator. In a strictly proper rational function, the degree of the numerator is less than the degree of the denominator. In an improper rational function, the degree of the numerator is greater than the degree of the denominator. 10 5 Long Division Method 10 6  Long Division Method Example-19: Using long division method, determine the inverse z-transform of H(z) = 1 – 0.5z-1 - 0.6z-2 + 0.64z-3 + … 10 The inverse Z transform is h[n] = δ[n] – 0.5δ[n-1] – 0.6δ[n-2] + 0.64δ[n-3] + … 7  Long Division Method Example-20: Using long division method, determine the inverse z-transform of X(z) = 5z-2 – z-3 + 0.2z-4 – 0.04z-5 + … 10 The inverse Z transform is x[n] = 5δ[n-2] – δ[n-3] + 0.2δ[n-4] – 0.04 δ[n-5] + … 8  Long Division Method Example-21: Using long division method, determine the inverse z- transform of Solution: First arranged in descending powers of Z then dividing the numerator of 𝑋(𝑧) by its denominator we obtain power series 10 9  Long Division Method 11 The inverse Z transform is x[n] = δ[n+2] + 3δ[n+1] + δ[n] + δ[n-2] + δ[n-3] + δ[n-4] + … 0  Long Division Method Example-22: Using long division method, determine the inverse z- transform of Solution: By dividing the numerator of 𝑋(𝑧) by its denominator we obtain power series Using z-transform table or 11 1  Long Division Method Example-23: Using long division method, determine the inverse z- transform of Solution: By dividing the numerator of 𝑋(𝑧) by its denominator we obtain power series Using z-transform table or 11 2  Partial Fraction Method ADVANTGES It decompose the higher order system into sum of lower order system General close-form solution can be found DISADVANTAGES Applicable to strictly proper rational function in standard form Getting complex by handling 3 different types of roots for a polynomial function of z, i.e., 1. Distinct Real Roots 2. Repeated Real Roots 3. Complex Conjugate Roots 11 3  Partial Fraction Method Example-24: Using partial fraction method find the inverse z- transform of the signal Y(z), if x[n] = u[n-1], h[n] = (-0.25)nu[n]. Solution As we know that Y(z) = X(z)H(z) where 1 𝑋 𝑧 = 𝑧−1 𝑧 𝐻 𝑧 = 𝑧 + 0.25 So, 𝑧 𝑌(z) = (z + 0.25)(𝑧−1) 11 4  Partial Fraction Method 𝑧 𝑌(𝑧) = (z + 0.25)(𝑧−1) The partial fraction expansion is 𝐴 𝐵 𝑌 𝑧 = + 𝑧 + 0.25 𝑧 − 1 The coefficient A and B can be found using the cover-up method. 𝑧 + 0.25 𝑧 −0.25 𝐴= lim = = 0.2 𝑧→−0.25 (z + 0.25)(𝑧 − 1) −0.25 − 1 𝑧−1 𝑧 1 𝐵 = lim = = 0.8 𝑧→1 (z + 0.25)(𝑧 − 1) 1 + 0.25 0.2 0.8 −1 0.2𝑧 0.8𝑧 𝑌 𝑧 = + =𝑧 + 𝑧 + 0.25 𝑧 − 1 𝑧 + 0.25 𝑧 − 1 11 5  Partial Fraction Method −1 0.2𝑧 0.8𝑧 𝑌 𝑧 =𝑧 + 𝑧 + 0.25 𝑧 − 1 The portion inside the brackets has a inverse z transform is 0.2(-0.25)nu[n] + 0.8u[n] The z-1 term outside the brackets indicates a time shift by one step. Thus, the final inverse transform is X[n] = 0.2(-0.25)n-1u[n-1] + 0.8u[n-1] 11 6  Partial Fraction Method Example-25: Using partial fraction method find the inverse z- transform of the signal 5 X(z) = 𝑧 2 + 0.2𝑧 Solution The denominator of X(z) can be factored to give 5 X(z) = 𝑧(𝑧 + 0.2) The partial fraction expansion is 𝐴 𝐵 25 X 𝑧 = 𝑧 + 𝑧 + 0.2 = 𝑧 + 𝑧 −25 + 0.2 = 𝑧 −1 (25 − 25 𝑧 𝑧 + 0.2 ) Thus, the final inverse transform is X[n] = 25δ[n-1] – 25(−0.2)𝑛−1 𝑢[𝑛 − 1] 11 7  Partial Fraction Method Example-26: Using partial fraction method find the inverse z- transform of the signal 0.5 Y z = 𝑧(𝑧 − 1)(𝑧 − 0.6) Solution The denominator is already factored into simple factors. The partial fraction expression of Y(z) has three terms, one for each of the roots in the denominator; 𝐴 𝐵 𝐶 𝑌(𝑧) = + + 𝑧 𝑧 − 1 𝑧 − 0.6 Covering up the z term in the denominator and evaluating Y(z) at z = 0, 0.5 5 A= = (0 − 1)(0 − 0.6) 6 11 8  Partial Fraction Method Covering up the (z - 1) term in the denominator and evaluating at t = 1, 𝟎. 𝟓 𝟓 𝑩= = (𝟏)(𝟎 − 𝟎. 𝟔) 𝟒 Covering up the (z - 0.6) term and evaluating at t = 0.6, 𝟎. 𝟓 𝟐𝟓 𝑪= =− (𝟎. 𝟔)(𝟎. 𝟔 − 𝟏) 𝟏𝟐 Hence 𝟓 𝟓 𝟐𝟓 𝟓 𝟐𝟓 − 𝟓 𝒛 − 𝒛 𝒀 𝒛 = + 𝟔 𝟒 + 𝟏𝟐 = 𝒛−𝟏 + 𝟒 + 𝟏𝟐 𝒛 𝒛−𝟏 𝒛 − 𝟎.𝟔 𝟔 𝒛−𝟏 𝒛 − 𝟎.𝟔 The inverse z transform using the Table is 𝟓 𝟓 𝟐𝟓 y[n] = δ[n - 1] + 𝒖 𝒏 − 𝟏 − (0.6)n-1 u[n - 1] 𝟔 𝟒 𝟏𝟐 11 9  Partial Fraction Method Example-27: Using partial fraction method find the impulse response of the system 𝑧 −2 𝐻 𝑧 = 1+0.25𝑧 −1 Solution Changing to standard from, the transfer function becomes; 1 𝐻(𝑧) = 2 𝑧 + 0.25𝑧 Its partial fraction expansion is 1 𝐴 𝐵 𝐻 𝑧 = = + 𝑧 𝑧 + 0.25 𝑧 𝑧 + 0.25 12 0  Partial Fraction Method 4 −4 𝐻 𝑧 = + 𝑧 𝑧 + 0.25 −1 4𝑧 𝐻 𝑧 =𝑧 4− 𝑧 + 0.25 The portion within the brackets gives the inverse transform 4δ[n] - 4(-0.25)n u[n], so the final inverse transform is h[n] = 4δ[n - 1] - 4(-0.25)n-1u[n - 1] 12 1  Partial Fraction Method Example-28: Using partial fraction method find the inverse z- transform of the signal 5 𝑋(𝑧) = 2 𝑧 + 0.2𝑧 Solution The denominator of X(z) can be factored to give; 5 𝑋 𝑧 = 𝑧 𝑧 + 0.2 Its partial fraction expansion is 5 𝐴 𝐵 𝑋 𝑧 = = + 𝑧 𝑧 + 0.2 𝑧 𝑧 + 0.2 12 2  Partial Fraction Method 25 −25 𝑋 𝑧 = + 𝑧 𝑧 + 0.2 −1 25𝑧 𝑋 𝑧 =𝑧 25 − 𝑧 + 0.2 The final inverse transform is x[n] = 25δ[n - 1] - 25(-0.2)n-1u[n - 1] 12 3  Partial Fraction Method Example-29: Using partial fraction method find the inverse z- transform of the signal Solution Eliminating the negative power of 𝑧 by multiplying the numerator and denominator by 𝑧2 yields Dividing both sides by 𝑧 leads to 12 4  Partial Fraction Method Again, we write where A and B are constants found as 12 5  Partial Fraction Method Thus Multiplying 𝑧 on both sides gives From table of z-transform pairs 12 6  Partial Fraction Method Example-30: Using partial fraction method find the inverse z- transform of the signal Solution Dividing both sides by 𝑧 leads to Using partial fraction method Multiplying 𝑧 on both sides gives From table of z-transform pairs 12 7  Partial Fraction Method Example-31: Using partial fraction method find the inverse z- transform of the signal Solution Eliminating the negative power of 𝑧 by multiplying the numerator and denominator by 𝑧3 yields Coefficient of highest power in denominator should be 1. Therefore 12 8  Partial Fraction Method Dividing both sides by 𝑧 leads to Using partial fraction method Multiplying 𝑧 on both sides gives From table of z-transform pairs 12 9 System Stability 13 0 Transfer Function & System Stability The poles and zeros of a system can be determined easily from the system’s transfer function. The poles and zeros of a system can provide a great deal of information about the behavior of the system. In a standard form, TF can be expressed as a rational function consist of numerator polynomial divided by denominator polynomial. 13 1 Transfer Function & System Stability It is easiest to identify the poles and zeros if the rational transfer function is converted to the form which has only positive exponents. 13 2 Transfer Function & System Stability The zeros or roots of the numerator polynomial are the zeros of the system. The roots of the denominator polynomial are the poles of the system. 13 3 Transfer Function & System Stability 13 4  Transfer Function & System Stability Poles are the values of 𝑧 that make the denominator of a transfer function zero. Zeros are the values of 𝑧 that make the numerator of a transfer function zero. Of the two, poles have the biggest effect on the behavior of a digital system (digital filter). Zeros tend to modulate, to a greater or lesser degree depending on their position relative to the poles. The poles of digital filter can be found if its transfer function is known. Both zeros and poles are in general complex numbers. 13 5  Transfer Function & System Stability A very powerful tool for the digital system analysis and design is a complex plane called z plane, on which poles and zeros of the transfer function are plotted. On the z plane, poles are plotted as crosses (X) zeros are plotted as circles (O) A plot showing pole and zero locations is called a pole-zero plot. 13 6  Transfer Function & System Stability Example-32: for a first order system the poles and zeros are 2 𝐻 𝑧 = 1+0.4𝑧 −1 Poles: at 𝑧 = -0.4 Zeros: at 𝑧 = 0 13 7  Transfer Function & System Stability The position of the poles and zeros on the z plane can give clue about the way a digital filter will behave. One reason the poles of a system are so useful is that they determine whether or not the filter is stable. The system is stable as long as the poles lie inside the unit circle, which is a circle of unit radius on the z plane. Since poles are complex numbers, this requires that their magnitudes be less than one. Mathematically, the region of stability can be described as 13 8  Transfer Function & System Stability If the magnitude of each pole is less than one, the poles are less than one unit’s distance from the center of the unit circle, and the filter is stable. If any of the poles of a system lie outside the unit circle, the filter is unstable. If the outermost pole lies on the unit circle, the filter is described as being marginally stable. 13 9 Transfer Function & System Stability Example-33: Find the poles and zeros and stability for the digital filter whose transfer function is Solution Eliminating negative exponents yields Poles: at 𝑧 = 0.25 and 𝑧 = 2 Zeros: at 𝑧 = 0 As one pole lie outside the unit circle at z = 2, hence the system is unstable. 14 0 Transfer Function & System Stability Example-34: The transfer function of a digital system is 1 − 𝑧 −2 𝐻 𝑧 = 1 + 0.7𝑧 −1 + 0.9𝑧 −2 Is this system stable? The poles are located at −0.35 ± 𝑗0.8818 For these poles the distance from the center of the unit circle is 𝑧 = −0.35 2 + 0.8818 2 = 0.9487 As both poles lie inside the unit circle, So the system is stable. 14 1 Transfer Function & System Stability Example-35: Determine the stability of the following system. Solution: Eliminating negative exponents yields As all poles lie inside the unit circle, hence the system is stable. 14 2 Difference Equation & System Stability Example-36: Find the stability of the filter if the difference equation of the filter is Y[n] + 0.8y[n-1] – 0.9y[n-2] = x[n-2] Solution: 14 3 Impulse & Step Responses 14 4 Impulse & Step Responses 14 5  Impulse & Step Responses For a step input, we can determine step response assuming zero initial conditions. Letting the step response can be found as 14 6  Impulse & Step Responses The z-transform of the general system response is given by We can determine the output 𝑦(𝑛) in time domain as 14 7  Impulse & Step Responses Example-37: The transfer function of a digital system is 2 𝐻 𝑧 = 1 − 0.4𝑧 −1 a) Determine the difference equation of the system. b) Find the pole-zero plot and evaluate stability. c) Find and plot the impulse response. Solution a) The difference equation is y[n] – 0.4y[n – 1] = 2x[n] 14 8  Impulse & Step Responses b) The poles and zeros are found from 2 2𝑧 𝐻 𝑧 = −1 = 1 − 0.4𝑧 𝑧 − 0.4 There is single zero at z = 0 and a single pole at z = 0.4. as shown in the figure. The pole is within the unit circle So the system is stable. 14 9  Impulse & Step Responses c) The impulse response of the system is h[n] = 2(0.4)nu[n] The impulse response is plotted in the figure. 15 0  Impulse & Step Responses Example-38: Given a transfer function depicting a DSP system Determine a) the Impulse response ℎ(𝑛) b) the step response 𝑦(𝑛) c) system response 𝑦(𝑛) if the input is given as 𝑥(𝑛) = (0.5)𝑛𝑢(𝑛) 15 1  Impulse & Step Responses Solution a) the Impulse response ℎ(𝑛) The transfer function can be rewritten as We get Taking inverse z transform yields 15 2  Impulse & Step Responses b) the Step response s(n) or y(𝑛) the z-transform of the step response is or We get Taking inverse z transform yields 15 3  Impulse & Step Responses c) system response 𝑦(𝑛) if the input is given as 𝑥(𝑛) = (0.5)𝑛𝑢(𝑛) the z-transform of the step response is or We get Taking inverse z transform yields 15 4 Impulse & Step Responses 15 5  Impulse & Step Responses The impulse response of a stable system always settles to zero. The step response of a stable system always settles to a constant value. For unstable systems, on the other hand, these responses grow without bound. Marginally stable systems produce cycling or oscillating behavior. 15 6 Impulse & Step Responses Stability Illustrations 15 7 Impulse & Step Responses Stability Illustrations 15 8  Impulse & Step Responses Among the stable systems, the closer the poles are to the unit circle, the longer the impulse and step responses take to settle to their final values. When all poles are extremely close to the origin of the z plane, the responses reach their final values almost immediately. 15 9  Impulse & Step Responses Stable and unstable impulse responses on the z plane 16 0 Impulse & Step Responses Poles Near Origin 16 1 Impulse & Step Responses Poles Near Origin 16 2 Impulse & Step Responses Poles Near Unit Circle 16 3 Impulse & Step Responses Poles Near Unit Circle 16 4  Steady State Output The steady state output for the step response of a stable system may be computed using the system’s difference equation, by replacing all outputs y with ySS and all inputs x with one (1). For example, the difference equation y[n] + Ay[n-1] + By[n-2] = x[n] produces ySS + AySS + BySS = 1 which gives a steady state output ySS = 1/(1+A+B) 16 5  Steady State Output The steady state output for the impulse response of a stable system is always zero. Replacing the outputs y with ySS and the inputs x with zero (0) For example, the difference equation y[n] + Ay[n-1] + By[n-2] = x[n] produces ySS + AySS + BySS = 0 which gives a steady state output ySS = 0 16 6  Steady State Output The zeros of a system do not have as great an impact on the system’s behavior as do the poles. In fact, when zeros occur far away from the poles, they have a negligible effect. When a zero lies close to a pole, however, it effectively cancels the behavior due to the pole. 16 7 Impulse & Step Responses Effect of Zero Position on Impulse Response 16 8 Impulse & Step Responses Effect of Zero Position on Impulse Response 16 9 Impulse & Step Responses Effect of Zero Position on Impulse Response 17 0 Digital Signal & Image Processing Lecture-7  Overview Realization of Digital Systems Direct-form I Realization Direct-form II Realization Cascade or Series Realization Parallel Realization  Realization of Digital Systems A realization is a hardware or software configuration that implements the system. Digital filters described by the transfer function 𝐻(𝑧) may be generally realized into the following forms:  Direct-form I  Direct-form II Cascade or Series  Parallel There are other forms of realizations such as lattice, however in this course we will only study above mentioned realizations. 17 3  Realization of Digital Systems The transfer function 𝐻(𝑧) of the digital filter (system) transfer is given by: Let 𝑥(𝑛) and 𝑦(𝑛) be the digital filter (system) input and output, respectively. We can express the relationship in 𝑧-transform domain as: 17 4  Realization of Digital Systems By substituting 𝐻(𝑧) from equation (1) in (2) yields Taking the inverse of the 𝑧-transform of Equation (3) we get the difference recursive difference equation 17 5  Direct-Form I Realization The recursive difference equation can be implemented by the direct- form I realization as shown in the figure. 17 6  Direct-Form I Realization Calculation for 𝑦(𝑛) using this form require 𝑀+1 input states, 𝑁 output states, 𝑀+𝑁+1 coefficient multiplications, and 𝑀+𝑁 additions. When more than two or three delays are needed, this particular implementation is very sensitive to the finite word length effects. 17 7  Direct-Form I Realization Example-1: Draw a Direct-Form I realization of a second-order transfer function H(z) given by Solution 17 8  Direct-Form II Realization We consider digital filter (system) defined with transfer function, 𝐻(𝑧), given by Considering 𝑁=𝑀, we can express equation (5) as 17 9 Direct-Form II Realization 18 0  Direct-Form II Realization Realization of Equations (9) and (10) produces direct-form II realization, (also called canonical form) which is demonstrated in following figure. 18 1  Direct-Form II Realization Much less storage is needed if a direct form II realization is used. This realization requires the use of an intermediate signal 𝑤(𝑛) that records salient information about the history of the filter in place of past inputs and past outputs. Instead of 𝑁 past outputs and 𝑀 past inputs, only max(𝑁,𝑀) samples of the intermediate signal need to be remembered to produce the new filter outputs. Calculation for 𝑦(𝑛) using this implementation require max(𝑁,𝑀)+1 intermediate states, 𝑀+𝑁+1 coefficient multiplications, and 𝑀+𝑁 additions. 18 2  Direct-Form II Realization Example-2: Draw a Direct-Form II realization of a second-order transfer function given by Solution The difference equations for the direct-form II realization are expressed as 18 3  Direct-Form II Realization The realization is shown in following figure. 18 4 Transpose of the Direct-Form II Realization Transpose of the direct form II realization is an another popular implementation model, obtained by reversing the flows of information of the direct form II realization. 18 5 Transpose of the Direct-Form II Realization To minimize the finite word length effect, second order blocks of the direct form II realization or its transpose are frequently connected together in cascade or parallel combinations to produce higher order filter implementation. Direct Form II Realization Transpose of Direct Form II Realization 18 6 Cascade (Series) Realization 18 7  Cascade (Series) Realization When two or more systems are combined in cascade (in series), the transfer functions of the systems can be used to determine a transfer function for the overall system. E.g. The transfer function of two systems H1(z) and H2(z) cascaded together is H(z) = H1(z)H2(z) The block diagram of the cascade, or series, realization is depicted in following figure. 18 8  Cascade (Series) Realization Example-3: Draw a Cascade realization of a second-order transfer function H(z) given by Solution To achieve the cascade (series) form realization, we factor 𝐻(𝑧) into two first-order sections to yield 18 9  Cascade (Series) Realization where 𝐻1(𝑧) and 𝐻2(𝑧) are chosen to be 19 0 Cascade (Series) Realization 19 1  Cascade (Series) Realization Example-4: Find the difference equation that corresponds to the cascaded system. First write down the difference equation of each stage. For stage 1: y1[n] = x1[n] – 0.1x1[n-1] + 0.2x1[n-2] For stage 2: y2[n] = x2[n] + 0.3x2[n-1] + 0.1x2[n-2] For stage 3: y3[n] = x3[n] – 0.4x3[n-1] 19 2  Cascade (Series) Realization First write down the difference equation of each stage. For stage 1: y1[n] = x1[n] – 0.1x1[n-1] + 0.2x1[n-2] For stage 2: y2[n] = x2[n] + 0.3x2[n-1] + 0.1x2[n-2] For stage 3: y3[n] = x3[n] – 0.4x3[n-1] Then find the transfer function of each stage. For stage 1: H1(z) = 1 – 0.1z-1 + 0.2z-2 For stage 2: H2(z) = 1 + 0.3z-1 + 0.1z-2 For stage 3: H3(z) = 1 – 0.4z-1 19 3  Cascade (Series) Realization The transfer functions of the three stages are. For stage 1: H1(z) = 1 – 0.1z-1 + 0.2z-2 For stage 2: H2(z) = 1 + 0.3z-1 + 0.1z-2 For stage 3: H3(z) = 1 – 0.4z-1 The overall transfer function of the system is H(z) = H1(z)H2(z) H3(z) H(z) = 1 – 0.2z-1 +0.19z-2 – 0.058z-3 – 0.008z-5 Finally the difference equation can be get from the H(z) Y3[n] = x1[n] -0.2x1[n-1] + 0.19x1[n-2] - 0.058x1[n-3] – 0.008x1[n-5] 19 4  Cascade (Series) Realization Example-5: Find the transfer function of the transposed direct form II realization of the filter. First write down the difference equation of each stage. For stage 1: y1[n] = – 0.1y1[n-1] + 0.5y1[n-2] + 2.5x1[n] + 0.9x1[n-1] - 0.4x1[n-2] For stage 2: y2[n] = 0.2y2[n-1] - 0.2y2[n-2] + 1.2x2[n] + 0.5x2[n-1] + 0.1x2[n-2]195  Cascade (Series) Realization The difference equation for the filter is most exactly found by multiplying the transfer function for each stage. H(z) = H1(z)H2(z) 2.5 + 0.9𝑧 −1 − 0.4𝑧 −2 1.2 + 0.5𝑧 −1 + 0.1𝑧 −2 𝐻 𝑧 = 1 + 0.1𝑧 −1 − 0.5𝑧 −2 1 − 0.2𝑧 −1 + 0.2𝑧 −2 3 + 2.33𝑧 −1 + 0.22𝑧 −2 − 0.11𝑧 −3 − 0.04𝑧 −4 𝐻 𝑧 = 1 − 0.1𝑧 −1 + 0.32𝑧 −2 + 0.12𝑧 −3 − 0.1𝑧 −4 19 6 Parallel Realization 19 7  Parallel Realization When two or more systems are combined in parallel the transfer functions of the systems can be used to determine a transfer function for the overall system. E.g. The transfer function of the two systems connected in parallel is H(z) = H1(z) + H2(z) The resulting parallel realization is illustrated in the block diagram in following Figure. 19 8  Parallel Realization Example-6: Find the transfer function of the parallel combination. For Top Section: 𝐻1 𝑧 = 𝑧 −1 1+0.25𝑧 −1 +0.1𝑧 −2 For Bottom Section: 𝐻2 𝑧 = 1+0.2𝑧 −1 +0.4𝑧 −2 19 9  Parallel Realization The overall transfer function of the parallel system is 1 + 0.25𝑧 −1 + 0.1𝑧 −2 −1 𝐻 𝑧 = + 𝑧 1 + 0.2𝑧 −1 + 0.4𝑧 −2 20 0  Parallel Realization Example-7: Draw parallel realization of a second-order transfer function given by Solution In order to yield the parallel form of realization, we need to make use of the partial fraction expansion. We get 20 1 20 2  Parallel Realization using the direct-form II realization for each section, we obtain the parallel realization in Following figure. 20 3  Realization of Digital Systems In practice, the second-order filter module with the direct- form I or direct-form II realization is used. The high-order filter can be factored in the cascade form with the first- or second-order sections. In cases where the first order-filter is required, we can still modify the second-order filter module by setting the corresponding filter coefficients to be zero. 20 4