Diskreetti Fourier-muunnos ja FFT

Tänään käsiteltiin Fourier-muunnos (kappale 3) loppuun. Myös ensi viikon välikokeen alue on kappaleen kolme loppuun. Kannattanee vilkaista myös seuraavat viikkoharjoitukset, koska ne käsittelevät samaa asiaa.

Ensimmäisellä tunnilla tarkasteltiin 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ästä mainittiin kaksi sovellusta. Ensimmäinen niistä 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))

Toisena esimerkkinä oli dekonvoluutio, eli kysymys mikä olisi konvoluutiolle käänteinen operaatio. Jos siis tiedetään h ja y yhtälöstä

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

niin kuinka voidaan ratkaista x(n)? Ratkaisu löytyy taajuustasossa, koska

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

joten

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

Tästä on hyötyä 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.

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).