Primerjava algoritmov za izračun Fourierjeve transformacije s pomočjo sistema ALGator

ZORMAN, ŽIGA (author), Dobravec, Tomaž (mentor)

V diplomskem delu bomo najprej predstavili osnovne matematične pojme, ki so potrebni za razumevanje delovanja izbranih algoritmov. Potem pa se bomo poglobili v pet različnih implementacij Fourierjeve transformacije. Analizirali bomo njihovo časovno zahtevnost, število kompleksnih steštevanj in število kompleksnih množenj. Zaradi integracije v sistem ALGator smo vse algoritme napisali v programskem jeziku Java. Sistem je namenjen razvijalcem algoritmov, saj omogoča učinkovito in enostavno testiranje ter analizo dobljenih rezultatov. Prav tako bomo med seboj primerjali implementacijo z decimacijo po času ter decimacijo po frekvenci enakega algoritma na rekurziven in iterativen način. Testni podatki, na katerih bomo testirali navedene algoritme, so sestavljeni iz vhodnih podatkov in dejanske rešitve. Za takšno obliko testov smo se odločili zato, da je preverjanje pravilnosti algoritmov čim hitrejše.

• Language: Slovenian
• Keywords: Fourierjeva transformacija, kompleksna števila, N-ti primitivni koren enote, hitra Fourierjeva transformacija, diskretna Fourierjeva transformacija, Bluesteinov algoritem, osnova 2, osnova 4, deljena osnova, ALGator
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2017
• PID: 20.500.12556/RUL-91002
• Publication date in RUL: 08.03.2017

Secondary language

• Language: English
• Title: Comparison of Fourier transform algorithms with the help of ALGator system

Abstract

At first we will explain the required mathematical knowledge which is crucial for the understanding of implemented algorithms in this thesis. Afterwards we will dive into five different implementations of Fourier transform and analyse their time complexity, number of complex additions and multiplications. Because of the integration in ALGator system all algorithms will be implemented in Java programming language. This system is intended to be used by the algorithm developers, because it offers very convenient implementation, effective testing and fast querying and analysis of the acquired results. We will compare decimation in time and decimation in frequency implementations of each algorithm and also its iterative and recursive forms. Testing data on which we will test our algorithms consist of the input data which needs to be transformed and correct transformation result. This way we will be able to verify the correctness of the algorithms as quickly as possible.

• Keywords: Fourier transform, fast Fourier transform, discrete Fourier transform, complex numbers, N-th primitive root of unity, Bluestein's algorithm, radix-2, radix-4, split radix, ALGator