UNIT-I Introduction to Digital Signal Processing Important Points to Remember «There are two types of signal processing = Analog signal processing and digital signal processing. Digital Signal Processing (DSP) has large number of advantages compared to analog signal processing, DSP is used in voice, speech, communication, consumer application, graphics, imaging, millitary, biomedical, industry, instrumentation, control and automation. 1.1 Introduction to Digital Signal Processing Part A: Short Answered Questions Q4 Write four advantages of digital Processing over analog signal processing. 1G [NTU : May-16, Marks 2] signal Ans.:i) DSP systems are flexible, They can be reconfigured easily. fi) DSP systems are highly accurate. They do not suffer from component tolerances. DSP systems are capable of performing complex mathematical algorithms easily. DSP systems are economical, liable and adaptable. Performance of DSP systems is repeatable. ii) iv) y Q.2 State four important applications of DSP. ‘Ans.:i) Speech recognition, speech vocoding, speech synthesis. fi) Echo cancellation, data encryption, cellular phone, video conferencing. voice mail, iil) Video, television, music, toys, music synthesizer. iv) Radar and sonar processing, navigation, missile guidance, RF modems. v) Xray enhancement, ultrasound equipment, CT scanning equipments vi) Robotics, CNC, security access, monitors. power line Q3 State advantages and disadvantages of DSP. ES" [INT = Sept-06, Marks 3, May-12, Marks 3] Ans. : Advantages : Please refer Q.1. Disadvantages = i) For wide band signals high speed A/D converters are required. ii) For small expensive. applications, DSP systems are Q4 Compare between DSP and analog signal processing. ESP [INTU : May-12, Marks 3] ‘Ans. : St.| Parameter | Analog system | Digital systems No. 1. | Time/Amplitude | Continuous | Discrete time time and and amplitude amplitude 2 | Hardware units | Resistance, | Flip-flops, shift capacitance, | registers, inductance, | counters, diodes, ‘memories, transistors, | adders, FETs ete. ‘multipliers. 3. | Functionality | Normally One digital single finction | hardivare con by each analog | implement system mulltiple functions by changing software 4 | Software No software | Hardware and program [program only | software both hardware ate present anIntroduction to Digital Signal Processing 1 Sigal Prosing 5] Conversion | Analog syste | Digial one ee converted to | converted to digital system | analog sytem Mi the hep | with te help GADD” | oDIOA fomertre. | convertors Part B : Long Answered Questions Q5 Draw the block diagram showing basic elements of digital signal processing and explain them. 03 [JNTU : May-12, Marks 5; May-11, Marks 5] Ans: Fig, Q5.1 shows the basic elements of digital signal processing. Analog to Digital Converter : The A/D converter converts analog input signal to its digital equivalent. ‘The DSP system processes this digital signal. Digital Signal Processer : It is also called DSP processor. It performs various operations such as amplification, attenuation, filtering, spectral analysis, feature extraction on digital data. The DSP processor consists of ALU, Shifter, serial ports, interrupts, address generater ete for its functioning. The DSP processors have special architectural features due to which DSP operations are implemented fast. Digital to Analog Converter : The D/A converter obtains analog signal from its digital version. The signals such as sound, video etc are required in analog from. Q6 Give the basic block diagram of DSP. State its merits and demerits. 2 [JNTU : May-12, Marks 10] Ans. : Please refer Q3 and Q5. 12 Discrete Time Signals, Sequences, Conversion and Operations Important Points to Remember * The signals are to be digitized before being processed by DSP system. To avoid aliasing, the signals are sampled at the minimum rate of twice of highest of signal frequency fs > 2 fmax Nyaquist rate = 2W, here "W" is the highest signal frequency. Dynamic systems consists integration, differentiation, delay elements or accumulation terms in their equation. of The system becomes time variant when the output is some function of time operator 't or 'n’ directly. Linear system produces zero output if input is zero under relaxed condition. Unit impulse or unit sample functions are used to determine impulse response of the system. Unit step function models application of DC supply to the circuit. Unit ramp function indicates charging current of the capacitor. Part A: Short Answered Questions Q7 Define sampling and Nyquist rate. & [INTU : May-16, Marks 3] Ans. : Sampling : A continuous time signal x,(t) is converted to discrete time signal x(n) by sampling. A. sampler takes the samples at regular intervals. Sampling theorem : A continuous time signal can be completely represented in its samples and recovered back if the sampling frequency F, > 2W. Here F, is the sampling frequency and W is the maximum frequency present in the signal, L¢. Fmay W. put Output Ggital digital put ‘Analog to] sional [Digital | signat [Digtalto ] Output anaiog digital signal analog |e analog ‘signal converter processor converter | Sena! Fig. Q.5.1 Basic elements of digital signal processing FF recemuca PuaLicAriONs™ An up inst br keeledDigital Signal Processing Introduction to Digital Signal Processing Nyquist rato: When the sampling rate becomes exactly equal to 2W (i.e. 2Finax) samples per second for signal bandwidth of "W Hz, then it is called Nyquist rate. ‘Thus, Nyquist interval : interval. ie, Nyquist rate = 2W = 2Fnay It is the reciprocal of Nyquist 14 2W ~ 2F yay Nyquist interval = Q.2 What is aliasing ? How it can be avoided ? Ans. : Aliasing : When the sampling rate F, is less than 2W (twice of highest signal frequency), higher signal frequency takes the form of lower signal frequency. This happens due to overlap of spectrums of sampled signal. This is called aliasing. Ways to avold aliasing : (i) Sampling rate F, must be made higher than 2W and (i) Signal must be strictly band limited to 2W. Q9 State frequency relationships in discrete and analog domain. Ans.:¢ The discrete time signal frequency (), continuous time frequency (F) and sampling frequency (F,)is represented as, fe Bert hee T= p 2 Fe ale oT o- ‘ Range of DT frequencies is given as, de pc or news -F8 FS ws Thus maximum signal frequency i8 fax * Q.40 Classify signals. Ans. : Following figure gives the classification. “Classification based on time amplitude characteristics 411 What are the standard discrete time signals ? Ans. : (i) Unit sample signal, 8 (n)= 1 at = 0 (Gi) Unit step signal, u(u)=1 at n= 0 (iii) Unit ramp signal, r(n)= n for n> 0 (iv) Exponential signal, x(x) = a 0.12 What do you mean by signal delay, time folding, time compression / expansion and precedence of time shifting and time sealing ? Sr [INTU = May-12, Marks 3] ‘Ans. :¢ When the signal is delayed, it is shifted right and if itis advanced, it is shifted left. * Time folding ofthe signal is equiealent to taking its mirror image at t = 0 oF = If y(t) = x(2t), the time axis is oi bya intr of. Aaa if y0)=>(4), the time axis is expanded by a factor of ‘2 ‘© Prececience rule of shifting and time scaling states : 1. First do the shifting operation. 2. Then do the time scaling operation. Q.13 Find and sketch the even and odd parts of these functions: a) sin) = w(n)— win 4) b) xtn) = sia ( a(n). Ans. a) x(n) = u(n)- u(n 4) Fig. 0131 shows odd and even parts of above sequence 2nn 4 4, Analog and digital signals 2. Continueus and discrete amplitude signals 3. Continuous and discrete time signals 4, Multichannel and mutidinensional signa's 4, Periodic and non perce signals 2, Energy and power signals 3. Even and odd signals 4, Deterministe and random signals OP reac Pum caren dopa br ene1 Signal Processing a4 Introduction to Digital Signal Processing 1 ay] I 1 [ I I I -x(-n) | | | | | I | | | I I I | I i | | | | I I | | ! f "42" | | I I I, | | 4 2|3 I I xi0) 1 A 3 112 =3 | 1 %efn) *_{A1) ? | | e ray | 2 ial rl I 3 tla 3 vty ae ~ te Fig, 192 Odd and even parts of xa) sn (224) win FF recemuca PUaLICATIONS™ An up nat br kengeDigital Signal Processing Introduction to Digital Signal Processing Part B : Long Answered Questions Q.14 State and prove lowpass signals. ‘Ang: Statement : A continuous time signal can be completely represented in its samples and recovered back if the sampling frequency is twice of the highest frequency content of the signal ie, sampling theorem for f22" Proof : Sampling : The sampled signal is given as, xg) = FOB 27) ‘Taking Fourier transform of this signal, X(N = = Sanae-ot)| FT {a{t)}* FT 18 (f-nT,)) XD fe BSH) f EX) 8-0) fe BXU-mf) ss. (Q141) Above equation shows that X(@) is placed at + f,, Efe AB fey FT of a DT signal is given as, x = SL xtmetenfn Here X() is contiuous and ‘f is continuous frequency. If we replace X(p) by Xs( J) then continuous frequency will be replaced by £ Ss -janbn 2 x Exe Here note that ' f is continuous frequency and ¢ is dirt ogy. Ab xo)=2(;)amd 2 * Xs = Yate Fre (Q.142) If f. = 2W, then from equation (Q.14.1) we can write, Te Xs) = f.X(/) for-W< f2W : Having ling rate higher than 2W, the overlap between the spectrums of X(), Xft fob XUF #2 fon is absent. Hence there is no aliasing. if) Bandlimiting the signal : Minimum sampling rate for avoiding aliasing is 2W. Hence signal must be lowpass filtered to avoid any frequency components higher than 2W. This avoids aliasing. Q.16 An analog signal contains frequencies upto 10 ket. i) What range of sampling frequencies allows exact reconstruction of this signal from its samples ? Hi) If this signal is sampled with a sampling frequency F, = 8 kHz, what is the folding frequency ? Examine what happens to the frequency Fy Examine what happens to the frequency Fa 5 kee. 9 kt. J s [ TVET TseCN TT TNCETEET LN 88 pag SU hee E38 es [| 88 ase b T1838 Se ese [les Base gl Bs 2t3e5 £e \Leerss es e°3s 23 ‘Spectrum of Feriginal signal ‘These frequencies. ‘are aliased xO spectrums: ‘Overlapping Q.15:1 Effects of undersampling or aliasing OP reac Pum carn doen at br enaDigital Signal Processing Introduction to Digital Signal Processing Ans. : Here W = 10 KHz i) Range of sampling frequencies : F, > 2W F, > 2x 10KHz ie, 20 kHz ii) Folding frequency Here & KHz is less than Nyquist rate of 20 kHz. Folding frequency is the aliased frequency. It is given as, FAW +8 kHz +10 Kz = 18 kz and —2 ke — BW =~ 8 kz + 10 kHz =~ 18 kHz and 2 Kz Here folding frequency is 2 kHz. Thus the higher frequency of 10 kHz appears as low frequency of £2 KHz after sampling, Sampling of F, = 5 kHz Et, 8 kHz +5 kHz = 13 kHz and 3 kHz ~ E+, =~ 8 kHz +5 KHz = — 13 kHz and ~ 3 kHz ‘Thus F, = 5 kHz appears as 3 KHz after sampling. Sampling of F, = 9 kHz +P, 38 KHz+9 kHz = 17kHz and -1 KHz — Et fy 9-8 ki #9 kilz =— 17 kHz and 1 kHz ‘Thus F) = 9 KHz appears as 1 kHz after sampling. Q.17 How signals are classified ? Give examples of each. [ITU : May-12, Marks 10] Ans. : The Continous Time (CT) and Discrete Time (DT) signals are classified as follows = i) Periodic and non-periodic signals. fi) Even and odd signals. iii) Energy and power signals. iv) Deterministic and random signals. “CT and DT signals : A CT signal is defined continuously with respect to time. A DT signal is defined only at specific or regular time instants. Examples : et! is CT signal and e#'%s is its DT version. Periodic and Non-Periodic Signals : A signal is said to be periodic if it repeats at regular intervals. Non-periodic signals do not repeat at regular intervals Examples : cos @rft) or cos (2nfi) are periodic signals but e* or e~® ls are non periodic signals. Condition for periodicity : A CT signal x(t) is periodic if x(t) = x(¢+Tp), here "Ty" is period. ‘A DI signal x(n) is periodic if its frequency is rational, or it can be expressed as ratio of two integers. ie. Brequeny fy ~ 4 and an ioe Here 'N' is period of DT signal Condition for periodicity of x,(0)+ x3 (1) oF x, (a) and Xp(n) ; Let Ty and T; be the periods of x, (1) and x2(t) respectively. Then x4(1}+x9(t) is periodic if, Ton ana ‘mt are FE 7 F Ee tational, Here 'n’ and ‘mare integers. The fundamental period is LCM of T, and Ty. Let Ny and Nz be the periods of xy(11) and x9(n) respectively. Then 1, (1)+19(n) is periodic if, rational, Here ‘n’ and ‘nt’ are integers. ‘The fundamental period is LCM of N, and N,. Even and Odd Signals : A signal is said to be even symmetric signal if inversion of time axis does not change the amplitude. i., x(t) = (-1) and x(n) = x(-1) ~ (QI71) A signal is said to be odd signal if inversion of time axis also inverts amplitude of the signal ie, + (Q17.2) Examples : Cosine wave is ‘even’ and sine wave is ‘odd! x ()=—x © t) and x (n) =— x Cn) Even and odd parts of the signal x (8) or x (n) are given as follows = xel8) = Pet) 4xC] oF x(n) 1 + Fees] and x5(0= Ete(}-aN] 0 xl OP reac Pum carn dopa br ene1 Signal Processing 18 Introduction to Digital Signal Processing Deterministic and Random Signals : A deterministic signal can be completely represented by mathematical equation at any time. Example : Exponential pulse, triangular wave, square pulse etc, A signal which cannot be represented by any mathematical equation is called random signal. Example : Noise generated in electronic components, transmission channels, cables ete, «Energy signal and Power signal : A signal is said to be an energy signal if its normalized energy is nonzero and finite. ie, 0 y(n)=x(n)~x(n-1) shift variant system — y(n)= x(n)cos (sn) Q.23 Define linearity property of the system. ‘Ans. : A system is said to be Tinear if it satisfies the superposition principle. Let x4(n) and x,(n) be the two input sequences. Then the system is said to be linear if and only if. T haya y(a)+ yx9 (1) = ayT Hey (n)]+a,T x90) Examples (un?) inear system — y(n) Nonlinear system —9 y(n) = x?(nt) Q.24 Define causality property. Ans.:A system is said to be causal if its output depends upon past and present input only. A system is said to be non-cnusal if its output depends upon future inputs also, Non-causal systems are physically non-realizable. Examples : Causal systems —> y(n) = x(n)+x(n~1) Non-causal systems > y(n) = x(2n) 25 Define stability of the system. ES [Dec.-17, Marks 2] ‘Ans.: When the energy bounded input produces a bounded output, then the system is called bounded input bounded output (BIBO) stable. Examples : Stable system — y(n) = x2(n) Usable system ry ta)= ox yd wx Q.26 What is an LTI system ? C3 [INTU : May-t7, Marks 2] ‘Ans.: When the system satisfies linearity and shift invariance properties simultaneously, it is called linear shift or time invariant (LTT or LSI) system. *Such systems are physically realizable and practically used systems mes Examples : y(n) = Y5x(k) is LTT or EST system, * Linear convolution operation is applicable for LTT systems. ie, yi = Sx@hn-ky ie 27 State causality and stability criteria of LTI systems. ‘Ans. : Causality : LTI system is causal if and only if, h(n) = 0 for n <0, This means impulse response of causal LTI system must be causal. Stability : LTT system is stable if and only if its impulse response is absolutely integral. ie, Siw] << with this condition, every bounded input produces bounded output. 0.28 State the relationship for LTI system. mut and output of OR State formula for linear convalution. SP recrnrca punticariows”. an up tst br hoonDigital Signal Processing 12 Introduction to Digital Signal Processing ‘Ans. : The linear convolution sum is given as, Putting this value of x(n) is equation (Q.33.1), yey = Sxeyn(n- y(n) = 1, Ssose-n] Here h(x) is the impulse response of the system. Since the system is linear and time invariant, Q.29 State important properties of linear, (a - convolution. u ‘Ans. : Commutative property, x(n) it(a) = h(n)ex(a) Associative property, Lex (ap y(n) (n) = (nf g(n)* gD] Distributive property, x(a igo) rg od] = Cay (n)+x (a) eg) Part B ‘ong Answered Questions Q.30 Define linearity, and causality of the systems. 8 [BNTU : May-11, Dec.-11, Marks 10] Ans. : Refer Q21 to Q.25. fime invariance, stability Q.31 State and prove basic properties of discrete time systems. 1S [NTU = Dee.-14, Marks 10) Ans. : Refer Q21 to Q25. Q.32 How the systems are classified. Ans. : Refer Q21 to Q25. Q.33 Derive the expression for the output response of an LTI system whose input sequence is x(n) and impulse function of the system is h(n). [& [NTU = May-12, Marks 10) OR Write a note on time domain input - output relationship of LTI system. 1S NTU : Dec-13, Marks 8] Ans.:For an input x(n} output of the system is given as, y(n) = Teo) 2(Q38) Here x(n) can be expressed in terms of weighted impulses. ie, x(n) = Fx )8(n-k) Here x(k) is the value of input. Since the system is linear, Since the system is shift invariant and T[&(1)] = h(n) ven = Benen we This is the relation that integrates input and output of LTI system. Q.34 Derive the necessary and sufficient condition for BIBO stability of LTI system. 03 [NTU = May-11, Marks 10] ‘Ans. : The linear convolution is given as, yin = FE nares k Taking the absolute value of both the sides, wo =| 3 nayxe-w) won| + (341) IF the input sequence x(n) is bounded, then there exists a finite number M,, such that k(n) k or k 1. This means n(n) = 0 for <0, Hence this system is causal. Stability : Consider SJi(ky= S2kwek-1) Since impulse response is not absolutely summable, this system is unstable. 240 Test the following causality and stability. (a) = sin 2fn/F)x(n) systems for linearity, ESP [NTU : May-16, Marks 5] Ans. : Linearity : Since input is multiplied by value of sine function. In other words input is multiplied by time dependent constant, Hence this system is linear. # Time invariance : Since the input is multiplied by sinusoidal function, which is function of time factor “if this system is time variant. Causality : This is causal system since output depends upon present input only. SP recrnca punticariows”. an up tst br hoonDigital Signal Processing 1-6 Introduction to Digital Signal Processing * Stability : Value of ‘sine’ function is less then or equal to 1. Hence output is bounded as long as input is bounded. Hence this system is stable. Q.41 Check for linearity and causality. () y(n) = Snx%n), (ii) yin) = eMx(n +3). ES [IWTU = June-14, Marks 8] Ans. : (i) y(n) = 51x? (a) * Linearity : Since output is proportional to square of input, this system is nonlinear. Squaring operation is nonlinear. * Causality : Since n” output depends upon 1! input, this system is causal (i) y (a) = e-Px(n+ 3) Linearity : Here e“" is some fixed number. It multiplies the input x(n+3) Hence output is linear function of input. Hence this system is linear. * Causality : Since output at i!" moment depends upon input at (+3)"" moment, ie. future input, this system is noncausal Q.42 Verify whether the following systems are inear, time invariant and causal or nat. i) y(n) =anx(n) ii) y(n) = ax(n- 1) +bx(n—2) ES May-11, Marks 8] Ans. +i) y()=anx(a) Linear : Since output is linear function of input. * Time variant : Since output is a function of time factor. * Causal : Since output depends upon present input only. i) y(n)= ax (n—1)+b x (n-2) «* Linear : Since output is linear function of input, Time invariant = Since output is independent of time factor’. © Causal : Since output depends upon (1—1)" and (1-2)! input samples. 14 Linear Constant Coefficient Difference Equations Important Points to Remember ‘+ The solution to the homogeneous difference equation is given as, x Vn) = Seat a Characteristic equation for homogeneous difference equation is given as, x Sark = 0 os * Forced response is the sum of natural response and particular solution. For various types of inputs particular solution is given as follows = St.No| Input, xy | Particular solution y(n) 1 1 | k 2 e | ka" 3__| cos(@uro) | hy cos(an)+kp sin(aun) 2 | eeostanr 9) | aM hycos(ay+ ksin(tan) 5 » | ft hymn é a? | Ty thywt Pht hyn 7 na” I "(hg + ky) a wPa® [at lky tht kit tkynPl Table 1.44 Part A : Short Answered Questions Q.43 What is forced and natural response ? Ans.: (i) Natural response (Zero input response) : The natural response is the output of the system with zero input. This response is obiained only with initial conditions. It is denoted by y") (n. Gi) Forced response (Zero state response) : The forced response is the output of the system for given input and zero initial conditions. Thus forced response is obtained only with given input. It is denoted by y(n) 0.44 How discrete time systems are represented by linear constant coeificient difference equations ? Ans.: Discrete time systems are represented by generalized constant coefficient difference equations, OP reac Pum carn doen at br enaDigital Signal Processing 1-16 Introduction to Digital Signal Processing y, au 1 vin=- Sapyin-ky+ Y bex(n-k) (QA) “4 +64 J = (0453) Pa] 120 Here ‘N’ represents the order of the difference | Te determine values of q and ¢ : equation and hence order of the system. With 1=0 in above equation, : : 1 Part B : Long Answered Questions yO) = 4 +(3) Q.45 A DT system is represented the followi ten sys ep by ing yO @) = ey Hey (043.4) v(n)=$ v(a-1)-5 v(n-2)+x(a) With n=1in equation (2.453), with initial conditions May = q+ 5. ae YOM) = tter ~ (2455) v(2) and x(o)=(4} woop Determine (i) Zero input response (il) Zero state response (ill) Total response of the system. Ans. : The given system equation can be written as, yon yorney y(n-2) = x(n) w= (Q.45.1) (i) To obtain zero input response(natural response) To oblain characteristic equation : With input zero difference equation will be yOo)-} yor) +} (4-2) 0 = (Q452) Here N=2, hence characteristic equation will be, 2 7 ag +a, rt, =0 Natural response : Natural response is given as, yO) = arta - ertea(s With n=0 in equation (Q.45.2), y(O)-} y(-D+3 y-2)-0 y)-3x04}(2)=0 = y(0)=1 With =1in equation (452), y-3 yo)+4 yn =0 1 3 yQ)-px145 x0-0 syed Here y")(0)=y(0) and yl(Q)=v(1)=3. Hence equation (45.4) and equation (245.5) become, tg od 1 3 atte =F Solving above equations we get, 7 2 and c= Hence equation (Q.45.3) becomes, y= 2-(3) = (Q.45.6) This is the required zero input response. Gi) To determine zero state response (forced response) = Patticalar solution : Input is, x-(3) (si). Hence particular solution will be of the form of OP reac Pum caren doops br eneDigital Signal Processing peed Introduction to Digital Signal Processing yO) = (ay a(n) = (Q457) Putting this value of y(P)(n) in system equation of equation (Q.45.1) and input x(n) {Geo bG) eon eb “(Jue For 22 above equation can be written as, Wagrad~ Bn 1/2 fea la [Biel 2 u(n=2) Hence equation (2457) becomes, yO = 3G) u(x) Forced response : gAexy = YmyeyP en) Patting for yf2(x) from equation (245.3) and y(n above, 1y' aay" ey = ae(3) +3(9) Values of constants cy and cy : With 1=0 in equation (Q45.1), VO)-3 v4 -2)= xO) ++ (458) For zero state response, initial conditions are zero, Hence y(-1) = y(-2) = 0. And, x(0) = ay =1 yO) = 1 With n=1 in equation (9.45.1), V)-3 ¥O)+3 H-D= Here y(-1)=0, y(Q)=1 and x(I)= 5. Hence, 3 aatygel y(l)- 5x14 5X0 =F 7 wa-F With n=0 and 1 in equation (Q.458), s0= (8) (3) . 1 ete te 3 ad = 20S edd Here y= y(o)=1 and yO C)=yy=2. wi Fegttaed = atbant Solving above two equations, «<8 and 3 Q=2 Hence forced response of equation (0.458) becomes, 8 iy aifay y(n = 5-2(3) 4G) Giii) Total response of the system : Total response of the system is equal to sum of natural response of equation (Q.456) and forced response of above equation. ie, tet) = yo (ny ey (ny Fo AG) MTA This is the total response of the system. OP reac Puma dopa br eweDigital Signal Processing 1-18 Introduction to Digital Signal Processing Q.46 Determine the step response of the difference equation, 1 v(m) 5 9(n-2)= v(-2)=0 ‘Ans. :Step 1: Roots of characteristic equation (m-1) with y(-1)=1 0 and ‘The given system equation is yan y(n-2)= x(0-1) = (Q46.1) Since we have to oblain step response, the input is, x(n) = u(x) To obtain characteristic equation make inputs equal to zero in equation Q.46.1), then we get, = (0462) Yon)=Fy(n-2)=0 = (Q.463) Here N =2, henee characteristic equation becomes, 2 Ya rt =0 ie ag P+ art ay 90 From equation (Q463), ay =1, ay =0 and a =~ §, hence above equation becomes, P-leo9 = 4 570 + 1 + Roots: = Ze n= Step 2 : Form of a natural response Natural response is given as, oy yoy = Sat a site nf for N=2 Putting n and n in above equation, VQ) = (3) (2.464) nee ant +a(-3) Step 3: Form of a particular solution Here x(1)= u(r) Hence from Table 1.41, particular solution has the form of y) (x) = ku(n) the = (0.465) Step 4 : Value of k In y(A(n) Putting y(2(0). in system equation of equation (Q46.1) and inputs, 1 5 (01-2) = u(r-1) For 22 all the terms in above equation will be present. Hence we will obtain value of ‘ for > 2. ku (ny 21 for 22 9 Brg Hence particular solution of equation (0.46.5) becomes, Mu) = 2 (ny = (0.46.6) Forced response of the system is equal to sum of natural response and particular solution. ie., yD (ny = yl (np vl (ny Putting values in above equation from equation (0.464) and equation (2464), Wm = 4 (+e (-3)+ 2 ‘Step 5 : Values of c,and ¢2 with Initial conditions (046.6) With ne yO)-3 ¥ (-2) = x(-) in system equation of equation (0.46), Since x(n) = u(n), x(-1)=0 and y(-2)=0. ¥@)= 0 w (Q.46.7) With n=1 in system equation of equation (0.46.1), ¥@- 57-1) - 20 Here x(0)=1 and y(-1)=1 hence we get, yO- Fen =1 yl) = 7 w=» (Q46.8) Putting 1=0 in equation (Q.46.6), : 90) +4 ('J +6 9 = tye? atats OP reac rum caren fon at br eneDigital Signal Processing 19 Introduction to Digital Signal Processing This value of y(/(0) must be equal to y(0)=0 of equation (0.467). Hence above equation becomes, = (0469) 9 9 atate-0 > aten-2 Similarly putting n=1 in equation (0.46.6), 1) 1,9 Ya = a3) +0(-3) +3 =lea-le+2 gan gets This value of y() (1) must be equal to y(1) equation (Q.46.8). Then above equation becomes, 1,49 _ 10 3 = BR > a-a=-% ~ (46.10) g2*g 9 On solving above equation and equation (2.46.9) for cy and ey we get, 7 ac -a Putting these values in equation (Q46.6), (Noy - -2 (2) (1742 wo 12 (3, 4 3, +3 This is the complete response of the system. It includes natural response as well as forced response (particular solution). Here we considered initial conditions as well as input, Hence step response of the system is, oA BCI 1L5 Frequency Domain Representation of Discrete Time Signals and Systems Important Points to Remember * Fourier transform is used to study frequency response behaviour of DT systems. © System function gives frequency response of DT system. na = ¥O ie. Xo Part A: Short Answered Questions Q.47 Define the frequency response of a discrete time system. (5 [NTU = May-17, Marks 3] ‘Ans. : The frequency response of discrete time system is given as, H(w) = Here |H(o)| = {ao +1: (OF? < magnitude Hi{a) sre 2) = Jee Q.48 Show that the frequency response of a discrete system is a periodic function of frequency. 7 [INTU : May-16, Marks 3] ‘Ans. : Frequency response of a discrete time system is given as, y = H(o) > oo Dryer Since eH = coswk-jsinwk, H(o) = YkGycosak-jsinwk] ‘ = $ nwawor-7 Suepsinar : Here note that coswk and sinok are periodic functions of frequency or harmonics. Thus frequency response is periodic function of frequency. Q.49 Define Fourier transform and inverse Fourier transform. ‘Ans. : Fourier transform is given as, Fame X() And inverse Fourier transform is given as xt) = ZL Fxcareio nao Fourier transform is convergent if S|x(n)| <=. SP recrnca punticariows”. an up tt br hoonDigital Signal Processing 1-20 Introduction to Digital Signal Processing Q.50 Determine fourier transform of x(n)" 1 for 120 x) = au for -1 @ “as 70 elsewhere Ans. : Let us check whether the fourier transform is convergent. ie, Z_ kel - = ta" By geometric series and lal<1 X(a) = x(n) co = Fat com a - 3 (er) Hore fe°/9|=Hal<1, hence we can apply geometric summation formula. —1_ Traci X(w) = (Q.502) This is the required fourier transform. Q.51 Determine fourier transform of the unit sample x (n) = 3 (n) ‘Ans. : The unit sample is defined as, 1 for x(n) n=0 0 for #0 By definition of fourier transform, x= Fawetrend =1 forallo -» QSL) ‘Thus fourier transform has a value of 1 for all values of a Part B : Long Answered Questions Q.52 Determine the fourier transform of unit step quence, x(n) =u (n). ‘Ans. : The unit step sequence is defined as, By definition of fourier transform x)= SF xonei = F ren “Zev Here let us use the relation, . no Ne aN aioe 3, a ~- (Q521) Hence X (1) becomes, NYP be vg OPO -— = (Q52.2) rer This relation not convergent for @=0. This is because x(n) is not absolutely summable sequence, However X(o) can be evaluated for other values of a Let us rearrange equation (Q.52.2) as, 1 X() = Sen pent eR RT . 1 RP [oP] By culer’s identity we can write, 1 x(o) = —_1__ 2) sin 2 ciel o20 (523) 2jsin 5 53 Explain briefly the frequency response of LT! system. GF [UNTU = Novi-13, Marks 5] Ans. The discrete time system is represented by the difference equation as follows : w aM y(n) = —Dagy(n-b+ Yoyx(n-b =I © FF recrnuca PUSLICATIONS™ An up nat br kengeDigital Signal Processing Introduction to Digital Signal Processing M a y(n) + Sasny- Db Ky ‘Taking Fourier transform of both sides, x M Y(o) + Lae) = Vbew/*X(W) ms n * Y(w) [» Bacrt|- [3° mus a r= Above equation is called system function of DT system. It gives the frequency response also. H(a) = Ag (o)+ JH, (0) Here Hg(«) and H,(o) are real and imaginary parts of H(o) Hence magnitude and phase response of system funetion are given as, [HE] > VAR? HA? af Ho) 210) = tan Fy Q.54 Write short notes on time and frequency domain input - output relationship of an LTI system. ‘Ans. : Time domain input output relationships of LTI system are given in terms of linear convolution and linear constant coefficient difference equation. ie, von) = Shekyx(n-ky _(Q.541) ite x u and (n) = -Sagyu-Ky+ Sb, iat co (Q.542) In frequency domain represented as, Hw) = Sheer these relationships are or (a) = 2: Fnwyeret yy = SyeeHxt0) & And from equation (Q.582) we can write, Y(o) = Bae Fy (aye Syyer*(W) mo aM Loer’x(@) x or Moy = YO HO 14 Saye a 55 An LT system is characterized by its Impulse response h (n) = (y= (a). Determine the spectrum and energy density spectrum of the ‘output signal, when the system is excited by the signal x(n) = (ay n(n). EPP NTU : Deewt3, Marks 8) Ans. : Here h(n) = (J Spectrum ofthe output signal seven as, Yo) = H(o)X(o)= Energy density spectrum is given as, Sy (0) = |¥(@)P =| Hof [XP OP reac Pumaren toon at br ene1 Signal Processing Introduction to Digital Signal Processing 1.6 Applications of z - transforms Triportant Points to Remember '* z- transform is given as, x@ = Sxeme" IROC is the region where z - transform converges. y J+ System function, Ha) = 5 \* The system is causal if ROC of its system function! is exterior of circle of radius r< oe ls The system is stable if ROC of its system function| includes unit circle. Part A: Short Answered Questions Q.56 List the applications of z - transform. ‘Ans. : 2 - transform is used for the analysis of i) Pole - zero plots. fi) System function of the LTI system. iii) Causality and stability of LTT systems iv) ROC of the discrete time sequences. v) Step response of discrete time systems. vi) Frequency response of discrete time systems. vii) Solution of difference equations. viii)Filter design and realization. Q.57 Give the relation between DTFT and 2 - transform. USP [INTU : May-16, Marks 2] Ans. : Fourier transform (DTFT) of the discrete time sequence is basically its z - transform evaluated on the unit circle in z - domain, Thus, X(@) = XO) jo Here |z[= 1 ie. unit circle. ‘Thus Fourier transform is the special case of 2 transform, Q.58 Define z - significance ? transform and ROC. What is Ans. : 2 - transform is given as, x= Faeme" ROC : Region of convergence (ROC) is the region where 2 - transform converges Significance of ROC : i) ROC gives an idea about values of 2 for which z-transform can be calculated. fi) ROC can be used to determine causality of the system. fii) ROC can be used to determine stability of the system. Q.59 State important z - transform pairs. An 1 Bn) 251; al u(n) 25 , Taz’ zl lal s(n) 2s lal na n(n) 2 j= atu(enat) E> Gaaty?’ Q60 State four important properties of z-transform. Ans. Property 1: The ROC for a finite duration sequence includes entire z-plane, except 2=0, andjor 21 = == Property 2 :ROC does not contain any poles. Property 3 :ROC of causal sequence (right hand sided sequence) is of the form IzI>r. Property 4 :ROC of left sided sequence is of the form leler Q61 Define system function of an LT system. ‘Ans. : We know that y(n) = x(u)#h(2) Taking z-transform of above equation, Y(2) = X@)H@) “ HQ) called system function of DT LTT system. FF recemuca PURLICATIONS™ An up nat br kengeDigital Signal Processing 1 23 Introduction to Digital Signal Processing Part B : Long Answered Questions Q.62 Obtain the z - transform of u (n) and 8 (n). Ans. : 2 - transform of (st): Says" xe = Sone" = maze 2 = transform of u(n) : X@= Sape"= Sra" wise ms since u (a) =1 for n>0 x@ ‘Thus the ROC is outside the unit circle. Q.63 Obtain the z - transforms of (i) a*u(n) and -ata(-n ~1). Ans. : z-transform of a" u(n) By definition of z-transform, X(e) Seren 10 = Serugne™ = since 6) = 1 for n= 010 = Byoe-" & = 14 (az) 4(az4)? 4(az)3 4(a2tyt 4 1 maz laze 1 or Izl>tal z-transform of —a u(-1—1) afr" rns) ye sonar 8 AEH ten for n=-1to- xe) =F xe" = Yat 1 = -bX@)=- Sata! «Fats! a {ort 9s (ots? s(t 9 a(et gt} oot fiee tan erty? sertay aertgt en} = ~(@72) elat2t<1 1 1 Ta la!zle 1 or tal < lal Q.64 Determine inverse ztransform of 1 Xe) = has ROC : |z|> 1 Ans. Stop 1: Converting X(2) to positive powers of z, 2 (2+ 1)(2-1P XG) = Step 2: Here there is multiple pole at 2 = Therefore the partial fraction expansion will be, Xe) AL An As 2” aI GN * Gaye X(@) z X(2) 7 a= dew Me a4 (2 _@en2z-2?| 3 ela} ea iF Putting values in equation (Q.64.1), - 1p 27 Rt eT Gap o> (Q64.1) OP reac Pum caren toon at br eneDigital Signal Processing Introduction to Digital Signal Processing Be ee Step 3: X(2) = 21-1 Go? Step 4: relations : ROC is IzI> 1. Let us use following pac) 2 , ROC: lzl>Ip,! Py? Hence inverse z-transform of first two terms of X(z) will be, ya 4 1-2 12 y" u(u) and ZT Py? apt wn ROC: lal>lp,| 2 | = Prey" win) Putting all the sequences together, X40) = FD" Ueops FM way eg AO)" (nd ft “al Q.65 Hf x(n) is a causal sequence, z- transform of the following sequences. () x(a) = nu (n), (i) x(n) = nu (n- 1). CE [aT May-17, Marks 5] or sdebafata find the Ans. = (i) x(n) = nu (a): 1 We know that 1(1i) <> The differentiation in z- domain states, nx(n) 2 nun) 29 8 mun) x(n) = Above equation can be rearranged as, x(n) = (n-141)u(n-1) u(n—y): = (n=) (n= 1) + 4(n=1) We know that 1r(n) > Iz By time shifting u(n-1) <=> 4 And n(n) <> (2-1-1) > ae s X(z) = (n-1u(n—1)+ u(n—1) Q66 Define causality and stability in terms of z- transform. ‘Ans. : Causality : The condition for LTT system to be causal is given as, h(n = 0 <0 Here ii(n) is the unit sample response of the LTI system, When the sequence is causal, its ROC is the exterior of the circle. Hence, LTT system: i causal if and only if the ROC of the| system function is exterior of a circle of radius rom. Stability A necessary and sufficient condition for the system to be BIBO stable is given as, S fron < & (66.1) We know that the system function is given as, nea =F aenet Taking magnitudes of both the sides OPE reac Pum cari doops br eneDigital Signal Processing Introduction to Digital Signal Processing Hey -| 3 aoe Magnitude of overall sum is less than the sum of magnitudes of individual terms. ie., Hels 3 pone 2 Hel< 3 be If H(2) is evaluated on the unit circle, 1=1 Hence above equation becomes, HEL < x pny then, If the system is BIBO stable, then J) fir(n)| s H@ 1-042 1-02 Taking inverse z - transform of H(z) gives impulse response, fa) = 0.4)" u(n)—(0.2)" u(n) (i) Step response Step response of the system can be oblained from impulse response as, yin) Fok - Fea, P= = since u(k) = 0 for k< 0. x Here use Sak oo ‘The above equation will be, oanttaa _ (02"1-1 os = 1.67 [0.4 (0.4) -1]+1.25[0.2"(02)-1] yeu) = = = 0.668 (0.4) 41.67 40.2502)" -1.25 [-0.668 (0.4)" +0.25(02)" +042] u(n) Q71 A digital system is characterized by the following difference equation. y(n) = x(n) + ay (n~ 1). Assuming that the system is relaxed Initially, determine its impulse response. CGP INTY : May-16, Marks 5] Ans.: The system is initially relaxed. Taking unilateral 2 - transform of given difference equation, ¥(2) = X()+az“¥(e) 2¥(2)ll-az!] = Xe) Ye s He) = x Toking inverse z - transform, h(n) = a"u(n) 1.7 Realization of Digital Filters Important Points to Remember '* When number of delays in the structure are equal to order of difference equation, then it is called canonic form realization. '* Cascade and parallel combination of structures reduce quantization effects in digital filters. Part A : Short Answered Questions 72 What realization. Ans.z# The structures can be of two types. IF the number of delays in the structure is equal to order of the difference equation or order of the transfer function, then it is called Canonic form realization. do you mean by canonie form “lf the number of delays in the structure are not same as order, then it is called non-canonic realization, Q73 State advantages of direct form - Il structure. ‘Ans. : i) It is canonical form. fi) Delay units requirement is reduced, iii) Overflow can occur at delay PF recenuca PuaLicariOws™ An up nat br keeege1 Signal Processing Introduction to Digital Signal Processing Part B : Long Answered Questions Q.74 What are the various building blocks required in realization of digital systems ? ES [INTU : June-14, Marks 8] Ans. : Following. table lists out various building blocks required for realization of digital systems Fig, Q75.1 shows the direct form - I structure and Fig, Q75.2 shows the direct form - II structure. x0) to) 1) J+ v0 =xi0-1p0r 4 Delay elements |" }—$-n09 =o) Time advance }— een Jen = seg St. No.| Name of the Symbol block a 1 adie — | oy 0 ° 2 Consort | yg 2 oye el mentor 3 ‘Signal multiplier| Fig. Q.75.1 : Direct form - 1 * Note that the direct form - II structure is obtained by cascade of two structures in direct form - L The delay units are combined while cascading. * Direct form - | is obtained by cascade of all zero structure followed by all pole structure. All zero system is derived from numerator of equation (Q75.1) and all pole system is derived from denominator of equation (Q.75:1). Table Q.74.1 Summary of elementary blocks used to represent discrete time systems Q75 Discuss the direct form - I and I MR filter realization structures in detail with necessary flow graphs. 0 [ONTU : Dec.-13, Marks 7] Ans. : Consider the system functions of discrete time system. u She ° x 14 Saye a alot tebe Pedy 751) x(0) yn) Fig, @.75.2 : Direct form - FF recemuca PuaLicAriONS™ An up nat br kengeDigi 1-28 Introduction to Digital Signal Processing 1 Signal Processing Q.76 Compare direct form - I and direct form - Il structures with respect to hardware requirements. (& [INTU = June-13, Marks 5] Ans.: Sr. No. Direct form ~ II structure 2 | Itcan be regarded as a all - zero filer section followed in series by a all pole filter section. It can be regarded as a all - pole filer section followed by a zero filter section. 3. | There are twice as many delays as are necessary. As a__| It is canonical with respect to delay. result, the DF-I structure is not canonical with respect to | This happens because delay elements associated with delay. all-pole and all-zero sections are shared, 4, | In most fixed-point arithmetic shcemes, there is no possibility of intemal filter aver flaw. In fixed-point arithmetic, over flow can occur at the delay-line input 5.__| tt requires 2N delay units. It requires N delay units Q.77 Obtain the parallel and cascade realization structures for the system function given by (ri tfa+ Ans. : Cascade realisation He = 0 [NTU + June-13, Marks 10] To obtain cascade realisation, the transfer function *() is broken into product of two functions as, H@) = H,@)= H@) where Hy() = H,@) = = 7 ede she? tye ty The cascade realisation structure for this system Fig. .77.4 function is shown in Fig, Q.771 : FF recemuca PuaLiCATiONS™ An up tat br kengeDigital Signal Processing Parallel realisation Introduction to Digital Signal Processing To obtain the parallelisation, we are suppose to perform partial expansion of H(2), resulting in 1a uel = os 2 (ie )(detsh?) Oo -_A Betec * = , (es) EE 2 3 Multiplying out and equating the coefficient of negative powers of z, we get A-1 B and C= a 2 ale The parallel realisation is as shown below Fig. Q.772. Q.78 Realize the given system in parallel form He) = (141/224) /- zt +1 4-28 1/227 Ans. : Let us convert the given system function to its equivalent partial fractions : {ky +hz) +(-Ko +ky ky +h3)21 +(0.5ky Ky 40.25k, —ky)2? +(0.5k, +0.25k5)2 9) (27 s022)(@-27 son) Equating the numerators of equation (Q78.1) and (Q783), Kg tk, = 1 Hy thy ky thy 05 O5ky — ky +0.25k,—ky = 0 05k, +0.25k3 ~ 0 Solving the above system of linear equations, ky 75, ky =-15, ky =—4, ky = 3 Putting values in equation (Q782), Qo Fig. 77.2 Parallel realization -AQ78.1) --4Q78.2) (Q.783) OP reac rum caren dopa br ene41-30 Introduction to Digital Signal Processing Q9 In canonic structure, the number of delays will be equal to the of the system. TSP [INTU : Aug-16] Above two second order sections can be realized in parallel form as shown in Fig, 781 Q40 The convolution using convolution sum, formula is called ES [INTU + Aug.-16] Multiple Choice Questions for Mid Term Exam Q1 If x{n] and yfn] are input and output of a xn) system then the system is said to be time invariant if yuk] = (where yf, K] = Thfu-k) ISVUNTU : Feb.-17] Be] sted (5) yin (J vie-¥ (a) vm Q2 If the output of a discrete time system depends on the present and past input samples but not on future inputs samples Fig. 0.78.1 Parallel from realizati sree he sys, now. \g- 0.78.1 Parallel from realization syeom, Fill in the Blanks for Mid Term Exam [a] causat Hl Q.1 If the system is initially relaxed then the [e] rR iq response of the system is response. 57 [DNTU + Feb.-17] 3. An LTT system is said to be causal if and only is sai ‘i if its impulse response, h{n] is for Q.2 A system is said to be system, if i pons its output depends on present, past and future negative values of 'r PSPUNT ¢ Feb-17] values of input. 0&7 [ONTU + Feb.-17] flo Be Q3 Which type structure provides a direct fai [a] >0 relation between time domain and 2-domain equations ? SSINTU : Feb-17] 4 The process of conversion of continuous time 4 The fundamental period of a sinusoidal signal into discrete time signal is known as sequence, N = = SSP DINTU : Feb-17] FS Bim # Aig] QS The z - transform converts difference equation [a] atiasing [b] sampling into ‘equations. [e] convolution [G] none of the Q.6 The DTFT of a sequence is equal to its above 2 transform if the radius, r= | | i puro: Feb-a7) QS The system y(n) = sinjx(n)] is ‘ ESP NTU = Aug.-16] Q7 When A signal is defined continuously for any value of an independent variable, it is [a] Stable [E] BiBo stable called _____. 03> [UNTU = Aug.-16] [e] Unstable [a] None of the Q.8 Ina discrete time signal x(n), if x(n) = x(- n) above then it is called Q6 The ROC of the sequence x(n) = u(-n) is USP [UNTU + Aug-16] FF recenuca PuaLICArIONS™ An up nat Wr kenge1 Signal Processing iat Baad [gj -1 [Wy ]ty and xy = Wa Xn Here WE" = [Wy ]and [5] ‘+ For N= 8, [Ws] is given as, we wo wo we we wo wo we vo wl w2 we wi we we w? wo wi we we wi we we w? we we wi we wi wi? wy? wt we we we we we we wis w2t (sl =| we we we wae wae we wet wee We we wee wed we we we? wes we wie wi? wis wt we? wee wa Dow? wit wel wet wi wi wa? we w7 wit w2t we wS wi wa 0 Here Ws . 11 wi Bo jsint = 1-jt . aR OR Since Wy is periodic, Wy'*® = WP. Similarly Wy*® =W3 and so on. ‘The values in the above matrix are listed below owe wis -wt ew? ow we = wi =wj6 =w2! =w? = WyDigital Signal Processing 2-2 DFT and FFT 2 wi _wi8 —w25 ws wae fg = Wao = Wer =Wee = We" = We" 4 yy? 0 —w28 Ww = wt =.= We = Ww? =w20 =w28 = Ww = ws =.= 52 yl wt we? wo? ws we = w.? =w2! =w2? -w” 1 (H)82(0) A> FX (K)N Xo(K Ta Prov in=% EXON os 11. | Parseval’s theorem Matrix approach to the computation of circular convolution. Circular convolution, y (n) = I (n) Nx (n), n= 0, 1, NT This equation can be formulated in matrix form as follows : 3) QO) gh NV, gh (N-2) 2 HDope x(0) yd) AOL AOSPAW-y .. HOLS) x) ¥Q) hQ) Ad ACO - AA) *hG) (2) yev-2y h(N-2)} H(N-3) HWA)... ACO) vO-D) 4, | ROW 2 AA 3) #740) xD]. "Gicalar is are represen by tis mare Part - A : Short Answered Questions Q.1 List the properties of DFS. ENT : Dec-17, Marks 2] Ans.: 1. Linearity : a x(u)+b y(n) 22> 5a 6, +b ey) 2. Time shift: x(n, 27S e-P80/T0 c(h) 3. Frequency shift : e!2"40"/70 x(11)< 27S 5 c.(k—ko) 4. Sealing : x(an)2F> 5a e,(h) 5. Convolution : x(n) * ylnde 2S» Negtk)ecy(t) Q.2 Define discrete fourier series. SSE PINTU = May-17, Marks 2] SP eon romero mp at oaDigital Signal Processing 2-4 DFT and FFT Ans. : DES for x(n) is given as, x x(a) = Sel ei?nIN = The fourier series coefficients e(K) are given as, iy j2syp ct) = ay Dx ce Paks Q.3 Define periodic convolution. Ans. : Let xy(1) and x2(n) be two periodic sequences with fourier coefficients ¢(K) and ¢2(k) And let, ef) = e(k)-e2(K) If c(k) are fourier coefficients of x3(1} then nt x5() = Lxulnxa(n— a) no “Thus +5() is periodic convolution of x4(n) and x9(n) Multiplication of fourier coefficients is equivalent to convolution of the corresponding, sequences. Q.4 Define DFT and IDFT. Ans. : DFT of a sequence x(1t) is given as, na X0) = Sax(npePN, k= 0,1, ..N-1 cot and IDFT is given as, xin = Say e288, 20,4, N=A we m= 0,1, In the matrix form DFT and IDFT is given as, Xy 7 Wyle and Xn > lWy ly here yl yl Q.5 What is DIFT ? What is the difference between DTFT and DFS ? Ans. : DTFT is given as, XQ) = Saxe Here ‘O/is the frequency and its range is form 0 to 2n. SP recrncat PURLOATiONS" Ao up tt br kone1 Signal Processing 2-5 DFT and FFT DFS is fourier series expansion of periodic DT signal. + DTFS converts periodic or non periodic DT signal to frequency domain. Q.6 Compare DIFT and DFT. Ans. : ES [NTU : May-06, Marks 3] St. No. DIFT DFT L = Na Yeo Equation : X(K)= J) x(nperP* mo k=01,..N-1 2 | Here X(a) is continuous function of Hore X(k) is defined for k= 0,1, N= 1. 3. | DTFT cannot be evaluated on digital computer. | DFT can be evaluated on digital computer. 4. | DTFT is double sided DET is single sided 5. _| The sequence 2(u) need not be periodic. ‘The sequence x(1) is assumed to be periodic. Q7 Distinguish between linear convolution and circular convolution. Ans. : Following table illustrates the comparison. S&P INTY : May-16, Marks 3] Sr. No Linear convolution Circular convolution 1. | Sequences are non periodic and must be of finite length. | Sequences are of length N and may be periodic. 2 | Convolution sum is of length N+ M-= 1. Where ‘Nand | Convolution sum is of length ‘N' and lengths of 'M’ are lengths of two sequences sequences is also 'N. 3. | Sequences are shifted linearly Sequences are shifted circularly + 7 % y= Sx ikn-W) gen = Lx(aIK(or— Dy = =o n=0,1..N¢M=1 m=01,..N-1 Q.8 List the three important properties of DFT. Ans. Symmetry : X(N —k) = X*(k) Circular convolution : x, (0) x9 (n)< 2» X, (X94) N Multiplication of two DFTs is equivalent to circular convolution of their sequences in time domain, Time reversal :x((-r))x 79 (CH), Circular Hime shift :x(1-1)jy «PET XEVe PAHO Not 1 Parseval's relation = x(n)y"(ut)= LS kuru m0 0 Q9 Obiain the circular convolution of the sequence x(n) = {1, 2, 1} and h(a) = 1, 2, 2) UNTY + May-17, Marks 3] OP reac rum carn dep at br eneDigital Signal Processing 2-6 DFT and FFT Ans. : In matrix form circular convolution of x(n) and I(n) for N = 3 is given as x0) 3) x(1)] [hy xm @hon = |a(1) x0) 2@)}| 1 M2) (1) x(0)} | (2) 11 2ypry ps -k14 2 121 +1 Part - B : Long Answered Questions Q.10 Determine DFS representation of the signal x(n) = coo) Ans. Here on} Hence 2nf =F 1k , s f= }=H Hence period N= 6 And x(n) can be written as, am) _ eB ge el xin) = of Fe = Lem y) imps i +3 4Q.10.1) DFS is given as, x(n) Yetkyel2auy ee Yetkye"l6 Hore N tbo sand wor Let 1 =~ 1 and 1 in above equation, xin) = De! 3 +eqe> Comparing above equation with equation (Q.10.1), 1 «> 5 ofl) 4 and ef the DFT cools at 0 Q.11 I x(n) is a periodic sequence with a period N. also periodic with period 2N. X;(k) denotes the discrete Fourier series coefficient of x(n) with period N and X,(k) denote the discrete Fourier series coefficient of x(n) with period 2N. Determine Xo(k) in terms of X;(k). ES NTU : Dec-17, Marks 5] SP eon romain mp at aDigital Signal Processing 2-7 DFT and FFT Ans. : The DFS coefficients are given as, Net cy = wa. xppertmins «DES coefficients of x(n) with period 2N will be 1 RT j2mknf2N p(k) = R= ay 2 xtnyer Since x(n) = 2{#+N) above summation can be written as, X(K) = ak Late FPAMIN 5 x yy_r PAM NYI2N y yt oy Een ech) =o 1 z 2 > en Ease -3% (Fuses K=O,1, 2 creer 2N= 2 for even k rik = (oa ity = Here e (AD, Hence (1467) {c ‘or odd k x(3) for even k 2 XW) = 0 for odd k Q.12 State and prove the circular convolution property of DFT. SP [NTU = May-13, Marks 10] Ans. : Statement : Let x; (1) a X, (k) and x, (n) a Xz (k) Then x4 (n) QW) x3 (0) AEX (W.X2 () Hore x,(G3) #5 (a) Nipoin cular consolation of y(n) and x This property sats that multiplication of two DFTs is equivalent to circular convolution of their sequences in time domain. Proof : Consider the two DFTs Not XO) = Exe P?2N, k= 0,1... NA -(Q12.1) = Net Xe (K) = FE xy (DePMN, k=O... NA +-AQ.12.2) i Let X5 (FE) =X (&)-Xp (8) --- (Q123) SP eon romero mp at oaDigital Signal Processing 2-8 DFT and FFT Lot 1x (m be inverse DFT of X; (k). Hence, Not 2 Xs (kyeramiN les x3 (0) Xy R)-Xy (kyel2M/N From equation (Q.12.3) 2in qear 2 Putting for X, (k) and X, (k) from equation (Q.12:1) and (Q.12.2) Fee Patnt |S cs cper ea | atm op % wea [not ry Lae) Boo] E ePatennDIN w (Q124) & Not consider ak = Part Net oP Rm DYIN F el2ata-n-D/N kw 0 for Pm mn DIN gy = (Q125) Here note that when (nr-1-1) is multiple of 'N, then eF?*"="-N/N = 1. Now consider the second case in above equation, ePPR(m—M-D = 1, since mat is always integer. Hence second case in equation (Q.125) is always zer0. ie, N for(m-n—l)ismultipleof N Net j2eA(m— DIN a z° {o otherwise 0 Hence equation (Q.12.4) can be written as, pNot Not x30) = Dy 09 3 220-N for (mn is multiple of Nt Nol Not 2 x3(0) = Fx (0) Fx () and (m1) is multiple of N. (Q.126) mh When (mi-it-) is multiple of 'N,, itis written a5, ned = +p N, where p is some integer. ie. nee = pN or ment =p 1 meatpN FF anc a rEDigital Signal Processing 2-9 DFT and FFT Putting this value in equation (2.12.6) Net 3 (nt) = Sx, (ux, (m= n+ pN) = Here x3(n~11+ pN) represents x, (n) shifted circularly by ‘u' samples. It is written as x, ((m—))y.- Nat 2 x3 (0) = So x4(u) x4 ((m-m)y, m= 0,1, N n=0 1 Above equation is called circular convolution of x(n) and x, (n) ie. xy (n) = 4, QD) xn 09, m= 01, NT Q.13 State and prove circular time reversal property of DFT. Ans. : Statement : Lot x(n) <2» X(&) then, N a((-ay = 8 Om) PEs XQ(-ADy = XON=H) When the sequence is circularly folded (reversed), its DFT is also circularly folded. N-1 Proof : DFT fx(N-u)} = J) x(N=nye JN =o Let m= N-n Then when 0, m= N and when n=N-1, — nr=1. Hence above equation will be, 1 DET fx(N— mw) = x(mpe™/0(N-m/n nan Performing summation from N to 1 will be similar to that from 0 to N-1, since the sequence x(1) is circular. Net DET {x(N=m) = SY x(npen Pam. net = Yale Perak m0 net =F x(mpel2/™, singe e7P = 1 wo since ¢7/28™ =¢7/22"N/N = 1 for all 'm’, multiply RHS of above equation by e~?2™"N/N ie, Net DET tx (N— wh} =D) x(m) e?04MIN go i2xm NIN so Not x(n) e-PRMNDIN ‘0 SP eon romero mp at onDigital Signal Processing 2-10 DFT and FFT = X(N-&) Thus DET fx (N— mp) = XN =X(CE))y Q.14 State and prove circular time shift property of DFT. Ans. + Statement: tn) «2° x than (r= ye 2°» x ger PAM Shifting the sequence circularly by 7T samples is equivalent to multiplying its DFT by e-P=4/¥, Proof : DFT {x{(=I))y}= s x((-D)y PAY since the shift is circular, right hand side of above equation can be wtten 3s, Not tt DET fe(u=N)y) = SY x(n DePWN 4S x(N—L4n) PRIN (141) ad = Put n—1 = m in first summation. Hence, ue wet xtra ye PIN = ST x(n eo PReKme H/T -= (Q142) wt mad Put m = N-1 +n in second summation. Hence, ma Not Si x(a de nye PMN OS nye Patdns 1 NYIN 0 nt Net = OS agape itor ON nN --- (Q143) with the resulis of equation (Q.14.2) and above equation, we can write equation (Q.14.1) as, Nett DET (n= Dy) =D x(npe™ Patines DN Net +S xtnpe takes mint Net = S x(nper Pater nly 0 Net =F xlnperPatn er jaattyn =o X (ke PaHIN Thus the circular time shift property is proved. SP recrncas PURLOATIONS' Ao up tt br komtDigital Signal Processing 2-0 DFT and FFT Q.15 State and prove periodicity and linearity properties of DFT. Ans.: i) Periodicity : Let x(n) and X(k)be the DFT pair. ‘Then, if x(1+N) = x(n) for all m, then “ X(k+N) = X(K) | for alle = (Q151) Proof : By definition DFT is given as, Net xm) =F xonwe = (Q.15.2) 0 Replace k by k +N, then above equation becomes, wet nN XEN) =D xanwy r= 5. x(n) Wet Ww - (Q.153) 10 =o . Ne ct : we N =e PO" = 1 always Not X(K+N) = Y x(e Wy" =X (K)_ by equation (Q.15.2) =o ii) Linearity : The linearity property of DFT states that if x(n) PETS XR) and x,(n) DEL X4(R) then, 4 4 (1) 4 ay Xz (t) EES a, Xi(R)+ ay Xp(K) (15.4) Here a, and a, are constants. Nat xm) = DS xonwit So Let x(n) = a, x; (n)+a3 x, (n) then above equation becomes, Not XR) =D [a xy (+ ay xp ()] WE 1 Nat Zi arss (ow + 2% (WY = ay Sx (DWE +a Sng (wh =o = ay Xy(k)+ ay X5 (Kk) SP eon romero mp at oaDigital Signal Processing 2-2 DFT and FFT Q.46 Discuss the four properties of DFT. ESLINTY : May-16, Marks 5] Ans. : Refer Q.13 to Q5 above. Q.17 Compute the DFT of the given time domain sequence, x(n) = {1, 2.3.4, 4.3.2, 1) BSP[INTU : May-1, Marks 8] Ans. : DIT is given as, Xy 7 Wy] ay Tor N=8 Xp [Wa] x5, Putting the values of [Wg] and x ‘X(0) xq) (2) XG) XA) x(5) Xi6) XM), honors” 0172+ jars 0 5828+ 72414 Q.18 Compute the DFT of x(n) = {-1, 0, -1) with T = 0.5. Plot the DET sequence. suggest a method for improving frequency resolution. T&[INTU = Aug06, Marks 6] Not Nat Ans. : XR) = SE xpwyl =D anyer2bvN m0 Here x(n) = 11,0, -Iland N=3 2 = XE) = Saupe PS = pa a( tye PS 4x Qyer HOH 0 SP recrncat PUuLOATIGNS- Ao up tat br knitDigital Signal Processing 2-2 DFT and FFT = -140-1[ cos 8 - jin SE] - -1-cos 9H + jin s X@) = xq) = XQ) = ‘Thus X(k) = * Ix = ZX(k) = Q.19 Compute DFT for the given sequence x(n) = {1, 2, 3, 4}. (ES [INT : May-12, Marks 7] hoa Anas ei j fe S* shad a I" pj a fa} b+ va 0.20 Find the IDFT of the sequence X(K) = (2, 2 - ms 4,243). EEPLANTU Maye12, Marks 8] tid . ijt j a 3 2] “|. Ans.: xed tj j ai 1 OX, pl) = SKK) + X* (-K)IRN(k) EES LINTY : May-16, Marks 5] Ans.: i) 2* (25 X*(Ciy Ry (W) DFS coefficients of x(n), ST ayer Pam DFS [xu] = Fy Dame! sip =D Nat DES[x*] = 3p Dx*(pe Pearl oo 1 ix(u)er PAN Bap Not Y [ 4 Sener] - [i XEN) Ry) HY X* Wyy Ry (09 —> Ney (9 ~ FINCH) +X WIR We have x(a) = x(n) +xQ(n) and x) = Pex et 0] Dis fxm] = DES {Fixtmex“¢-n} = Fx0+ XC] Xe) — DFS [relo)] = FEX)* X41] Hence DFS, fr*(i)y Ry (oll = SC) EXCH Ry) SP recrncat PURLCATIONS"- Ao up tat br knDigital Signal Processing 2-16 DFT and FFT Q.26 Determine the fourier series representation for the following discrete time signals : i) x(n) = aio{ 3) sin 222) 19 sia) = { 1 for0 3sin( $) sic) sin A sin B = Leos(A-B-peos( A+B) sa) = Fo F-8 fo( fo FH o('2) min t= Se) 2 Here oy = Sasanp,=%= and oy =F s2np, = ‘Thus fundamental period will be N = 8 Then x(n) can be written as, 3 cost" 3 coef 3 x) = Sos 50 5") _alelese le | 3fe © 2] : 2 | DFS is given as, xn) = SretkyelIN = PL etkyei2ml® = LP etkyel2™4 with N= 8 whe a — with k = 1-1, 3,~3 in above equation, xd) = eye" a cy PU + (3) eF3™™M4 + (ayer HeH/4 Comparing above equation with equation (Q.26.1) we get following DFS coefficients, (1) = 1) = 3 and 3) = 3) =—3. Rest of coefficients are zero ii) DFS coefficients is given as, My 1a lz | Nat d= Dame ne “a S nen Pan Senet no 0 4 hi sy] PER = DF ne rae Cape OY LPS pees 7. ye PMY et SP recrncas PURLoATIONS" Ao up tat br knitsDigital Signal Processing DFT and FFT Here eI » cos(nk)- jsin(nk) = My x 1] % ~ pany fake, ,— jks) s tt) = hy] Ye P'S Cay ne PU | ne PsN = = > with N = 8 above equation will be, fk) = 0 fork =Oand2 2 fork =1and 3 Here 1-1 13, 2 eh) = 2 Suen PHY for k= : k) ay for k= 1 and 3 Q27 Compute the circular convolution of the sequences x(n) = (1, 2, 0, 1) and xan) = (2, 2, 1, 1) using DFT approach. SS [NTU : May-16, marks 5] Ans. : DFT of y(n) and x9(1) is given as, oad agyy Xy(k) > 1, a e a) = ale], 0 1j 1 yaa 4 bajaj x0) Wlee] oy lf Multiplication of X,(k) and X,(k) will be, 4 1-§||1. j XW) = XX) | | isslli+i] [2 Now calculate IDFT of X(k) 11 1 17p247 ps Liye aft j -i||-i2|_|7 er pe “lo 22 : Linear Convolution using DFT Important Points to Remember ‘+ Let the two sequences be of the length L and M. Then their linear convolution will be of length L + M -1 + Linear convolution can be obtained using circular convolution by making lengths of two sequences equal to L+M—1. «Necessary number of zeros are appended to increase the lengths of sequence. FP ara rari ar woreDigital Signal Processing 2-18 DFT and FFT Part A: Short Answered Questions Q.28 How linear convolution is implemented using circular convolution ? Ans. : Refer important points of section 22 Q.29 Find the linear convolution using circular convolution of following sequences : x(n) = (1, 2, 1}, ln) = (1, 2) Ans. : Here x(n) has length of 3 and in) has length of 2. Hence linear convolution of x(n) and (nt) will have 342-1=4 samples. Making lengths of x(n) and h(x) to be 4 by appending zeros. ie., x(n) = {1 2, 1, 0) and h(n (1, 2, 0, 0) Circular convolution of above sequences can also give linear convolution. yO}] fx) 2G) x@) aE] fhOy) pL Ox 27/1] ft y@)) _ }2) 2©) 2G) x2)}/ MD) _]2 1 0 2) _|4 y@)| 7 |x@) 20) x@) x@)}]2)]7]1 2 1 of fo]=}5 v@)} [x6 2@) 20 x] |r] lo 1 2 lo} [2 Thus x{(n)*h(n) = (1, 4, 5, 2) Part B : Long Answered Questions Q.30 Explain the computation of linear convolution using circular convolution. ‘Ans. : Let unit sample response of system be h (n) of length M and input be x (n) of length L. Then output of the system is given by linear convolution as, yoo = Sheyx(n-k b Here length of y (n) will be N= b+ M~1. # The Linear convolution can be calculated using circular convolution if we make lengths of h (n) and x (n) equal to N. This means we have to append L-1 zeros at the end of h (n) and M-1 zeros at the end of x (n). This is called zero padding. Thus, he Gu) = (e(Q),W(),.. (M=1), 0,0, 0) Mi samples Tot zm XG) = fe), x().-x(E-1),0,0,...0) Tastes Tere + The circular convolution of above two sequences will have the length N= E+ M — 1. This circular convolution will be same as linear convolution of original sequences. Q.31 How linear convolution is obtained using DFT and IDFT ? Ans. : In Q.30 we have seen that Tinear convolution is obtained using circular convolution if we use zero padding. ‘= After zero padding take DFT of x (n) and h (n). ie. DFT th (w} = HQ), k=0, 1... NA DET (x (n)} = XW, k= 0,1, ..... N- SP recrncat PuRLIOATIONS" Ao up tat br komtDigital Signal Processing 2-19 DFT and FFT Here N = L+M—1. And -L’ and M’ are lengths of x (1) and_h (n) respectively. + Multiplying the two DFTs of length 'N' we get, ¥ () ~ HEk)-X() + Taking IDFT of Y@) gives circular convolution of h (a) and x (n) of length N= L + M — 1. This circular convolution is equivalent to Tinear convolution. ie., y(n) = IDET IY GE = him N x(n) Q.32 An input sequence x(n) = {2, 1, 0, 1, 2} is applied to a DSP system having an impulse sequence A(n) = (5, 3, 2, 1} Determine the output sequence by i) Linear convolution. Verify same through circular convolution. Ans. : Given x(n) = {2, 1, 0, 1, 2) and h(n) = 15, 3,2, 1) ) Output sequence by linear convolution = Using multiplication method, output sequence is given below = yor) = x()* (ni) xn) 21012 Mn) 5 3 24 21012 42024x 6303 6xx 505 0x x x 179485 2 un) = {10, 11, 7, 9, 14, 8, 5, 2) if) To determine linear convolution through circular convolution : xt) = x4(m)= {2, 1, 0, 1, 2] > Ny =5 h(n) = x(n) = 15,3, 2, I] Ny =4 Therefore = N= Ny+Ny-1-5 44-168 Appending zeros to above sequences * x(n) = 12, 1, 0, 1, 2, 0, 0, 0} and x9(n) = {5, 3, 2, 1, 0, 0, 0, O} Using matrix approach, y(n) = x, (rN) x60) 000210 17/5] fo 1200021 0]|3} | lo 120002 4][2| |7 1012000 2//1] Jo wo) =|) 401200 aflo| fra fo 210120 a]|o| Js foo 21012 o]fo] 5 joo 02101 24 [0] [2 ” yn) = x3(1t)= 410, 11, 7, 9, 14, 8, 5, 2 FF ana naa roeDigital Signal Processing 2-20 DFT and FFT 2.3 : Computation of DFT using Overlap Add and Overlap Save Methods Important points to remember + Overlap save and overlap add methods are used for linear filtering. It is one of the important application of DFT. + Simple approach is provided by overlap save and overlap add methods. + These methods are computationally efficient due to FFT algorithms. Part - A: Short Answered Questions Q.33 State the principle involved in averlap-save and overlap-add methads. Ans. : The long duration sequence is split in short sequences. Necessary number of zeros are appended at the beginning or the end of these short sequences. = DFT of these segments are multiplied with DFTs of the impulse response. Then IDFT of the multiplication result gives filtered outputs due to short sequences. ‘+ Find result is then obtained by overlapping the sequences and adding or descending overlaps. Part - B : Long Answered Questions Q.34 Discuss the procedure of computing linear convolution using overlap-add method. eSpwi + Dec-13, Marks 5] Ans. : Overlap add method In this method the data blocks of length N= [+ M-1 are formed by taking ‘L’ samples from input sequence and padding M-1 zeros as shown below. x(n) = XO2Oj-- (LD, 0,020 + (Q341) ‘Lo Supls of wpa dat sequence x(a) (ICD zeros we ‘adie atthe end aol) = | x(Yx(L4 0, VL, 040, (9342) New Tapes of pr seqamee() ICD aon oe fie atthe ed xg) = 1 QD, xQL4D BLD, 00.00) (0343) "T sample of mputsequeace x(a) (I=) er ‘Thus each data block is of length ‘N’. The N-point DFT Y,,(K) of the output is obtained by multiplying Hik)and Xp(K) ie, You(h) = H)*Xop(K), = OTe NAL = (Q344) SP eon romain mp at aDigital Signal Processing 2-21 DFT and FFT Here H(t) is N-point DFT of unit sample response h(v)and Xq (k) is DET of m"* data block. ‘The sequence y,,(1) is obtained by taking N-point IDFT of ¥,,(k) Thus samples of sequence Yq, (1) will be, ysl) = {ys(0), yi. vL-D ve (L yi(L4 DvD} ~ (QH5) al) = Ly) ¥2 (Dea E=D, ¥o(B Wg (LD, --¥9(N-D} (9346) ‘+ Last M-1 samples of each output sequence must be overlapped and added to First M-1 samples of succeeding output sequence. '* The final output sequence will be as follows : ye) = {41 O41 Dt LDL (D+ 2 O). [yn L+ D+ 4 OD] [yr (N=1)4 yp (M=1)], vp (M), yo (N-D} = (Q347) This process continues till the end of input sequence. Q.35 Explain the overlap save method for calculating linear convolution. ‘Ans. : Overlap save method : In the overlap save method ‘L’ samples of the current segment and (M-1) samples of the previous segment forms the input data block. Thus the input data blocks will be, x(n) = 0.9, 2), Myon nee (LT) (935.1) ‘ie block padded wih NI sores ‘L! Gamer of Gla asquenee xt) x(n) =] x(L-M4D,n (Le), x(D,x(L# 1.x 2L-1) = (Q35.2) O01) Ge ame of equmer() Nat a amples of sequence 2(n) x(n) =} r@I-M41),..x@L-1) .x@D,r@L41)..x@L-1) 42353) (CT) daa senple oF aaqumnoe a(n) New T dala samples 7 of sequence € (2) Thus 14(n),x9 (1), x5(1),... ete blocks of N= L+ M=1 samples are formed for block by block filtering, We know that unit sample response tr(1t) contains ‘M' samples, Hence its length is made 'N' by padding L-1 zeros as shown below. Ben) = | OMA eae B(MET) 0,0) (LT 2er08) ‘Mamples of ua emplewesponse (L-I) gems ae pda w@ make NEL MOL tual simples SP eon romain mp at aDigital Signal Processing 2m DET and FFT The DFTs of x4(u), x2(0} .-. Ym (n) and h (a) are calculated. Thus, Gm{k) = H{k)-Xm(k), k= 0, 1, ... NT And Gm (ti) = IDET, (k)) The individual samples of 9, (1) will be, Go) = Gre O-Ion O--GerM—D-Gro( M.D MAD .-- Gn ND) ‘Initial M-1 samples of each of Hm (ni) must be discarded to avoid aliasing, Last ‘L’ samples of my (1) are correct output samples. ie. Ym (2) * Bos () for n= M, Mud, .... NI Above blocks of yy (1) are filled one after another to get final output 0.36 What is the value of x(n) * h(n) 0 893+L-13L-6 Step2: hm) =, 1, 10, 0 0 0 0} ‘Meamples—_L- Tze Step 3: x4(n) = H1,2,0-3,42 0,0) Csamphs MoT Zara xA(n) = 1,1,-2, 3,21 0,0) Teainples ALT Zeros x3(1) = £3,0,0,0,0,0, 0, 01 Zeros appended M-Tzems Step 4: To obtain H(k) and X,(k) Here x, (n) can be written as, xy(n) = 8(n)+28(1-1)-35(n-3)+48(n-4) +2 B(n— 5) ber _;2 We know that, | 3-1) <> €!N wit = (Q36.1) ” X,(k) = 1+2WE-3 wg ea f+ 2Ww 3 H(Q) = 8(1)+8(n=1)45(0~2)- 14 WE +W2E By equation (236.1) SP eon romain mp at aDigital Signal Processing 2-23 DFT and FFT i(k) = X1(k)- HK) = (14 2WE -3 3 + awe 42 Wek) We + WF) = resi ssw? wots wetsawst sowste2w?* Obtain IDFT using equation (Q.36.1), Ya (i) = 1435 (1=1) 43 81 2)-8 (1-3) +5 (1-4) +38 (1 5) +68 (1-G)425(N-7) = {1, 3, 3, -1, 1,9, 6, 2) Step 5: x(n) = + 1,1, ~2,3,2,1, 0,0) s Xo(k) ~ -1+WE- 202 4aw3t 42k WE * alk) > Xa(k) H(k) = (1+ WE 22 eat s2wygt sWwEFy We Wet) = -1-2 Wek +2 Wet +3 WSE HOWE +3 Wok + WIE Taking IDFT using equation (Q.36.1), yoln) = -1,0,-2,2,3,6,3,11 Step 6: x4(n) = 13,0, 0,0, 0,0, 0,0) * X5(k) = 3 s ys(h) =X (Hk) = (3) Cl WE + W2E 2 3-3wi-3w2 * y3(n) = + 3,-3,-3) Step 7 : We have to add last M - 1 ie, 2 samples of each y,(n) to first M - 1 ie. 2 samples of succeeding y,(n) It is shown below oP Pb er Pee wo | | = fo |-2 [2 [a [e [a ft wo | | | | J-3 |-3 [-s uy fa [3 [3 ar fa [a [5 [2 -2 |2 [3 6 |o -2 |-3 Thus the output of linear filter is, y(n) > {1,3,3,-1,13,5,2,-2,2,3,6,0,-2,-3) T Q.37 Perform linear convolution of the two sequences x(n) = (1, 2, 3,- 1, 2, ~ 3, 4, 5, 6) and h(n) = 2, 1, ~ 1) using overlap-add method. 1S INTU : May-22, Dec-13, Marks 10] Ans. : 1) Overlap-save method hin) = (2, 1,-ie M=3 Step 1: N = 2M=93=8 Since N = L+M-1>8=L+3-15L=6 SP recrncas PunLoATONS" Ao up tat br knitDigital Signal Processing 2-28 DFT and FFT Step 2 An) = (2,1, -1, 0, 0, 0,0, 0) N= Scamples Step3: 4m) = 10,0, 12,3, -1, -2, -3, 4) MaYzems—Ceamplizolstay x(n) = 3,4, 5, 60,000) LatKt—1 remaithg samples samy les of of x(n) * it Step 4: yin) = ayn) iin ~ (0,0, 12, 3,1, -2, -3, 1812, 1, -1, 0, 0,0, 0, 0} = (7,4, 24, 18-11, -8,-7, 71 siep $2 yun) = (iS aGw = 13,4,5,6,0,0,0,0) 12,1, -1, 0, 0, 0, 0, 0) > +6,5,17, 13,1, -6, 0,0) Step 6 : First M— 1 ie. 2 samples of yy(n) and yp(n) are discarded and then sequences are fitted one after another. ie. yon) =|24, 18, -11, -8, -7, 7, 17, 13, 1, -6,0,0) T ={24, 18, -11, -8, -7, 7, 17, 13, 1, -6} t 2) Overlap-add method Step 1 N = 2M=23=8 and L=N-M+1=8-3+1-=6 Step 2: Mu) = (2,1, 1, 0,0,0,0,0) T= Samples Step 3: a(n) = (12,3, -1, -2, -3, 4, 0, 0) T= Geamplesofimy _ M~—Tzeros x2(n) = {5, 6 0, 0,0,0, 0, 0) Neb= 6 M~izeros samples of fn) sata) ®) itn) (12, 3, 1, -2, -3, 40,0 Step 4: yin) 2, 1, -1, 0, 0, 0, 0, 0} (24, 18, -11, -8, ~7, 7, 7, -A) SP eon romain mp at aDigital igual Processing 225 DETand IFT Step 5: y(n) = xo(n)(N) htm 15,6, 0,0, 0,0, 0, 01(8)I2 1, -1, 0, 0,0, 0,0) {10, 17, 1,-6,0, 0,0, 0) Step 6: Last M— 1 ie, 2 samples of each y(n) should be added to first M 1 ie. 2 samples of succeeding y,(n). It is shown below : no-=| |r |u|» {7 |7 [7 [4 | | yaln= | | | w |v |r j|* [o |o fo jo wai | [au fs {7 [7 [wv [ws |r |* Jo jo fo fo ‘Thus, y(n) = (24, 18, -11, -8, ~7, 7, 17, 13, 1, -6) Thus, the linear convolution obtained using overlap-save method is same as that obtained by overlap-add method, Q.38 Perfomm linear convolution of two sequences x(n) = (1, - 1, 2, - 2, 3, - 3, 4,—4} and h(n) = {- 1, 1} using overlap add method. DG [INTU = May-13, Marks 10] ‘Ans. : Overlapped Method hin) = Stepl: N= L=N-M+1=4-2+1 -3 Step 2: h(n) Step3: x(n) = (1, A, 2 o1 L=3simples = M-1 of x(n) zer0s x(n) = 1-23, 9) Next L=3 samples M-1 of x(n) zeros x(a) = H,-4,0,01 Step 4: y(n) = xy(n)(Q) hte) = 1-12.08) +11, 0,0) -+1,2,-3,2) SP recrncat PURLCATIONS Ao up ta br knitsDigital Signal Processing 2-26 DFT and FFT x2(n) (N) h(n) +2,5,-30 110,01 12, —5, 6, —3) xg(n) (hin) 4-40.09 E1100 148-40 Step5: — y2(n) 1 Step 6: y3(n) Step 7 : Last M— 1 ie 1 sample of each y,(n) should be added to first M — 1 ie. 1 sample of succeeding y(n). This is shown below : yina-1|2|-3]2 yal) = 2|-s}6 |-3 yaln) 2 -4|a|-4 |o yma-1 }2]}-3]4]-3]6 |-7 |s |-4 |o Thus, y(n) = + 1, 2-3, 4, -5,6,-7, 8-4) 24 : Relation between DTFT, DFS, DFT and z-transform Part - A : Short Answered Questions Q.39 Give the relation between DTFT and z-transform. (ES [INT : May-16, Marks 2] Ans.: DFT X(k) = X(Q)|p_2#, x ‘Thus DFT is the sampled version of DTFT with ‘N' samples over the frequency range of 0 to 2x. Q.40 What is the relationship between DFT and z-transform. Ans. : DFT is basically z-transform evaluated on the unit circle at evenly spaced points. XG) = X(2)|,._ amy Q.41 State the relationship between DFT and DFS. DS [INTU : May-17, Marks 5] Ans. : DFT and DFS coefficients are related by following equation, Xik) = Nok), k=O, ...N-1 And IDFT is same as DFS equation. ie, Teint = SSL ef2minyn ao) = 5 EMEP = Siete! SP eon romero mp at aDigital Signal Processing 2-27 DFT and FFT Part - B : Long Answered Questions Q.42 Derive the relationship between DFT and z-transform. Ans. : Relationship between DFT and z-transform + The z-transform of sequence x(1) is given as, xe) =F xe" (421) «Let us sample X(2) at 'N’ equally spaced points on the unit circle. These points will be, ap = PEIN and k=O Tene N = (Q422) ‘If we evaluate z-transform at these points, Mohy_gare =F iePemee If x(n) is causal sequence and has 'N’ number of samples, then above equation becomes, Net XY, J2ewN = SY x(npe /aktN w=» (Q42.3) 0 The RHS of above equation is nothing but DFT X(k} Thus the relationship between DET and z-transform is, Relationship = (K)= XY, =f 2 HIN wwe (QA24) Explanation : This means if z-transform is evaluated on unit circle at evenly spaced points only, then it becomes DFT. Earlier we have seen that if z-transform is evaluated on unit circle, then it becomes Fourier transform. Q.43 Derive the relationship between DFT and DFS. ‘Ans. : Relationship between DFT and DFS ‘+ The Discrete Fourier Series (DFS) coefficients for a periodic sequence x» (1) over period N are given as, i eh) = S xp(n) oP ERIN, + (Q43.1) Tt is shown in next section that, a(n) PET) X(K) _-By equation (43.2) and xp (rt) PEE K(k) --By equation (Q433) Here xp(it) is the periodic version of x(n) x(n) as well as xp(n) have the same DFT ie. X(k} By definition of DFT we can write, SP eon romain mp at aDigital Signal Processing 2-28 DFT and FFT Not XR) Lore PEM | k = «Since x(n) and x(n) have same DFT we can write above equation as, Not XK) =D xp (ne /2=IN | k=0,1, N-1 Patting this value in equation (0.43.1) we have, a= XK), k= 0,1...N=1 = (Q.43.4) Relationship : X(k) = N-e(k), k=0,1,...N=1 -- (Q43.5) This equation gives the relationship between DFT and DFS coefficients. If we know the DFS coefficients, then DFT can be obtained by above equation. Consider the IDFT formula, Nal xo Sec, From equation (Q.42.8) we know that c(k)= 4 X(W), hence above equation becomes, wet x(n) =D ek) el7*MIN n= 0,1,...N-1 2 We know that x(n) is basically periodic with period N. Observe that this equation is basically DFS equation. Thus IDFT is same as DFS equation Q.44 Derive the relationship between DFT and DTFT. USF [AWTU = May-12, Marks 5] Ans. : Relationship between DFT and DTFT '« The DTFT is given as, x(a) =F x{nyerion seus eve ths DTT at 2 whee #012, NL Then we gt Fr) = z a(n) ef st oe tat(251) se DET olf ps ua ny = Exeeiny Thus xp(1t) is the sequence which is periodie with period N. Hence if sequence x(n) has the length less than ‘N’, then x,(%) = x0), SP recrncat URICATIONS- Ao up tat br knDigital Signal Processing Relationship = ale X(k) ie. DFT of x(n) If length of x(n) is greater than N, then DET and DIFT will have no direct relationship. 2.5 : FFT Algorithms : Radix-2 DIT-FFT Important Points to Remember * Decimation means to reshuffle the sequence. + Radix2 FFT algorithms end up in direct calculation of 2-point DFT. sin place requirement. calculations reduce memory * Bit reversal provides decimated sequences. © Computational complexity of FFT algorithms. Complex multiplication : tog, N ‘Complex addition : Nlog, N. Part - A : Short Answered Questions Q.45 What is FFT ? List its applications. EG’ [INTU : Dec.-14, Marks 2, May-14, Marks 3] Ans.: FFT : Special algorithms are developed to compute DFT quickly. These algorithms exploit the periodicity and symmetry properties of twiddle factors (phase factors). These algorithms require less computational time compared to direct computation of DFT. These algorithms are called fast fourier transform (FFT) algorithms. ‘As the length of DFT increases, FFT algorithms are computationally more efficient, Applications of FFT algorithms i) Linear filtering of long sequences. ii) Spectrum analysis of signals. iii) Image and voice compression/decompression. iv) Solution of difference equations. v) Evaluation of discrete sine and cosine transforms. DFT and FFT Q.46 State the number of computations in direct calculation of N-point DFT. St. No. Operation Number of computations 1 NP 2 | Complex additions NUN 3 | Real multiplications an? 4 | Real additions N2—2N 5. | Trigonometrie functions 2N? Q47 State the properties af twiddle or phase factor. ‘Ans.: Periodicity, Wy? = Wy, a 7. _wh Symmetry, wy? = -Wy and W2 = Wap Q.48 Draw the butterfly diagram for radi DIT-FFT and explain in place computation. ‘Ans. : Fig. Q48.1 shows the butterfly diagram. Anas Wib Bean wb Fig, ©.48.4 Butterfly computation in FFT From two input values ‘a’ and ‘b' the two values * and 'B’ are calculated. * Once ‘A’ and ‘B' are computed, there is no need to store ‘a! and 'b’. Thus ‘A’ and ‘B’ can be store in place of ‘a’ and ‘b. This is called in place computation. The advantage of _ in-place computation is that it reduces memory requirement. 49 What Is the computational radix 2 DIT-FFT computation. complexity of algorithm compared to direct FF recemuca PUaLICATIONS™ An up nat br kengeDigital Signal Proessing 2-30 DFT and FFT Ans. [Number of, Direct computation | _—_DIT FFT algorithm Improvement in processing speed for ins ‘multiplications, Pe ‘Complex ‘Complex ‘Complex Complex ” N | multiplications | additions | multiplications | additions nN? WioggW Nt nt | Xiggey |X iega 2 Part - B : Long Answered Questions Q.50 What is FFT ? Calculate the number of multiplications needed in the calculation of DFT using FFT algorithm with 32 point sequence. BG [INTU + Aug.-06, May-16, Dec.-11, 17, Marke 5] Ans. : FFT : Refer Q.45 (section 2.5) Direct computation of DFT 1. Complex multiplications = N? = 32? = 1024 2. Complex additions = N2— N = 1024 — 32 = 992 DIT-FFT algorithm 1. Complex multiplications = tog, N= * tog, 92 = 80 2. Complex additions = Nlog, N =S2log, 32 = 160 Q.51 Explain radixc2. DIT-FFT algorithm in detail for N= OR How the computational speed of FFT algorithm has been improved over DFT. 5[INTU : Dec-13, Maris 5] OR How the computational complexity is reduced in FET over DFT ? S5/[QNTU = Hay-13, Marks 5] Ans. : The N-point DFT is split in even numbered x (n) and odd numbered x (n) as follows + XW) = ZY xonwe sy roywkt tea sel N -1 Na ~ SD renpw: xQm+e1Wwi s mS xemengen® =0 =o Here let f,(n) = x Qn) and fy (n= x Qn + 1) xm y Silay Wy + 5 Sa (ny "Wy 22 Hore use W2 = Nay a x@ = s futons «wk 5 at) we, =D = Fy (+ Wh Fk) k= 0,1, NT - (Q51.1) point DFTs are periodic with period ©. Hence x w +8) = mapand n (re) 50) FF ane nara so