Quelque chose appelé la transformation de Fourier rapide est en cours d'exécution sur votre téléphone portable en ce moment. La FFT, comme on le sait, est un algorithme de traitement du signal que vous utilisez plus que vous ne le pensez. Il est, selon le titre d'un article de recherche, "un algorithme que toute la famille peut utiliser."

Alexander Stoytchev, professeur agrégé d'ingénierie électrique et informatique à l'Iowa State University, également affilié au Virtual Reality Applications Center de l'université, son programme d'études supérieures Human Computer Interaction et le département d'informatique - affirme que l'algorithme FFT et son inverse (connu sous le nom d'IFFT) sont au cœur du traitement du signal.

Et, En tant que tel, « Ce sont des algorithmes qui ont rendu possible la révolution numérique, " il a dit.

Ils font partie de la musique en streaming, passer un appel téléphonique, naviguer sur Internet ou prendre un selfie.

L'algorithme FFT a été publié en 1965. Quatre ans plus tard, les chercheurs ont développé une méthode plus polyvalente, version généralisée appelée chirp z-transform (CZT). Mais une généralisation similaire de l'algorithme FFT inverse n'a pas été résolue depuis 50 ans.

Jusqu'à, C'est, Stoytchev et Vladimir Sukhoy, un doctorant de l'État de l'Iowa se spécialisant en génie électrique et informatique, et l'interaction homme-machine - ont travaillé ensemble pour proposer l'algorithme tant recherché, appelée transformation en z chirp inverse (ICZT).

Comme tous les algorithmes, c'est un processus étape par étape qui résout un problème. Dans ce cas, il mappe la sortie de l'algorithme CZT sur son entrée. Les deux algorithmes sont un peu comme une série de deux prismes - le premier sépare les longueurs d'onde de la lumière blanche en un spectre de couleurs et le second inverse le processus en combinant le spectre en lumière blanche, Stoytchev a expliqué.

Stoytchev et Sukhoy décrivent leur nouvel algorithme dans un article récemment publié en ligne par Rapports scientifiques , une revue de recherche sur la nature. Leur article montre que l'algorithme correspond à la complexité ou à la vitesse de calcul de son homologue, qu'il peut être utilisé avec des composantes de fréquence en décroissance ou croissance exponentielle (contrairement à l'IFFT) et qu'il a été testé pour sa précision numérique.

Stoytchev a déclaré qu'il avait trébuché sur l'idée de tenter de formuler l'algorithme manquant tout en recherchant des analogies pour aider les étudiants diplômés de son cours "Perception computationnelle" à comprendre la transformée de Fourier rapide. Il a lu beaucoup de littérature sur le traitement du signal et n'a rien trouvé sur l'inverse de la transformation z chirp connexe.

"Je suis devenu curieux, " dit-il. " Est-ce parce qu'ils ne pouvaient pas l'expliquer, ou est-ce parce qu'il n'existe pas ? Il s'est avéré que cela n'existait pas."

Et il a donc décidé d'essayer de trouver un algorithme inverse rapide.

Sukhoy a déclaré que l'algorithme inverse est un problème plus difficile que l'original, algorithme avancé et donc "nous avions besoin d'une meilleure précision et d'ordinateurs plus puissants pour l'attaquer". Il a également déclaré qu'une clé était de voir l'algorithme dans le cadre mathématique des matrices structurées.

Même à ce moment là, il y avait beaucoup de tests informatiques "pour montrer que tout fonctionnait - nous devions nous convaincre que cela pouvait être fait."

Il a fallu du courage pour continuer à attaquer le problème, dit James Oliver, directeur du Student Innovation Center de l'Iowa State et ancien directeur du Virtual Reality Applications Center de l'université. Stoytchev et Sukhoy reconnaissent Oliver dans leur article "pour avoir créé l'environnement de recherche dans lequel nous avons pu poursuivre ce travail au cours des trois dernières années".

Oliver a déclaré que Stoytchev avait obtenu son soutien pour un défi mathématique et informatique qui n'avait pas été résolu depuis 50 ans :« Alex m'a toujours impressionné par sa passion et son engagement à relever de grands défis de recherche. Il y a toujours des risques dans la recherche et il faut du courage. consacrer des années de travail acharné à un problème fondamental. Alex est un chercheur doué et intrépide.