Die schnelle Fourier-Transformation (FFT) ist in vielen Geräten aktiv, auch auf Ihrem Handy. Im Bereich dieses bekannten Signalverarbeitungsalgorithmus ist es nun nach 50 Jahren der Suche zu einem Durchbruch gekommen.

Alexander Stoytchev und seinem Doktoranden Vladimir Sukhoy von der Abteilung für Elektro- und Informationstechnik an der Iowa State University gelang eine mathematische Sensation. Nach dem 1805 von Carl Friedrich Gauß grundlegend vorgestellten FFT-Algorithmus gelang Cooley und Tukey 1965 eine eingeschränkte, praktisch gut einsetzbare Variante des FFT-Algorithmus. Die FFT ist gegenüber der diskrete Variante (DFT) deutlich schneller. Auch eine inverse Funktion, die IFFT, wurde entwickelt, welche die Resultate der FFT wieder in dessen Ausgangswerte zurückverwandeln kann. Vier Jahre nach der FFT wurde eine vielseitigere, verallgemeinerte Version namens Chirp-Z-Transformation (CZT) entwickelt. Aber eine ähnliche Verallgemeinerung des inversen FFT-Algorithmus, die ICZT, blieb erstaunliche 50 Jahre lang ungelöst.

Stoytchev und Sukhoy haben die letzten Jahre an der Entwicklung der lang ersehnten inversen Chirp-Z-Transformation (ICZT) gearbeitet. Auch hier gibt die ICZT mit den Resultaten der CZT dessen Input zurück. Im Prinzip arbeiten die beiden Algorithmen ähnlich wie zwei Prismen: Das erste Prisma trennt die Wellenlängen des Eingangslichts nach Wellenlänge in ein Spektrum von Farben auf und das zweite Prisma kehrt den Prozess um.
 
Drei verschiedene Arten von Frequenzkomponenten: (a) exponentiell abklingend, (b) mit fester Größe und (c) exponentiell wachsend. FFT und IFFT verwenden nur Frequenzkomponenten fester Größe. Bild: A. Stoytchev und V. Sukhoy, Scientific Reports.

Stoytchev und Sukhoy beschreiben ihren neuen Algorithmus in einem Artikel für die Fachzeitschrift Scientific Reports. Ihr Beitrag zeigt, dass der Algorithmus der Komplexität oder Geschwindigkeit seines Gegenstücks entspricht, und dass er mit exponentiellen Frequenzkomponenten verwendet werden kann (im Gegensatz zur IFFT). Außerdem wurde er auf numerische Genauigkeit getestet.

Stoytchev stolperte über das Problem im Rahmen seines Kurses „Computational Perception“. Bei der Literaturrecherche konnte er nichts über die Umkehrung der CZT finden. Dabei stellte sich heraus, dass es eine ICZT schlicht nicht gab.
Der inverse Algorithmus war ein härteres Problem als die CZT. Zur Lösung brauchte es bessere Präzision und leistungsfähigere Computer. Der Schlüssel war, den Algorithmus innerhalb des mathematischen Rahmens von strukturierten Matrizen zu sehen.

Quelle: Iowa State University