Nopea Fourier-muunnos – Teoria ja toteutus modernilla C++:lla

Tässä tutkielmassa selvitetään, kuinka voidaan toteuttaa tietokoneohjelmana sellainen nopea yksiulotteinen Fourier-muunnos (FFT), joka toimii nopeasti kaiken kokoisilla syötteillä. Tutkielman alussa käydään läpi matemaattista teoriaa sekä perusmuotoisesta että diskreetistä Fourier-muunnoksesta (DFT), ja selvitetään, mikä niiden päämäärä on. Diskreetistä Fourier-muunnoksesta käsitellään sekä yksiulotteinen että moniulotteinen versio. Myös diskreettiä kosinimuunnosta (DCT) käsitellään ja tutkitaan sen eroja Fourier-muunnokseen. Tämän jälkeen tutkitaan erilaisia tunnettuja menetelmiä toteuttaa diskreetti Fouriermuunnos niin, että se toimii nopeasti. Erityisesti Cooleyn-Tukeyn menetelmää ja sen eri muotoja tutkitaan sellaisessa tarkkuudessa, että sen toimintaperiaatteen sekä sen syntyyn johtaneen ajatusketjun voi ymmärtää. Lisäksi käsitellään Raderin sekä Bluesteinin FFT-menetelmiä. Teorian käsittelyn jälkeen DFT sekä esitetyt FFT-algoritmit toteutetaan C++-ohjelmointikielellä. Lisäksi laaditaan ja toteutetaan yhdistetty algoritmi, joka pyrkii tapauskohtaisesti valitsemaan optimaalisen yhdistelmän algoritmeja saavuttaakseen nopeimman mahdollisen muunnoksen. C++-kielestä käytetään kirjoitushetkellä tuoreinta standardiversiota, C++20. Toteutettujen menetelmien nopeutta tutkitaan ja verrataan suhteessa toisiinsa sekä tunnettuun FFT-kirjastoon, FFTW. Lisäksi tutkitaan menetelmien laskentatarkkuutta. Lopuksi analysoidaan vertailumenetelmien tarkkuutta ja pätevyyttä, ja pohditaan toteutuksen puutteita sekä mahdollisia parannuskeinoja. Tutkielmassa esitetään myös FFT-muunnoksesta esimerkkisovellus, joka pyrkii selvittämään puheääninäytteestä sen sisältämät vokaaliäänteet. Tutkielman päämääränä on tarjota lukijalle selkeä esimerkkitoteutus kaikista esitetyistä muunnoksista sekä käsitellä kattavasti niiden rajoituksia, heikkouksia ja vahvuuksia. Parhaan hyödyn saamiseksi teoriasta lukijan tulisi ymmärtää differentiaali- ja integraalilaskennan perusteet sekä kompleksilukujen perusteet. Erityisesti summamerkinnän, ∑, sekä Eulerin lauseen ymmärtäminen on tärkeää matemaattisen teorian kannalta. Tietokonetoteutuksen lähdekoodi on laadittu sellaiseksi, ettei sen ymmärtämiksi tarvitse tuntea C++20-standardin yksityiskohtia, tai edes C++-kieltä kunnolla. Kokemus C-ohjelmoinnista on kuitenkin hyödyksi koodia luettaessa.

Grantor dc:publisher

Helsingin yliopisto

Year dc:date.issued

2024

Author dc:creator

• Yliluoma, Joel

Contributors dc:contributor

• Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta
• University of Helsinki, Faculty of Science
• Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten

• nopea Fourier-muunnos
• C++20
• Cooleyn-Tukeyn algoritmi
• Raderin algoritmi
• Bluesteinin algoritmi
• C++
• optimointi
• optimization
• fftw
• fft
• dft
• dct
• pienimmän neliösumman menetelmä
• Bluestein
• Cooley-Tukey
• Rader
• algorithm
• fftw3

Language dc:language.iso

fin

Identifier URI

URN:NBN:fi:hulib-202403201558

OAI identifier oai:identifier

oai:helda.helsinki.fi:10138/573505