2026-09-23T19:03:05Zhttps://helda.helsinki.fi/server/oai/request

oai:helda.helsinki.fi:10138/5735052026-07-23T15:16:07Zcom_10138_18086com_10138_17738col_10138_18093

Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta University of Helsinki, Faculty of Science Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten Yliluoma, Joel 2024 URN:NBN:fi:hulib-202403201558 http://hdl.handle.net/10138/573505 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. In this thesis we study how to implement the one-dimensional fast Fourier transform (FFT) as a computer program in such a way that it works fast on inputs of all sizes. First we walk through the mathematical theory behind the continuous and the discrete Fourier transform (DFT), and study the motivation behind them. We explore both the one-dimensional and the multi-dimensional versions of the DFT. We also study the discrete cosine transform (DCT) and explore its differences to the Fourier transform. After that, we explore various known methods for implementing the fast Fourier transform. We focus especially on the Cooley-Tukey algorithm and its different forms in enough detail, that one can understand both how it works and how it was conceived. We also explore Rader’s and Bluestein’s FFT algorithms. After the theory we implement the DFT and the FFTs using the C++ programming language. We also devise and implement a combined algorithm, which seeks to provide the fastest possible transformation by choosing the optimal combination of algorithms in each case. We use C++20, which is the most recent standard version of C++ at the time of writing. We analyze the speed of the implemented methods, comparing them against each others and also compared to a famous FFT library, FFTW. In addition, we analyze the numeric accuracy of the implementations. Then we analyze the accuracy and applicability of the analysis methods and study the shortcomings and possible approaches for improving the implementations. We also present a simple example application of FFT, where the program attempts to identify the vowel sounds present in a voice sample. The purpose of this thesis is to offer the reader a clear example implementation of all the presented transforms and to thoroughly explore their limitations, weaknesses and strengths. For best value, the reader is expected to understand the basics of calculus and the basics of complex numbers. Especially the sum notation, ∑, and Euler’s formula are vital for understanding the mathematical theory. The computer source code is designed in such way that the reader does not need to know the details of the C++20 standard, or indeed even the C++ language, but experience in C programming will help. fin Helsingin yliopisto University of Helsinki Helsingfors universitet 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 Matematiikan opettaja Teacher in Mathematics Lärare i matematik Matematiikan, fysiikan ja kemian opettajan maisteriohjelma Master's Programme for Teachers of Mathematics, Physics and Chemistry Magisterprogrammet för ämneslärare i matematik, fysik och kemi Nopea Fourier-muunnos – Teoria ja toteutus modernilla C++:lla Fast Fourier Transform – Theory and implementation in modern C++ pro gradu -tutkielmat master's thesis pro gradu-avhandlingar URN:NBN:fi:hulib-202403201558 open.access