T-61.3010 Digitaalinen signaalinkäsittely ja suodatus T-61.3010 Digital Signal Processing and Filtering ============================================================ RATKAISUJA / SOLUTIONS PART 4 ============================================================ ------------------------------------------------------------ (25) 1. välikoe / 1st mid term exam, 7.3.2008 ------------------------------------------------------------ Monivalintatehtävä 1 / Multichoice Problem 1 Kohdittain / Statement by statement: kok.lkm / total count N=100: väite: [oikea(t)] --> lkm[A/B/C/D/-/Z] [vastaus%]:[A/B/C/D/Z]% statem.[correct] --> count[A/B/C/D/-/Z] [reply%]:[A/B/C/D/Z]% 1.1: [D] [3/1/49/38/9/0] [91%]:[3/1/54/42/0]% 1.2: [BD] [12/53/12/15/8/0] [92%]:[13/58/13/16/0]% 1.3: [C] [14/3/79/2/2/0] [98%]:[14/3/81/2/0]% 1.4: [C] [7/13/49/18/13/0] [87%]:[8/15/56/21/0]% 1.5: [D] [4/0/2/94/0/0] [100%]:[4/0/2/94/0]% 1.6: [ABCD] [57/6/0/21/16/0] [84%]:[68/7/0/25/0]% 1.7: [B] [6/58/10/3/22/1] [78%]:[8/74/13/4/1]% 1.8: [A] [52/3/13/18/13/1] [87%]:[60/3/15/21/1]% 1.9: [D] [2/5/39/4/50/0] [50%]:[4/10/78/8/0]% 1.10:[B] [9/26/27/9/28/1] [72%]:[12/36/38/12/1]% Muutamia kommentteja / Some comment: - 1.1: x = exp(j(2pi k + pi)/2008), k=0..2007 = exp(j(pi)/2008), exp(j(3pi)/2008), ... --> theta = 2pi/2008 ****(oikein/correct 38%) - 1.2: N1=3, N2=14, N3=4 --> N0=28N1=6N2=21N3 *******(oikein/correct 68%) - 1.3: L{y}=5+7-1=11, A{y}=-1-1=-2 y[n] = {a01, a02, _a03_, a04, ..., a11} ********(oikein/correct 79%) - 1.4: h[n] = 0.5 (d[n] + d[n-1]) H(z) = 0.5 (1 + z^(-1)) <--> 1. order FIR *****(oikein/correct 49%) - 1.7: Vrt./compare 1.1: x^2008 + 1 = 0 All 2008 zeros symmetrically on unit circle with interval 2pi/2008 ******(oikein/correct 58%) - 1.8: Poles at p1=0.5, p2=0.7: H(z) = 1 / [(1 -p1 z^(-1))(1 - p2 z^(-1))] *****(oikein/correct 52%) - 1.9: Katso/See [P56] (oikein/correct 4%) - 1.10: Katso/See Matlab 3 B = [...], A = [...], freqz(B,A), zplane(B,A), impz(B,A), ... ***(oikein/correct 26%) Pistekeskiarvo / Mean: N=100: 4.04p / 8p. Datahistogrammi kokonaispisteistä nähtävillä / Histogram of total points: http://www.cis.hut.fi/Opinnot/T-61.3010/VK1_K2008/monivalinta_vk1A_k2008.png Tehtävä 2 / Problem 2 - input sequence x[n] = A cos((2pi/4)n + theta) - output sequence y[n] = A cos((2pi/4)n + (theta-pi/2)) - system: H(z) = G (1 - (-0.5)z^(-1))(1 - (-2)z^(-1)) = G (1 + 2.5 z^(-1) + z^(-2) h[n] = G (d[n] + 2.5d[n-1] + d[n-2]) - scaling: |H(w=pi/2)| = 1 G |1 - 2.5j - 1| = 1 H(z) = 0.4 + z^(-1) + 0.4z^(-2) - amplitude response: lowpass - phase response: linear, lkm[A/B/C/D/-/Z] [vastaus%]:[A/B/C/D/Z]% statem.[correct] --> count[A/B/C/D/-/Z] [reply%]:[A/B/C/D/Z]% 1.1: [C] [2/0/98/3/6/0] [94%]:[2/0/95/3/0]% 1.2: [C] [49/7/23/11/19/0] [83%]:[54/8/26/12/0]% 1.3: [A] [96/2/7/1/3/0] [97%]:[91/2/7/1/0]% 1.4: [B] [3/71/7/13/15/0] [86%]:[3/76/7/14/0]% 1.5: [B] [59/22/4/1/23/0] [79%]:[69/26/5/1/0]% 1.6: [B] [23/39/23/3/21/0] [81%]:[26/44/26/3/0]% 1.7: [D] [2/37/2/11/57/0] [48%]:[4/71/4/21/0]% 1.8: [D] [3/2/18/59/27/0] [75%]:[4/2/22/72/0]% 1.9: [C] [34/12/30/10/23/0] [79%]:[40/14/35/12/0]% 1.10: [D] [14/5/25/36/29/0] [73%]:[18/6/31/45/0]% Muutamia kommentteja / Some comment: - 1.2: When N0=3, we get cos((2pi/9)n^3 + 2pi(n^2 + 3n +3)) where 2pi-multiple, because n is integer and therefore also (n^2 + 3n + 3) is integer. / **(oikein/correct 22%) - 1.3: L{y}=3+7-1=9, A{y}=1-2=-1 y[n] = {a01, _a02_, a03, ..., a09} *********(oikein/correct 88%) - 1.4: fs=12 kHz <--> 2pi *******(oikein/correct 65%) - 1.5: T = 0.004 ms, fT = 250 Hz. Flipping around each fT/2=125: 420 Hz -(|375|)-> 330 -(|250|)-> 170 -(|125|)-> 80 **(oikein/correct 21%) - 1.6: Formulas (DTFT): e^(j wk n) x[n] <-DTFT-> X(e^(j(w-wk))) e^(j wk n) = {1, -1, 1, -1, 1, -1, ...} ****(oikein/correct 36%) - 1.7: Vrt./compare 1.1: f(x) = 1.5/(x-(0.9)) - 0.5/(x-(-0.9)) H(z) = 1.5/(1-(0.9)z^(-1)) - 0.5/(1-(-0.9)z^(-1)) h[n] = 1.5 (0.9)^n mu[n] - 0.5 (-0.9)^n mu[n] h[2008] = 1.5 (0.9)^2008 - 0.5 (-1)^2008 (0.9)^2008 *(oikein/correct 10%) - 1.8: (C): 8 zeros equally spaced *****(oikein/correct 54%) - 1.9: Zero and Pole at z=+1 cancel each other: H(z) = (1/2008) (1 - z^(-2008))/(1 - z^(-1)) = K (1 - z^(-1))(1 + z^(-1) + ... + z^(-2007))/(1 - z^(-1)) = (1/2008) (1 + z^(-1) + ... + z^(-2007)) h[n] = (1/2008) (delta[n] + ... + delta[n-2007]) ***(oikein/correct 28%) - 1.10: Katso/See Matlab 3 B = [...], A = [...], freqz(B,A), zplane(B,A), impz(B,A), ... ***(oikein/correct 33%) Pistekeskiarvo / Mean: N=109: 2.83p / 8p. Datahistogrammi kokonaispisteistä nähtävillä / Histogram of total points: http://www.cis.hut.fi/Opinnot/T-61.3010/VK1_K2008/monivalinta_vk1B_k2008.png Tehtävä 2 / Problem 2 (a) H1(z) = 1 + z^(-1); z=-1 --> LP; linear-phase FIR (b) h[n] = K (h1[n] (*) h1[n] (*) h1[n] (*) h1[n] (*) h1[n] (*) h1[n]) H(z) = K (1+z^(-1))^6 = K (1+6z^(-1)+15z^(-2)+20z^(-3)+15z^(-4)+6z^(-5)+z^(-6)) |H(z=1)| = K |(1+z^(-1))^6| = 64 K = 1 K = 1/64 (c) Katso/see [P42], [P58] H(e^jw) = K e^(-j3w) (...) lkm[A/B/C/D/-/Z] [vastaus%]:[A/B/C/D/Z]% statem.[correct] --> count[A/B/C/D/-/Z] [reply%]:[A/B/C/D/Z]% 1.1: [B] [0/84/4/0/0/0] [100%]:[0/95/5/0/0]% 1.2: [A] [71/3/3/0/11/0] [88%]:[92/4/4/0/0]% 1.3: [D] [0/1/0/65/22/0] [75%]:[0/2/0/98/0]% 1.4: [C] [2/0/69/8/9/0] [90%]:[3/0/87/10/0]% 1.5: [A] [56/2/15/5/10/0] [89%]:[72/3/19/6/0]% 1.6: [B] [0/77/4/1/6/0] [93%]:[0/94/5/1/0]% 1.7: [B] [1/40/5/3/39/0] [56%]:[2/82/10/6/0]% 1.8: [B] [6/15/1/1/65/0] [26%]:[26/65/4/4/0]% 1.9: [C] [1/9/48/7/23/0] [74%]:[2/14/74/11/0]% 1.10:[B] [0/29/5/3/51/0] [42%]:[0/78/14/8/0]% Muutamia kommentteja / Some comment: - 1.8: oikein siis (B) eli k=-1, jolloin kompensoiva nolla tulee kohtaan z=1 eli napaparin lähelle. **(oikein/correct 17%) - 1.9: navat ja nollat aiheuttavat lokaaleja värähdyksiä. (B):ssä päästökaistalla 2 huippua ja estokaistalla 2 nollaa --> 4. asteen elliptinen suodin (C):ssä estokaistalla 2 nollaa ja piissä nolla --> 5. asteen suodin (D):ssä päästökaistalla 3 napaa --> 6. asteen suodin Tämän lisäksi Chebychev II päästökaistalla monotoninen ja estokaistalla värähtelevä --> (C) ******(oikein/correct 55%) Pistekeskiarvo / Mean: N=88: 5.67p / 8p. Datahistogrammi kokonaispisteistä nähtävillä / Histogram of total points: http://www.cis.hut.fi/Opinnot/T-61.3010/VK2_K2008/monivalinta_vk2A_k2008.png Tehtävä 2 / Problem 2 Pistekeskiarvo / Mean: N=88: 3.68p / 6p. Kuvallisia ratkaisuja, kts. / Some solutions, see http://www.cis.hut.fi/Opinnot/T-61.3010/VK2_K2008/t2.pdf 2A) FFT - DFT:n laskemiseen tehokas O(N^2) -> O(N log N) - radix-2 DIT FFT, perhosyhtälöt, bittikäänteinen x[n], "in-place"-laskenta, 2^N - esimerkki: Psi_1[0] = x[0] = 2 Psi_1[1] = x[2] = -1 Psi_1[2] = x[1] = 4 Psi_1[3] = x[3] = 5 W_2^0 = 1, W_4^0 = 1, W_4^1 = -j Kuvan 4 järjestelmään sijoitus, kertolaskut ja summaukset: Psi_2[0] = 1 Psi_2[1] = 3 Psi_2[2] = 9 Psi_2[3] = -1 Psi_3[0] = 10 Psi_3[1] = 3+j Psi_3[2] = -8 Psi_3[3] = 3-j Huomaa, että Psi_R[0] on summa kaikista x[n]:istä ja Psi_2[1] = Psi_2[3]^* eli kompleksikonjugaatteja symmetrisesti. 2B) Ylösnäytteistys + alipäästösuodatus Alkuperäisen suotimen rajataajuus 3 kHz == 0.6 pi. a) L=3: - spektrissä fs_new=30 kHz, tulee kaksi "image"-spektriä - aikatasossa kaksi nollaa alkuperäisten väliin b) LP-suodatus: - "anti-imaging"-suotimen rajataajuus noin 3-5 kHz - "imaget" katoavat, LP:n rajataajuudeksi 3 kHz == 0.2pi - aikatasossa väleissä olevat nollat interpoloituu väliin Tehtävän 2 pistehistogrammi kurssin WWW-sivulla: http://www.cis.hut.fi/Opinnot/T-61.3010/VK2_K2008/t2_vk2A_k2008.png ------------------------------------------------------------ (28) Tentti / 2. välikoe / 2nd mid term exam, 14.5.2008 ------------------------------------------------------------ Monivalintatehtävä 1 multichoice Problem 1 Kohdittain / Statement by statement: kok.lkm / total count N=78: väite: [oikea(t)] --> lkm[A/B/C/D/-/Z] [vastaus%]:[A/B/C/D/Z]% statem.[correct] --> count[A/B/C/D/-/Z] [reply%]:[A/B/C/D/Z]% 1.1: [D] [2/0/0/71/5/0] [94%]:[3/0/0/97/0]% 1.2: [C] [0/3/68/2/5/0] [94%]:[0/4/93/3/0]% 1.3: [A] [59/8/0/0/11/0] [86%]:[88/12/0/0/0]% 1.4: [D] [0/5/1/70/2/0] [97%]:[0/7/1/92/0]% 1.5: [D] [1/0/6/35/36/0] [54%]:[2/0/14/83/0]% 1.6: [C] [3/1/54/0/20/0] [74%]:[5/2/93/0/0]% 1.7: [D] [9/1/4/41/23/0] [71%]:[16/2/7/75/0]% 1.8: [C] [7/5/14/2/50/0] [36%]:[25/18/50/7/0]% 1.9: [C] [4/0/16/1/57/0] [27%]:[19/0/76/5/0]% 1.10:[B] [6/25/0/1/46/0] [41%]:[19/78/0/3/0]% Muutamia kommentteja / Some comment: - 1.5: navat laskemalla epästabiili suodin / compute roots - not stable *****(oikein/correct 45%) - 1.7: Oikein siis (D): 1 - 1.8z^(-1) + 0.82 z^(-2) Y(z) = ----------------------------- X(z) + 1 + 1.7z^(-1) + 0.72 z^(-2) 1 + kz^(-1) ----------------------------- E(z) 1 + 1.7z^(-1) + 0.72 z^(-2) *****(oikein/correct 53%) - 1.8: oikein siis (C) eli k=1, jolloin kompensoiva nolla tulee kohtaan z=-1 eli napaparin lähelle. **(oikein/correct 18%) - 1.9: (C) roots([1 4 6 4 1]) fails already **(oikein/correct 21%) Pistekeskiarvo / Mean: N=78: 5.28p / 8p. Datahistogrammi kokonaispisteistä nähtävillä / Histogram of total points: http://www.cis.hut.fi/Opinnot/T-61.3010/VK2_K2008/monivalinta_vk2B_k2008.png Tehtävä 2 / Problem 2 Pistekeskiarvo / Mean: N=78: 3.68p / 6p. Kuvallisia ratkaisuja, kts. / Some solutions, see http://www.cis.hut.fi/Opinnot/T-61.3010/VK2_K2008/t2b.pdf 2A) FFT - DFT:n laskemiseen tehokas O(N^2) -> O(N log N) - radix-2 DIT FFT, perhosyhtälöt, bittikäänteinen x[n], "in-place"-laskenta, 2^N - esimerkki: Psi_1[0] = x[0] = 6 Psi_1[1] = x[2] = -3 Psi_1[2] = x[1] = 1 Psi_1[3] = x[3] = 1 W_2^0 = 1, W_4^0 = 1, W_4^1 = -j Kuvan 4 järjestelmään sijoitus, kertolaskut ja summaukset: Psi_2[0] = 3 Psi_2[1] = 9 Psi_2[2] = 2 Psi_2[3] = 0 Psi_3[0] = 5 Psi_3[1] = 9 Psi_3[2] = 1 Psi_3[3] = 9 Huomaa, että Psi_R[0] on summa kaikista x[n]:istä ja Psi_2[1] = Psi_2[3]^* eli kompleksikonjugaatteja symmetrisesti. Tosin tässä tapauksessa, koska x[n] on "symmetrinen" y-akselin suhteen, niin DFT:stä tuleekin myös reaalinen. Huomaa, jos bittikäännös unohtunut, niin laskettu jonosta {_6_, -3, 1, 1} --> {5, 5+4j, 9, 5-4j} 2B) IIR- ja FIR-suotimien suunnittelu Rajakulmataajuus omega_c = pi/3 a) FIR, esim. ikkunamenetelmä: h_ideal[n] = (1/3) sin(pi/3 n)/(pi n) = {..., sqrt(3)/(4pi), sqrt(3)/(2pi), _(1/3)_, sqrt(3)/(2pi), sqrt(3)/(4pi), ...} w[n] taulukosta, M=2 h_FIR[n] = h_ideal[n] . w[n] =~ {0.14, 0.28, _0.33_, 0.28, 0.14} . {w[-2], w[-1], 1, w[1], w[2]} =~ {0.011, 0.15, _0.33_, 0.15, 0.011} Hamming-ikkunalla h_FIR[n-2] --> kausaalinen versio --> a = e = 0.011, b = d = 0.15, c = 0.33 b) IIR, bilineaarimuunnos: Omega_pc = k tan(omega_c/2) = k tan(pi/6) Sijoitus z = k (1-z^(-1))/(1+z^(-1)) H(z) = K (1 + z^(-1)) / (1 - 0.27 z^(-1)) Tehtävän 2 pistehistogrammi kurssin WWW-sivulla: http://www.cis.hut.fi/Opinnot/T-61.3010/VK2_K2008/t2_vk2B_k2008.png Tehtävä 2, ka = 1.5p 2A Kts [P74] (vrt. Vk2-pistelaskarit, tehtävä 10) 2B a) [P70] (Paperi #5 / 2008) b) [P68c] (Paperi #5 / 2008) Tehtävä 3, ka = 2.3p 3a) [P20d] N_0=20 (Paperi #1 / 2008) 3b) [P26,P15,P18]: - sisääntuloekvenssi rajoitettu --> ulostulokin rajoitettu - x_1[n] = 0, n < 0, x_1[0] = 2 - 0.71 + 2, ... Ei-kausaalinen LTI --> y_1[n] != 0, joillakin n < 0 arvoilla - y_1[n]:stä löytyvät vain ja vain nuo kolme taajuutta, jotka x_1[n]:ssäkin. LTI voi vain vahvistaa (vaimentaa) ja viivästää (edistää) signaalia. - muuta?! Tehtävä 4, ka = 3,7p 4) h[n] <--- z-muunnos ---> H(z) = SUM_n h[n] z^(-n) a delta[n-k] <--- z-muunnos ---> a z^(-k) Mm. [P30, P31, P32] ja Paperi #2/08 4a) H(z) = H1(z) . H2(z) + H3(z) = 1 - z^(-3) + z^(-5) - z^(-6) 4b) Dekonvoluutio joko aikatasossa [P32] tai taajuustasossa (polynomien jakolasku [P31d]). Aikatason osalta yhtälöryhmä redusoituu niin, että voidaan ratkaista yksi tuntematon kerrallaan, kuten [P32]/Remark "tabular method" esitetään. x[n] = {1, 2, _0_, 3} Tehtävä 5, ka = 1,9p 5a) Apumuuttujan käyttö [P64] / Paperi #4/08: kannattaa laittaa heti summamerkin jälkeen. 1 + 2 z^(-1) + z^(-2) H(z) = 0.5 ------------------------------ 1 + 1.5 z^(-1) + 0.5 z^(-2) 1 + z^(-1) = 0.5 ------------------ 1 + 0.5 z^(-1) kun havaitaan nolla ja napa kohdassa -1 eli sekä ylä- että alakerrassa polynomitermi (1 - (-1)z^(-1)) = (1 + z^(-1)). 5b) Kts [P63] / Paperi #4/08 5c) Napanollakuvion tulkinta: alipäästösuodin. Tehtävä 6, ka = 1,3p 6a) Kts. [P81,P85]. H(z) ----- ----- ----- ----- ----- / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ ---------------------------------------------------------- 0 2pi 4pi 6pi 8pi 0 10 20 30 40 kHz H(z^4) image image image ----- ----- ----- ----- ----- / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ ---------------------------------------------------------- 0 pi/2 pi 3pi/4 2pi 0 10 20 30 40 kHz h[n/4] kolme nollaa alkuperäisten näytteiden välissä 6b) H(z^4) -> LP -> ........... ............ ----- : : ----- / \ : : / \ / \: : / \ ---------------------------------------------------------- 0 pi/2 pi 3pi/4 2pi 0 10 20 30 40 kHz h[n/4] --> LP --> kolmet nollat interpoloituneet väleihin Rajataajuus 0.8pi:n sijasta 0.2pi, mutta Hertzeissä ihan sama 4 kHz.