DFT:n sovelluksia ja FFT

Tänään käsiteltiin Fourier-muunnos (kappale 3) loppuun ja vilkaistiin seuraavan kappaleen alkua
pikaisesti.

Ennen itse asiaa tehtiin pikainen ekskursio kahteen signaalinkäsittelyn alan koneoppimiskilpailuun. Luennoijanne osallistui viime vuonna tänne (Huttunen et al.) ja tänne (Team #251), joista molemmissa tulos oli "best performer". Nyt kehitteillä on osallistuminen tähän kilpailuun. Aiheet ovat nimenomaan signaalinkäsittelyyn liittyviä, koska kaikissa datan määrä on suuri. Esimerkkinä mainittiin että viimeisimmän kilpailun datan pystyy kyllä lataamaan Matlabiin, mutta esimerkiksi matriisin transponointi saa koneen jumiin.

Tämän jälkeen siirryttiin tarkastelemaan Fourier-muunnoksen ominaisuuksia. Ominaisuuksista tutustuttiin lähemmin siirtoon ajassa (esim. laske signaalin x(n+20) muunnos, kun tiedetään x(n):n muunnos) sekä konvoluution muunnokseen (DFT muuntaa konvoluution kertolaskuksi, eli x(n)*y(n) -> X(n)Y(n)). Tämä on perustana mm. dekonvoluutiolle joka on konvoluutiolle käänteinen operaatio. Menetelmää käytettiin mm. Hubble-teleskoopin alkuaikoina, jolloin yhdessä peilissä olleen hiontavirheen vuoksikuvat olivat sumuisia. Kuvantamisprosessia voidaan nimittäin mallintaa (kaksilulotteisella) konvoluutiolla

y(n,m) = h(n,m) * x(n,m),

missä x on todellinen näkymä, y on havaittu sumuinen kuva, ja h on linssin impulssivaste (nk. point spread function; PSF). Yhtälössä y ja h ovat tunnettuja, ja tehtävänä on ratkaista x? Ratkaisu löytyy taajuustasossa, koska

Y(n,m) = H(n,m) X(n,m),

joten (Matlabin syntaksilla ilmaistuna):

x(n,m) = ifft (Y(n,m) ./ H(n,m)).

Toisena esimerkkinä tarkasteltiin kappaleen 6 esimerkkiä kameran liikkeen aiheuttamasta epäterävyydestä, ja havaittiin terävyyden paranevan yksinkertaisellakin dekonvoluutiolla (arvaamalla h).

Dekonvoluutiosta on hyötyä yleisemminkin lineaarisen kanavan aiheuttaman häiriön poistossa. Jos tiedetään signaalin x kulkeneen kanavan h läpi, voidaan vastaanotetusta mittaustuloksesta y päätellä x, jos meillä on joku käsitys kanavasta h. Esimerkkinä tästä mainittiin langattoman tiedonsiirtokanavan estimointi ja sen aiheuttaman vääristymän kompensointi.

Toinen menetelmän tuottama etu on että Fourier-muunnoksen (käytännössä FFT:n) avulla voidaan laskea konvoluutio kaavasta (Matlabin syntaksilla ilmaistuna):

conv(x,y) = ifft(fft(x) .* fft(y))

Luennon lopuksi käsiteltiin nopeaa Fourier-muunnosta eli FFT:tä, joka on vain nopeampi tapa toteuttaa diskreetti Fourier-muunnos (DFT). FFT perustuu signaalin jakamiseen lyhyempiin pätkiin, jotka muunnetaan jakamalla ne edelleen rekursiivisesti kahtia. Rekursio päättyy, kun muunnoksen pituus on 1, jolloin muunnosta ei tarvitse enää tehdä. 1-ulotteisen vektorin tapauksessa muunnosmatriisi on yksinkertaisesti F = [1], joka tarkoittaa pelkkää ykkösellä kertomista eikä sitä tarvitse tehdä. Lyhyemmistä vektoreista saadaan koostettua pidemmät vektorit kaavoilla (3.3) ja (3.4).

Tunnin lopulla vilkaistiin Z-muunnosta, joka on puuttuva linkki suodatuksen ja Fourier-muunnoksen välillä.