R11 - Paperi #6 -- kommentteja

Kurssin loppupuoliskolla käsittellään ilmiöitä, joita syntyy kun suotimen siirretään "matemaattisen täydellisestä, symbolisesta" maailmasta kohti "epätäydellistä, epätarkkaa".

Luku pi on irrationaaliluku, voimme kirjoittaa sen yhdellä symbolilla, joka on matemaattisen tarkka. Mutta jos haluamme kirjoittaa sen murtoluvuksi tai tallettaa tietokoneen muistiin, joudumme käyttämään pyöristystä. Pyöristykset tulevat konkreettisiksi erityisesti käytettäessä pientä bittimäärää.

Tämän viikon laskareissa pääpaino on diskreetin Fourier-muunnosta nopeasti laskevassa algoritmissa, esimerkkinä radix-2 DIT FFT. Tätä kysytään myös välikokeessa.

Toinen esimerkki on signaalin alas- ja ylösnäytteistys digitaalisesti ilman D/A, A/D-muuntimia.

Tehtävä 1, pohjustus.

Katsotaan ensin määritelmän mukaista diskreettiä Fourier-muunnosta ja erityisesti siinä esiintyvää termiä W_N. Nyt jos N=4, niin W_N^kn-pisteet ovat tasavälein yksikköympyrällä.



Nyt voidaan siis vaikkapa käsin laskea DFT jonolle x[n] = {_2_, 3, 5, -1}.
Jono x[n] on neljä merkkiä pitkä, N = 4. Tällöin myös muunnos X[k] on neljä merkkiä pitkä: X[0], X[1], X[2], X[3]. Kukin X[k] lasketaan summana neljästä termistä x[n]W_N^kn. Alla laskettuna X[0] ja X[1]. Laske X[2] ja X[3].



Jos muunnettava jono x[n] on reaaliarvoinen (niinkuin yleensä onkin), niin muunnoksella X[k] on tiettyjä symmetrisiä ominaisuuksia:



DFT:ä tarvitaan siis vaikkapa signaalin taajuusestimoinnissa. Jatkuvasta signaalista voidaan ikkunafunktiolla leikata pala, esim. 256 merkkiä pitkä. Hamming-ikkuna (kuten Hann, Blackman, ...) vaimentavat pätkän alun ja lopun nollaan, jotta spektriin ei tule "säröä" epäjatkuvuudesta johtuen.



Kun tällä lasketaan DFT-256, niin taajuusakseli 0..f_t jaetaan 256 palaan. Taajuusresoluutioksi f_T=8000 Hz tulee noin 40 Hz. Olennaista on siis huomata, että jälleen näemme signaalista vain kaistan 0..f_T/2 eli ensimmäiset 129 DFT:n arvoa.



Kaikki tämä siis voitaisiin laskea kynällä. Lisäksi voidaan osoittaa, että joka kerta lasketaan jo aiemmin laskettuja x[n]W_N-termejä. FFT-algoritmit laskevat DFT:tä yhtä tarkasti mutta "viisaammin", jolloin laskuoperaatioiden määrä putoaa huomattavasti. Tätä esitetään O-notaatiolla. Määritelmän mukaisessa DFT:ssä laskuoperaatoita on O(N^2) kun taas FFT:ssä yleisesti O(N log_2 N).



Esitellään radix-2 DIT FFT, jonka algoritmi voidaan visualioida "virtauskaavioksi". DFT-muunnettava jono x[n] asetaan tietyssä järjestyksessä vasempaan reunaan, lasketaan kerros kerrokselta oikealle päin kunnes oikeassa reunassa on DFT:n arvot X[k].



Tässä algoritmissa x[n] järjestetään bittikäänteiseen järjestykseen. Esim. kymmenjärjestelmän luku 11 on 1011, niin bittikäännetty järjestys on 1101, jota vastaa kymmenkannan 13. Kun N=4 ja bittejä siis b=2, koska 2^b = 2^2 = 4, niin {0, 1, 2, 3} ~ {00, 01, 10, 11} --> {00, 10, 01, 11} ~ {0, 2, 1, 3}. Tämä on "desimointia". Lasketaan kompleksiset kertoimet W_N^s. Tämän jälkeen taso tasolta eteenpäin. Visuaalinen ilme on peräisin "perhosyhtälöistä".



Esimerkkimateriaalissa on annettu esimerkki tilanteesta N=8. Vertaile N=4 ja N=8. Miltä näyttäisi N=16. Tai N=256?



Tehtävä 2, pohjustus

Monen näytteenottotaajuuden (multirate) tekniikoita ja järjestelmiä voidaan tarvita vaikkapa signaalin näytteenottotaajuuden muuttamisessa käyttämättä D/A-A/D-muunnosparia, joka luo aina virhettä tai kun halutaan analysoida tai käsitellä signaalin eri taajuuskaistoja (suodinpankit, filter bank), esim. audiokoodauksessa kriittiset kaistat. Uudelleennäytteistys voi toki tehdä vaikkapa splineillä tai Lagrangen kertoimilla - digitaalinen sämpläys on DSP-juttu. Multirate-järjestelmillä voidaan toteuttaa suotimia tehokkaammin kuin "suoralla toteutuksella".

Alasnäytteistyksessä vähennettään näytteenottotaajuutta jollain kokonaisluvulla. Aikatasossa otetaan vain joka M:s näyte. Taajuuspuolelta nähdään, että uhkana on signaalin vierastuminen.



Ylösnäytteistyksessä näytteenottottaajuutta kasvatetaan kokonaisluvulla L. Aikapuolella jokaisen alkuperäisen näytteen väliin sijoitetaan L-1 kpl nollia. Tämä tuottaa signaaliin korkeita, ylimääräisiä taajuuksia ("image").



Uudelleennäytteistyksessä voidaan luoda L/M-suhde, jonka lisäksi tarvitaan sopiva alipäästösuodatus toisaalta poistamaan "image" ja vierastumisen vaara.



Tehtävä 2 on pieni esimerkki alas- ja ylösnäytteistyksen vaikutuksesta taajuustasossa. Muista, että kuten analogisen signaalin näytteistyksessä kuin myös tässäkin, mitään korkeita taajuuksia ei katoa vaan ne mahdollisesti laskostuvat matalille taajuuksille.

Alla olevassa ratkaisumallissa harjaannutetaan matemaattista silmää käyttämällä alasnäytteistyksen matemaattista kaavaa.



Ylösnäytteistyksessä samoin, mutta tässä tapauksessa hieman helpompi. Huomaa, että kun ensin pudotetiin 1/3-osaan ja sitten nostettiin 3-kertaiseksi, niin lopullinen näytteenottotaajuus on sama kuin alussa. Kaistan pi/3..2pi/3 lisäksi on tullut komponentit 0..pi/3 ja 2pi/3..pi -kaistoille. Nämä voidaan nyt erottaa LP-, BP- ja HP-suotimilla H_0, H_1 ja H_2.