Qualcosa chiamato la trasformazione veloce di Fourier è in esecuzione sul tuo cellulare in questo momento. La FFT, come è noto, è un algoritmo di elaborazione del segnale che usi più di quanto pensi. È, secondo il titolo di un documento di ricerca, "un algoritmo che tutta la famiglia può usare".

Alexander Stoytchev, professore associato di ingegneria elettrica e informatica presso la Iowa State University, affiliato anche al Virtual Reality Applications Center dell'università, il suo corso di laurea Human Computer Interaction e il dipartimento di informatica, afferma che l'algoritmo FFT e il suo inverso (noto come IFFT) sono al centro dell'elaborazione del segnale.

E, come tale, "Sono algoritmi che hanno reso possibile la rivoluzione digitale, " Egli ha detto.

Fanno parte della musica in streaming, fare una telefonata, navigando in internet o facendo un selfie.

L'algoritmo FFT è stato pubblicato nel 1965. Quattro anni dopo, ricercatori hanno sviluppato un più versatile, versione generalizzata chiamata chirp z-transform (CZT). Ma una simile generalizzazione dell'algoritmo FFT inverso è rimasta irrisolta per 50 anni.

Fino a quando, questo è, Stoytchev e Vladimir Sukhoy, uno studente di dottorato dello Stato dell'Iowa che si è laureato in ingegneria elettrica e informatica, e l'interazione uomo-computer - hanno lavorato insieme per elaborare l'algoritmo a lungo cercato, chiamata trasformata z chirp inversa (ICZT).

Come tutti gli algoritmi, è un processo graduale che risolve un problema. In questo caso, mappa l'output dell'algoritmo CZT sul suo input. I due algoritmi sono un po' come una serie di due prismi:il primo separa le lunghezze d'onda della luce bianca in uno spettro di colori e il secondo inverte il processo ricombinando lo spettro in luce bianca, Stoytchev ha spiegato.

Stoytchev e Sukhoy descrivono il loro nuovo algoritmo in un articolo recentemente pubblicato online da Rapporti scientifici , una rivista di ricerca sulla natura. Il loro articolo mostra che l'algoritmo corrisponde alla complessità computazionale o alla velocità della sua controparte, che può essere utilizzato con componenti di frequenza in decadimento esponenziale o in crescita (a differenza dell'IFFT) e che è stato testato per l'accuratezza numerica.

Stoytchev ha detto di essere incappato nell'idea di tentare di formulare l'algoritmo mancante mentre cercava analogie per aiutare gli studenti laureati nel suo corso "Percezione computazionale" a comprendere la veloce trasformata di Fourier. Ha letto molta della letteratura sull'elaborazione del segnale e non è riuscito a trovare nulla sull'inverso della relativa trasformata z chirp.

"Mi sono incuriosito, " ha detto. "È perché non potevano spiegarlo, o è perché non esiste? Si è scoperto che non esisteva".

E così decise di provare a trovare un algoritmo inverso veloce.

Sukhoy ha detto che l'algoritmo inverso è un problema più difficile dell'originale, forward algoritmo e quindi "avevamo bisogno di una migliore precisione e di computer più potenti per attaccarlo". Ha anche detto che una chiave era vedere l'algoritmo all'interno del quadro matematico delle matrici strutturate.

Anche allora, ci sono stati molti test al computer "per dimostrare che tutto funzionava:dovevamo convincerci che si poteva fare".

Ci voleva coraggio per continuare ad attaccare il problema, disse James Oliver, direttore dello Student Innovation Center dell'Iowa State ed ex direttore del Virtual Reality Applications Center dell'università. Stoytchev e Sukhoy riconoscono Oliver nel loro articolo "per aver creato l'ambiente di ricerca in cui abbiamo potuto portare avanti questo lavoro negli ultimi tre anni".

Oliver ha detto che Stoytchev ha guadagnato il suo sostegno per una sfida matematica e computazionale che non è stata risolta da 50 anni:"Alex mi ha sempre impressionato con la sua passione e il suo impegno nell'affrontare grandi sfide di ricerca. C'è sempre il rischio nella ricerca e ci vuole coraggio dedicare anni di duro lavoro a un problema fondamentale. Alex è un ricercatore dotato e senza paura."