Ingeniører løser 50 år gammelt puslespil inden for signalbehandling

Noget kaldet den hurtige Fourier-transformation kører på din mobiltelefon lige nu. FFT, som det er kendt, er en signalbehandlingsalgoritme, som du bruger mere, end du er klar over. Det er, ifølge titlen på en forskningsartikel, "en algoritme, som hele familien kan bruge."

Alexander Stoytchev - en lektor i elektro- og computerteknik ved Iowa State University, som også er tilknyttet universitetets Virtual Reality Applications Center, dets Human Computer Interaction-graduate-program og afdelingen for datalogi - siger FFT-algoritmen og dens inverse (kendt som IFFT) er kernen i signalbehandling.

Og, som sådan, "Dette er algoritmer, der gjorde den digitale revolution mulig, " han sagde.

De er en del af streaming af musik, foretager et mobiltelefonopkald, surfer på internettet eller tager en selfie.

FFT-algoritmen blev offentliggjort i 1965. Fire år senere, forskere udviklede en mere alsidig, generaliseret version kaldet chirp z-transform (CZT). Men en lignende generalisering af den inverse FFT-algoritme har været uløst i 50 år.

Så længe, det er, Stoytchev og Vladimir Sukhoy - en Iowa State ph.d.-studerende med hovedfag i elektro- og computerteknik, og menneskelig computerinteraktion - arbejdede sammen for at finde frem til den længe søgte algoritme, kaldet den inverse chirp z-transform (ICZT).

Som alle algoritmer, det er en trin-for-trin proces, der løser et problem. I dette tilfælde, det kortlægger output fra CZT-algoritmen tilbage til dets input. De to algoritmer er lidt som en serie af to prismer - den første adskiller bølgelængderne af hvidt lys i et spektrum af farver, og den anden vender processen ved at kombinere spektret tilbage til hvidt lys, Stoytchev forklarede.

Stoytchev og Sukhoy beskriver deres nye algoritme i et papir for nylig udgivet online af Videnskabelige rapporter , et Nature Research-tidsskrift. Deres papir viser, at algoritmen matcher beregningskompleksiteten eller hastigheden af ​​dens modstykke, at det kan bruges med eksponentielt henfaldende eller voksende frekvenskomponenter (i modsætning til IFFT), og at det er blevet testet for numerisk nøjagtighed.

Stoytchev sagde, at han faldt over ideen om at forsøge at formulere den manglende algoritme, mens han ledte efter analogier for at hjælpe kandidatstuderende i hans "Computational Perception"-kursus med at forstå den hurtige Fourier-transformation. Han læste meget af signalbehandlingslitteraturen og kunne ikke finde noget om det omvendte til den relaterede chirp z-transform.

"Jeg blev nysgerrig, " sagde han. "Er det fordi de ikke kunne forklare det, eller er det fordi det ikke findes? Det viste sig, at det ikke eksisterede."

Og så besluttede han at forsøge at finde en hurtig invers algoritme.

Sukhoy sagde, at den omvendte algoritme er et sværere problem end originalen, fremad algoritme og så "vi havde brug for bedre præcision og mere kraftfulde computere til at angribe den." Han sagde også, at en nøgle var at se algoritmen inden for den matematiske ramme for strukturerede matricer.

Selv da, der var masser af computertestkørsler "for at vise, at alt fungerede - vi var nødt til at overbevise os selv om, at dette kunne lade sig gøre."

Det krævede mod at blive ved med at angribe problemet, sagde James Oliver, direktør for Iowa State's Student Innovation Center og tidligere direktør for universitetets Virtual Reality Applications Center. Stoytchev og Sukhoy anerkender Oliver i deres papir "for at skabe det forskningsmiljø, hvor vi kunne forfølge dette arbejde i løbet af de sidste tre år."

Oliver sagde, at Stoytchev fik sin støtte til en matematisk og beregningsmæssig udfordring, der ikke var blevet løst i 50 år:"Alex har altid imponeret mig med sin passion og engagement i at tage store forskningsmæssige udfordringer op. Der er altid risiko i forskning, og det kræver mod at vie års hårdt arbejde til et grundlæggende problem. Alex er en begavet og frygtløs forsker."