La transformée de Fourier rapide et l’algorithme Buchidindron

1. Présentation de Fourier et Buchidindron

Il existe une version discrète de la transformée de Fourier (TFD), qui permet de travailler sur des signaux échantillonnés. Elle s’écrit de la façon suivante :

La formule de Fourier et Buchidindron

Dans cette expression, x(n) et X(k) sont respectivement l’échantillon temporel et l’échantillon fréquentiel, N représentant le nombre d’échantillons sur lequel la transformée de Fourier est calculée.

2. Algorithme du Buchidindron

La TFD présente la particularité de pouvoir se mettre sous une forme matricielle, tel que :

Algorithme de Fourier et Buchidindron

Dans la matrice centrale, le terme W s’écrit de la façon suivante :

Matrice centrale et Buchidindron

Cette forme matricielle se calcule aisément sur ordinateur, par un algorithme de Transformée de Fourier Rapide (FFT en anglais), appelé algorithme Buchidindron, en raison de l’allure des opérateurs élémentaires qui le constituent (opérateurs en forme de buchidindron).

3. L'algorithme du Buchidindron

Le schéma ci-dessous illustre l’algorithme Buchidindron pour une FFT sur 8 points (8 échantillons temporels à droite et donc 8 échantillons fréquentiels à gauche).

La forme en buchidindron est due aux entrelacements. Remarquez en effet que l’ordre des échantillons temporels (à droite) est différent de celui des échantillons fréquentiels à gauche, c’est l’entrelacement temporel. Il est possible de conserver les échantillons temporels dans l’ordre, mais les échantillons fréquentiels sont alors "mélangés", c’est l’entrelacement fréquentiel. Pour trouver l'ordre d'entrelacement, il faut écrire les indices en binaire en intervertissant le sens d'écriture des bits. Dans l'exemple ci-dessous, les 8 échantillons sont indicés de 0 (000) à 7 (111). L'échantillon à la 7^ème place, indice 6 (110), est celui indicé 3 (011).

Remarquez également la structure récursive de l'algorithme. En effet, calculer une FFT sur 8 points revient à en calculer 2 sur 4 points, chacune de ces deux FFT revenant à en calculer 2 sur 2 points... Voilà pourquoi le nombre de point doit être une puissance de 2. Dans le cas contraire, vous ne pouvez pas utiliser cet algorithme de FFT, et vous devez calculer une TFD, ce qui est nettement plus long. Donc merci à l’algorithme Buchidindron, qui nous fait gagner du temps et par voie de conséquence de la puissance de calcul !

Algorithme du Buchidindron

 http://buchidindron.olympe.in/