20.500.12556/RUL-91002 Primerjava algoritmov za izračun Fourierjeve transformacije s pomočjo sistema ALGator Comparison of Fourier transform algorithms with the help of ALGator system 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. 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. Fourierjeva transformacija kompleksna števila N-ti primitivni koren enote hitra Fourierjeva transformacija diskretna Fourierjeva transformacija Bluesteinov algoritem osnova 2 osnova 4 deljena osnova ALGator 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 true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2017-03-08 14:10:06 2017-03-08 14:10:10 2022-08-09 21:08:38 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 18414 Zorman_Ziga_-_Primerjava_algoritmov_za_izracun_Fourierjeve_transformacije_s_pomocjo_sistema_ALGa.pdf Zorman_Ziga_-_Primerjava_algoritmov_za_izracun_Fourierjeve_transformacije_s_pomocjo_sistema_ALGa.pdf 1 0362213814214F7B4582CD71D03D0CB2 cc3d25155c3b813e774d014b49090f39584947e941a60756beb3d946a21ce533 db129b67-a1b1-11eb-a523-00155dcfd717 20.500.12556/rul/dabe8c10-534c-4356-924d-e5dc8712bb9d https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=94608 Fakulteta za računalništvo in informatiko 0 0 0