Elementare Darstellung der schnellen Fouriertransformation

Zusammenfassung

Es wird eine einfache und durchsichtige Darstellung der schnellen Fouriertransformation gegeben. Unter Verwendung der grundlegenden Idee von Theilheimer wird gezeigt, daß sich die zeilenpermutierte Transformationsmatrix in das Produkt zweier Blockmatrizen zerlegen läßt, derart, daß sich die Fouriertransformation der OrdnungN=2n auf zwei Transformationen der Ordnungn zurückführen läßt. Die rekursive Anwendung dieser Tatsache führt auf einen sehr einfachen Prozeß, die gegebenen Daten zu transformieren. Im Vergleich zu bekannten Realisierungen des Algorithmus von Cooley-Tukey benötigt die hier präsentierte Version nur am Schluß den Prozeß der Bitinversion, um noch die richtige Zuordnung vorzunehmen.

Abstract

A simple and transparent presentation of the fast Fourier transform is given. By applying the fundamental idea of Theilheimer it is shown that the matrix of the linear transformation, after a suitable permutation of its rows, can be written as the product of two blockmatrices, such that the Fourier transformation of the orderN=2n can be reduced to two Fourier transformations of the ordern each. The recursive application of this fact leads to a very simple process of transforming the given data. In comparison to known computer programs for the Cooley-Tukey algorithm the version presented here needs the process of bitinversion only at the very end to rearrange the final data into the proper order.