De snelle Fourier-transformatie (FFT) is op veel apparaten actief, zelfs op uw handy. Op het gebied van dit bekende signaalverwerkings-algoritme is het nu, na 50 jaar onderzoek, tot een doorbraak gekomen.

Alexander Stoytchev en zijn promovendus Vladimir Sukhoy van het Department of Electrical and Information Technology aan de Iowa State University zijn verantwoordelijk voor een wiskundige sensatie. Na de door Carl Friedrich Gauss in 1805 geïntroduceerde basisversie van het FFT-algoritme slaagden Cooley en Tukey in 1965 erin een beperkte, praktisch bruikbare variant van het FFT-algoritme op te stellen. De FFT is veel sneller dan de discrete versie (DFT). Er is ook een inverse functie ontwikkeld, de IFFT, die de resultaten van de FFT weer omzet in de oorspronkelijke waarden. Vier jaar na de FFT werd een veelzijdiger algemene versie met de naam Chirp-Z Transformation (CZT) ontwikkeld. Maar een vergelijkbare generalisatie van het inverse FFT-algoritme, de ICZT, bleef een verbazingwekkende 50 jaar lang een vrome wens.

Stoytchev en Sukhoy hebben de afgelopen jaren gewerkt aan de ontwikkeling van de langverwachte omgekeerde Chirp-Z-transformatie (ICZT). Deze ICZT zet de resultaten van de CZT weer om in de oorspronkelijke waarden. In principe werken de twee algoritmen op dezelfde manier als twee prisma’s: het eerste prisma splitst het invallende licht in een kleurenspectrum en het tweede prisma keert het proces om.
 
Drie verschillende soorten frequentiecomponenten: (a) exponentieel afnemend, (b) met constante grootte en (c) exponentieel toenemend. FFT en IFFT kunnen uitsluitend overweg met frequentiecomponenten met constante grootte. Afbeelding: A. Stoytchev en V. Sukhoy, Scientific Reports.

Stoytchev en Sukhoy beschrijven hun nieuwe algoritme in een artikel in het vaktijdschrift Scientific Reports. Ze tonen daarin aan dat het algoritme een vergelijkbaree complexiteit of snelheid als zijn tegenhanger heeft, en dat het kan omgaan met exponentiële frequentiecomponenten (in tegenstelling tot IFFT). Het is ook getest op numerieke nauwkeurigheid.

Stoytchev stuitte op het probleem als onderdeel van zijn cursus Computational Perception. Tijdens literatuuronderzoek kon hij niets vinden over een inverse CZT – deze bleek domweg niet te bestaan.

Het inverse algoritme vormde een grotere uitdaging dan de CZT. Voor de oplossing waren uiterste precisie en krachtige computers nodig. De sleutel tot het succes was het algoritme te onderkennen binnen het wiskundige kader van gestructureerde matrices.

Bron: Iowa State University