The Most Important Algorithm Of All Time - YouTube

Une vidéo sur la FFT, ou transformation de Fourier rapide, (Fast Fourier Transform).

La transformation de Fourier, c’est ce qui permet de décomposer un signal compliqué (son, par exemple) en une somme de signaux très simples, essentiellement une somme de sinusoïdes parfaites.
Stocker l’information de ces sinus prend alors moins de place que stocker le signal initial. C’est comme ça que fonctionne par exemple le format de compression audio MP3 : https://couleur-science.eu/?d=dc0354--introduction-a-la-decomposition-de-fourier

Il s’agit d’une compression destructive : certaines informations sont éliminées, mais ce sont des pertes imperceptibles à l’oreille. Ainsi, l’utilisateur moyen d’un MP3 se contente très largement d’un MP3 320 kbps à la place du lossless, et le réseau téléphonique peut descendre à 12 voire 4 kbps, et toujours être intelligible.

Le problème dans la transformation de Fourier, c’est que ça demande beaucoup de calculs pour décomposer un signal. Un son d’une seconde à 128 kbps va demande 128000² opérations complexes, soit 16 milliards d’opérations… et pour une seule seconde audio !

Sauf que certains de ces calculs sont redondants (comme le montre la vidéo) et en jouant sur ça, on réduit le nombre de calculs à 653 000 opérations (pour notre exemple, au lieu de 16 milliards).

L’algorithme qui utilise cette optimisation s’appelle la FFT et est utilisée absolument partout en traitement du signal, que ce soit les formats de fichiers compressés (MP3, JPEG…), la transmissions de signaux (4G, 5G, Wifi…), ou l’analyse de signaux inconnus captés par une antenne (signaux radars, dont l’analyse permet de déterminer la source du signal inconnu).

L’algo actuellement utilisé date du XXe siècle, et devait être utilisée pour détecter des détonations de bombes nucléaires pendant la course à l’armement de la (première) Guerre Froide.

Mais dans la vidéo j’apprends qu’un algo très similaire avait déjà été proposé un siècle avant par… Carl Friedrich Gauss.