Alexander Stoytchev van de Iowa State University zegt dat het een van de 'meest populaire en nuttige' algoritmen is die er zijn, hoewel de meesten van ons er nog nooit van hebben gehoord.

Maar, als je een mobiele telefoon hebt gebruikt, internetten of een medisch beeld nodig hadden, je hebt geprofiteerd van de snelle Fourier-transformatie (FFT).

De transformatie en zijn inverse (bekend als de IFFT) zijn sinds 1965 in gebruik. in uw mobiele telefoon wordt de FFT gebruikt om het ontvangen signaal van het basisstation (of zendmast) te analyseren. De IFFT lost het omgekeerde probleem op:het synthetiseert het signaal dat je telefoon naar het basisstation stuurt.

1969, onderzoekers ontwikkelden een bruikbaarder, gegeneraliseerde versie van de FFT bekend als de chirp z-transform (CZT). Maar niemand had een algemene versie van het IFFT bedacht. Het was een 50 jaar oude puzzel in signaalverwerking.

Dat is, tot afgelopen herfst toen twee ingenieurs van de staat Iowa - Stoytchev en Vladimir Sukhoy - in een onderzoekspaper aankondigden dat ze een oplossing in gesloten vorm hadden bedacht voor de inverse chirp z-transform (ICZT) en een snel algoritme om het te berekenen. (Het papier wekte veel interesse in de signaalverwerkingsgemeenschap, met meer dan 26, 000 toegangen sinds oktober.)

Nu melden Stoytchev - een universitair hoofddocent elektrotechniek en computertechniek die ook verbonden is aan het Virtual Reality Applications Center van de universiteit - en Sukhoy - een docent elektrotechniek en computertechniek - nieuwe onderzoeksresultaten over hun algoritme.

In een artikel dat zojuist online is gepubliceerd door Wetenschappelijke rapporten , een tijdschrift voor natuuronderzoek, de twee laten zien hoe hun algoritme functioneert "op de eenheidscirkel, " wat verwijst naar een speciaal geval van zijn parameters. (Hun vorige paper benadrukte alleen operaties "buiten de eenheidscirkel.")

Het artikel beschrijft hoe het algoritme kan werken met frequentiecomponenten die worden gegenereerd door meetpunten van de eenheidscirkel in het complexe vlak. Deze punten vormen een contour die bekend staat als de chirp-contour. In tegenstelling tot het IFFT, die alleen kan werken met bemonsteringspunten op gelijke afstand die de eenheidscirkel volledig bedekken, het ICZT-algoritme kan werken met contouren die slechts een fractie van de eenheidscirkel beslaan. Het kan ook werken met contouren die zich om de cirkel wikkelen en meerdere omwentelingen uitvoeren. Dit maakt het gebruik van bepaalde (niet-orthogonale) frequentiecomponenten mogelijk, die een van de belangrijkste beperkingen van het IFFT opheft en zou kunnen leiden tot een beter spectrumgebruik.

Het document identificeert de parameterwaarden waarvoor het algoritme numeriek nauwkeurig is en waarvoor niet, en beschrijft hoe de nauwkeurigheid ervan als functie van de parameters kan worden geschat. (Technische opmerking:het laat zien dat de singulariteiten van de ICZT van grootte n gerelateerd zijn aan de elementen van de Farey-reeks van orde n-1. Dit is een interessant verband omdat Farey-reeksen vaak voorkomen in de getaltheorie.)

Het blad laat zien dat, op de eenheidscirkel, het ICZT-algoritme bereikt een hoge nauwkeurigheid met alleen 64-bits drijvende-kommagetallen en vereist geen extra numerieke precisie, waardoor het gemakkelijker te implementeren is. Het rapporteert dat het algoritme goed kan combineren met het bestaande CZT-algoritme om back-to-back signaalanalyse en signaalsynthese uit te voeren. En het laat zien dat het algoritme snel is (het werkt in wat bekend staat als O(n log n) tijd).

"Dit algoritme is algemener dan het IFFT, maar behoudt dezelfde snelheid, ' zei Stoytchev.

Dat is goed nieuws voor de ingenieurs die werken aan het oplossen van allerlei uitdagingen op het gebied van signaalverwerking:

"Toepassingsdomeinen die hiervan kunnen profiteren, " schreven de ingenieurs van de staat Iowa in de krant, "omvat signaalverwerking, elektronica, medische beeldvorming, radar, sonar, draadloze communicatie, en anderen."