Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Implementation of Single-Point Discrete Fourier Transform on two dimensional data
Organization Unit
Authors
  • Nicolas Spielmann
Supervisors
  • Michael Hanspeter Böhlen
  • Muhammad Saad
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2019
Abstract Text The discrete Fourier transform is an algorithm that is used to transform the time representations of a function into its frequency components under the assumption that this given function is periodic. It is the base of many modern applications that use signal processing. Currently the fast Fourier transform algorithm, which reduces the run time of the discrete Fourier transform from O(n^2) to O(n*log(n)) is the fastest way to compute the Fourier transform. In order to calculate the Fourier transform of two dimensional data, the algorithm will just be used to transform all rows and then transform all columns. One use case of the two dimensional algorithm is to generate dirty sky images form radio astronomy data. In this thesis a faster algorithm to compute the single point two dimensional Fourier transform is described and it is mathematically proofed. This new algorithm will describe all fields of the Fourier transform with its first row or column of the transformed grid. Furthermore the importance of Fourier transform in stream pipelines is considered and this new algorithm is implemented using the stream processing environment Apache Flink. After the initial implementation of the new algorithm, some stream specific optimization have been made to the algorithm. While computing the Fourier Transform, a lot of computations are made a multiple time. This fact is used to further improve the algorithm. These different Algorithms are then evaluated using artificially generated source files to determine the run time. This shows that the new algorithm, for the biggest grid tested, is 60 times faster than the normal FFT implementation. With the small stream specific enhancements, the algorithm is even up to 120 times faster for the largest grid tested.
Zusammenfassung Die diskrete Fourier Transformation ist ein Algorithmus, der benutzt wird, um aus Datenpunkten zu verschiedenen Zeiten die Frequenz-Komponenten eines Signals zu ermitteln, unter der Annahme das Signal sei periodisch. Sie ist die Basis vieler modernen Applikationen die Signalverarbeitung machen. Zurzeit ist die schnelle Fourier Transformation, welche die Laufzeit von der diskreten Fourier Transformation von O(n^2) zu O(n*log(n)) reduziert der schnellste Weg die Fourier Transformation zu berechnen. Um die Fourier Transformation von zwei dimensionalen Daten zu berechnenen, wird der eindimnensional Algorithmus benutzt um zuerst alle Reihen und dann anschliessend alle Spalten zu transformieren. Eine Anwendung des zweidimensionalen Algorithmus ist es, aus Radioastronomiedaten verunreinigte Bilder des Himmels zu machen. In dieser Arbeit wird ein schnellerer Algorithmus für die Berechnung der zwei dimensionalen Fourier Transformation für einen Punkt beschrieben und mathematisch bewiesen. Der neue Algorithmus wird alle Ergebnisfelder der Transformation durch die Felder der Transformation der ersten Reihe oder der ersten Spalte ausdrücken können. Weiteres wird die Wichtigkeit der Fourier Transformation in Stream Pipelines berücksichtigt und der neue Algorithmus wurde in der Stream Processing Umgebung Apache Flink implementiert. Nachdem der ursprüngliche Algorithmus implementier wurde, wurden einige Stream spezifischen Anpassungen gemacht, um die Performance zu optimieren. Währendem die Fourier Transformation berechnet wird, werden viele Rechnungen mehrmals gemacht. Wir haben diesen Fakt benutzt, um den Algorithmus weiter zu verbessern. Diese verschiedenen Algorithmen sind dann evaluiert worden mit einem künstlich generierten Datenset um die Laufzeit jener zu bestimmen. Das ergab, dass die ursprüngliche Implementation des neuen Algorithmus für das grösste Raster 60-mal schneller ist als die normale FFT Implementation. Mit kleinen stream spezifischen Anpassungen ist der Algorithmus sogar bis zu 120-mal schneller für das grösste getestete Raster.
PDF File Download
Export BibTeX