Exercises in Digital Signal Processing 1 The Discrete ...

1 Exercises in Digital Signal ProcessingIvan W. SelesnickJanuary 27, 2015 Contents1 The Discrete Fourier Transform12 The Fast Fourier Transform163 Filters184 Linear-Phase FIR Digital Filters295 Windows386 Least Square Filter Design507 Minimax Filter Design548 Spectral Factorization569 Minimum-Phase Filter Design5810 IIR Filter Design6411 Multirate Systems6812 Quantization7413 Spectral Estimation7514 Speech Filtering8215 More Exercises8616 Old Exercises911 The Discrete Fourier Compute the DFT of the 2-point Signal by hand (without a calculator orcomputer).x= [20,5] Compute the DFT of the 4-point Signal by [3,2,5,1] The even samples of the DFT of a 9-point real signalx(n) are given byX(0) = ,X(2) = + j,X(4) = + j,X(6) = + j,X(8) = j,Determine the missing odd samples of the DFT. Use the properties of theDFT to solve this The DFT of a 5-point signalx(n), 0 n 4 isX(k) = [5,6,1,2,9],0 k new signalg(n) is defined byg(n) :=W 2n5x(n),0 n are the DFT coefficientsG(k) of the signalg(n), for 0 k 4?

2 Compute by hand the circular convolution of the following two 4-pointsignals (do not use MATLAB, etc.)g= [1,2,1, 1]h= [0,1/3, 1/3,1/3] What is the circular convolution of the following two sequences?x = [1 2 3 0 0 0 0];h = [1 2 3 0 0 0 0]; What is the circular convolution of the following two sequences?1x = [1 2 3 0 0 0 0];h = [0 0 0 0 1 2 3]; What is the circular convolution of the following two sequences?h = [1 2 3 0 0 0 0];x = [1 1 1 1 1 1 1]; What isyafter running the following MATLAB commands? Do not useMATLAB to get your answer and do not explicitly compute the DFT;instead use the properties of the = [1 2 0 -1];g = [1 0 0 2 1];X = fft([x 0 0 0]);G = fft([g 0 0]);Y = X.*G;y = ifft(Y); What isyafter running the following MATLAB commands?clearx = [1 2 3 4];g = [5 6 7 8];X = fft([x 0 0 0]);G = fft([g 0 0]);Y = X.

3 *G;y = ifft(Y); Suppose you run the following DFT example in = [1 2 3 4 3 2 1] ;x2 = [1 2 3 4 4 3 2] ;x3 = [1 2 3 4 -4 -3 -2] ;x4 = [0 2 3 4 -4 -3 -2] ;X1 = fft(x1)X2 = fft(x2)X3 = fft(x3)X4 = fft(x4)This vectors X1, X2, X3, X4 are shown below out of order. Using propertiesof the DFT, match them to vectors A, B, C, D, by completing the how you get your answers. Do not use MATLAB for this problemand do not explicitly compute the DFT; instead use the properties of - + - + - + :00 + - + - + + - + - + Letx(n), for 0 n N 1, be arealN-point Signal . The DFT coefficientsareX(k), for 0 k N 1.(a) Show thatX(0) is a real number.(b) AssumeNis an even number. IsX(N/2) real, imaginary, or a genericcomplex number? Show your Consider the following 8-point signals, 0 n 7.(a) [1,1,1,0,0,0,1,1](b) [1,1,0,0,0,0, 1, 1](c) [0,1,1,0,0,0, 1, 1](d) [0,1,1,0,0,0,1,1]2 Which of these signals have a real-valued 8-point DFT?

4 Which of thesesignals have a imaginary-valued 8-point DFT? Do not use MATLAB orany computer to solve this problem and do not explicitly compute theDFT; instead use the properties of the Consider the following 9-point signals, 0 n 8.(a) [3,2,1,0,0,0,0,2,1](b) [3,2,1,0,0,0,0, 2, 1](c) [3,2,1,0,0,0,0, 2, 1](d) [0,2,1,0,0,0,0, 2, 1](e) [0,2,1,0,0,0,0,2,1](f) [3,2,1,0,0,0,0,1,2](g) [3,2,1,0,0,0,0, 1, 2](h) [0,2,1,0,0,0,0, 1, 2](i) [0,2,1,0,0,0,0,1,2]Which of these signals have a real-valued 9-point DFT? Which of thesesignals have an imaginary-valued 9-point DFT? Do not use MATLAB orany computer to solve this problem and do not explicitly compute the DFT;instead use the properties of the Consider theN-point sequencex(n) defined forn= 0,..,N 1. Showthat ifx(n) is real, then theN-point DFTX(k) satisfiesX(N k) =X(k), k= 0.

5 ,N 1,(1)where the overline notation denotes the complex and circular the circular convolution propertyof the DFT in Matlab. Write two Matlab functions to compute the circularconvolution of two sequences of equal length. One function should usethe DFT (fftin Matlab), the other function should compute the circularconvolution directly not using the DFT. Verify that both Matlab functionsgive the same in a hard copy of both functions, and an example verifying they givethe same results (you might use thediarycommand). and linear a Matlab function that uses theDFT (fft) to compute the linear convolution of two sequences that arenot necessarily of the same length. (Use zero-padding.) Verify that itworks correctly by comparing the results of your function with the The 13-point DFT of a 13-point signalx(n) is given byX(k) = [0 0 1 0 0 0 0 0 0 0 0 1 0], k= 0.

6 ,12 Give a formula forx(n) in terms of trigonometric functions. You answershould not contain What is the inverse DFT of the followingN-point Discrete -time sequenceX(k)?X(k) = [0,1,0,0, ..,0 N 3 terms,1], k= 0,1,..,N answer should be a formula forx(n) in terms ofnandN. Isx(n)real-valued? If so, simplify your answer forx(n) so that it does not What is the inverse DFT of the followingN-point Discrete -time sequenceX(k)?X(k) = [0,j,0,0, ..,0 N 3 terms, j], k= 0,1,..,N answer should be a formula forx(n) in terms ofnandN. Isx(n)real-valued? If so, simplify your answer forx(n) so that it does not The DFT of anN-point signalx(n) is given byX(k) = [0,ej ,0,0, ..,0 N 3 values,e j ],0 k N theN-point signalx(n). Simplify your answer. Isx(n) real? If so,express your answer without using The 23-point signalx(n) is two cycles of a cosine Signal ,cos(2 2Nn),0 n N 1,withN= signalx(n) is illustrated in the 1 (n)(a) The 23-point DFT ofx(n) is computed.

7 The DFT coefficients aredenotedX(k). Accurately sketch|X(k)|for 0 k N 1.(b) A 23-point signaly(n) is obtained by circularly shiftingx(n) by 3samples to the right. The 23 DFT coefficients ofy(n) are denotedY(k). Accurately sketch|Y(k)|for 0 k N Find the DFT of theN-point Discrete -time Signal ,x(n) = cos(2 Nn+ ), n= 0,1,..,N Sketch the signalx = sin(2*pi*[0:7]/8);and find the DFT of x. Do not use direct computation of the The 20-point signalx(n) is given byx(n) = sin(2 N2n),0 n N 1whereN= 20.(a) Roughly sketch the Signal for 0 n 19. Do not explicitly calculatethe values.(b) Find the DFT coefficients of the Signal . That means, findX(k) for0 k 19. Show the derivation of your answer. You should not usedirect computation of the (a) Find the DFT of theN-point Signal ,x(n) = cos(4 Nn)n= 0,..,N , sketchx(n) andX(k).

8 (b) Find the DFT of theN-point Signal ,x(n) = cos(4 Nn 4)n= 0,..,N (a) Find the DFT of theN-point Signal ,x(n) = sin(4 Nn)n= 0,..,N , sketchx(n) andX(k).(b) Find the DFT of theN-point Signal ,x(n) = sin(4 Nn )n= 0,..,N (a) What is the 30-point signalx(n) that has the following DFT? (Providea mathematical formula.)X(k) ={1, k= 40, k6= 4for 0 k <30(b) What is the DFT of theN-point Signal ,x(n) = cos(2 NP n),0 n N 1wherePis an integer between 0 andN? Hint: using the previouspart. Show the derivation of your Find theN-point DFT of theN-point sequence:x= [1,0, 1,0 repeats, ..,1,0, 1,0]The sequence is made ofKperiods of the 4-point sequence (1, 0, -1, 0).The length of the sequence isN= 4K. Simplify your The following MATLAB commands define two ten-point signals and theDFT of = cos([0:9]/9*2*pi);x2 = cos([0:9]/10*2*pi);X1 = fft(x1);X2 = fft(x2);(a) Roughly sketch each of the two signals, highlighting the distinctionbetween them.}

9 (b) Which of the following four graphs illustrates the DFT|X1(k)|? Ex-plain your answer. Which graph illustrates the DFT|X2(k)|?01234567890246 GRAPH A01234567890246 GRAPH C01234567890246 GRAPH D01234567890246 GRAPH B01234567890246 GRAPH E01234567890246 GRAPH F01234567890246 GRAPH G01234567890246 GRAPH HGive your answer by completing the table and provide an explanationfor your answer. Note that there are more graphs shown than answer will use only two of the eight graphs. Provide a briefexplanation for your answer. You should be able to do this exercisewithout using MATLAB (this was an exam question). The following MATLAB commands define three ten-point signals and theDFT of = sin([0:9]/10*pi);x2 = sin([0:9]/9*2*pi);x3 = sin([0:9]/10*2*pi);X1 = fft(x1);X2 = fft(x2);X3 = fft(x3);(a) Roughly sketch each of the three signals, highlighting the values of thefirst and last values of each Signal (b) Which of the following graphs illustrates the DFT|X(k)|of each sig-nal?

10 01234567890246 GRAPH A01234567890246 GRAPH C01234567890246 GRAPH D01234567890246 GRAPH B01234567890246 GRAPH E01234567890246 GRAPH F01234567890246 GRAPH G01234567890246 GRAPH H 01234567890246 GRAPH I 5 Give your answer by completing the table and provide an explana-tion for your answer. Note that there are more graphs shown thanneeded. Your answer will use only three of the graphs. Provide a briefexplanation for your What is the result of the following MATLAB commands? Explain youranswer.>> x = ones(1,10);>> X = fft(x) LetNbe an even integer. Let theN-point signalx(n) be defined for0 n N 1 asx(n) ={1, neven0, the DFT of theN-point Discrete -time signalx(n). Your answer shouldbe simplified. IfX(k) is real, write it without using What is the result of the following MATLAB command? Do not use directcomputation of the DFT.}