Iets dat de snelle Fourier-transformatie wordt genoemd, draait nu op je mobiele telefoon. de FFT, zoals het bekend is, is een signaalverwerkingsalgoritme dat u meer gebruikt dan u denkt. Het is, volgens de titel van een onderzoekspaper, "een algoritme dat het hele gezin kan gebruiken."

Alexander Stoytchev - een universitair hoofddocent elektrische en computertechniek aan de Iowa State University, die ook is aangesloten bij het Virtual Reality Applications Center van de universiteit, zijn afstudeerprogramma Human Computer Interaction en de afdeling informatica - zegt dat het FFT-algoritme en zijn inverse (bekend als de IFFT) de kern vormen van signaalverwerking.

En, als zodanig, "Dit zijn algoritmen die de digitale revolutie mogelijk hebben gemaakt, " hij zei.

Ze maken deel uit van het streamen van muziek, mobiel bellen, internetten of een selfie maken.

Het FFT-algoritme werd in 1965 gepubliceerd. Vier jaar later onderzoekers ontwikkelden een veelzijdiger, gegeneraliseerde versie genaamd de chirp z-transform (CZT). Maar een vergelijkbare generalisatie van het inverse FFT-algoritme is al 50 jaar onopgelost.

Tot, dat is, Stoytchev en Vladimir Sukhoy - een doctoraalstudent in de staat Iowa met een co-major in elektrotechniek en computertechniek, en menselijke computerinteractie - werkten samen om het lang gezochte algoritme te bedenken, de inverse chirp z-transform (ICZT) genoemd.

Zoals alle algoritmen, het is een stapsgewijs proces dat een probleem oplost. In dit geval, het brengt de uitvoer van het CZT-algoritme terug naar zijn invoer. De twee algoritmen lijken een beetje op een reeks van twee prisma's:de eerste scheidt de golflengten van wit licht in een spectrum van kleuren en de tweede keert het proces om door het spectrum terug te combineren tot wit licht. Stoytchev legde het uit.

Stoytchev en Sukhoy beschrijven hun nieuwe algoritme in een paper dat onlangs online is gepubliceerd door Wetenschappelijke rapporten , een tijdschrift voor natuuronderzoek. Hun paper laat zien dat het algoritme overeenkomt met de computationele complexiteit of snelheid van zijn tegenhanger, dat het kan worden gebruikt met exponentieel afnemende of groeiende frequentiecomponenten (in tegenstelling tot de IFFT) en dat het is getest op numerieke nauwkeurigheid.

Stoytchev zei dat hij op het idee stuitte om te proberen het ontbrekende algoritme te formuleren terwijl hij op zoek was naar analogieën om de afgestudeerde studenten in zijn "Computational Perception" -cursus te helpen de snelle Fourier-transformatie te begrijpen. Hij las veel van de signaalverwerkingsliteratuur en kon niets vinden over de inverse van de gerelateerde chirp z-transform.

"Ik werd nieuwsgierig, "zei hij. "Is dat omdat ze het niet konden uitleggen, of is het omdat het niet bestaat? Het bleek niet te bestaan."

En dus besloot hij te proberen een snel invers algoritme te vinden.

Sukhoy zei dat het inverse algoritme een moeilijker probleem is dan het origineel, forward-algoritme en dus "hadden we een betere precisie en krachtigere computers nodig om het aan te vallen." Hij zei ook dat een sleutel was om het algoritme te zien binnen het wiskundige kader van gestructureerde matrices.

Zelfs dan, er waren veel computertests "om te laten zien dat alles werkte - we moesten onszelf ervan overtuigen dat dit kon."

Er was moed voor nodig om het probleem aan te pakken, zei James Oliver, directeur van het Student Innovation Center van Iowa State en voormalig directeur van het Virtual Reality Applications Center van de universiteit. Stoytchev en Sukhoy erkennen Oliver in hun paper "voor het creëren van de onderzoeksomgeving waarin we dit werk de afgelopen drie jaar konden voortzetten."

Oliver zei dat Stoytchev zijn steun verdiende voor een wiskundige en computationele uitdaging die al 50 jaar niet was opgelost:"Alex heeft altijd indruk op me gemaakt met zijn passie en toewijding om grote onderzoeksuitdagingen aan te gaan. Onderzoek brengt altijd risico's met zich mee en er is moed voor nodig om jarenlang hard te werken aan een fundamenteel probleem. Alex is een begaafd en onverschrokken onderzoeker."