Diskreetti Fourier-muunnos DFT sekä nopea Fourier-muunnos FFT

Abstract

Tässä tutkielmassa käsitellään Diskreettiä Fourier-muunnosta sekä Nopeaa Fourier-muunnosta, joka on tehokkaampi algoritmi diskreettejä Fourier-muunnoksia varten. Diskreettiä Fourier-muunnosta varten käsitellään lisäksi tarvittavat taustatiedot Fourier-sarjoista. Fourier-sarja on matemaattinen työkalu, jonka avulla jaksollinen funktio voidaan ilmaista eritaajuisten sini- ja kosinifunktioiden summana. Fourier-sarja toimii lähtökohtana Fourier-muunnokselle, josta on olemassa jatkuva sekä diskreetti versio. Jatkuvaa Fourier-muunnosta hyödynnetään lähinnä matematiikan ja fysiikan teoreettisissa sovelluksissa. Reaalimaailman sovelluksissa käytetään käytännössä aina diskreettiä versiota, jota tässä tutkielmassa käsitellään. Diskreetti Fourier-muunnos eli DFT on Fourier-analyysissä käytetty työkalu, jonka avulla ajan suhteen diskreetti ja äärellinen signaali saadaan esitettyä taajuuden suhteen. Tämän avulla voidaan selvittää, mitä taajuuksia signaali sisältää ja mikä on kunkin taajuuden amplitudi. Diskreettiä Fourier-muunnosta hyödynnetään laajasti käytännön sovelluksissa, mutta se on algoritmina kuitenkin hidas. Tämän vuoksi reaalimaailman sovelluksissa hyödynnetäänkin lähes aina nopeaa Fourier-muunnosta eli FFT:tä, jonka avulla päästään samaan lopputulokseen käyttäen huomattavasti tehokkaampia algoritmeja. FFT:n vaatimien laskutoimitusten määrä on vain murto-osa verrattuna DFT:hen, mikä korostuu entisestään näytteiden määrän kasvaessa suureksi. FFT:n tehokkuuden vuoksi sitä käytetäänkin laajasti erilaisia signaalinkäsittelyä vaativissa sovelluksissa, kuten äänen- ja kuvankäsittelyssä sekä lääketieteellisessä kuvantamisessa.