Comment fonctionne FFT
Chapitre 12: La transformée de Fourier rapide
Comment fonctionne FFT
La FFT est un algorithme complexe, et ses détails sont généralement laissés à ceux qui se spécialisent dans de telles choses. Cette section décrit le fonctionnement général de la FFT, mais longe une question clé: l'utilisation des nombres complexes. Si vous avez une formation en mathématiques complexes, vous pouvez lire entre les lignes pour comprendre la vraie nature de l'algorithme. Ne vous inquiétez pas si les détails vous échappent; peu de scientifiques et d'ingénieurs qui utilisent la FFT pourrait écrire le programme à partir de zéro.
En notation complexe, les domaines temporel et fréquentiel contiennent chacun un signal constitué de points nSimplification. Chacun de ces points complexe est composé de deux nombres, la partie réelle et la partie imaginaire. Par exemple, quand on parle de l'échantillon complexe X [42], il fait référence à la combinaison de ReX [42] et ImX [42]. En d'autres termes, chaque variable complexe possède deux numéros. Lorsque deux variables complexes sont multipliés, les quatre composants individuels doivent être combinées pour former les deux composants du produit (comme dans l'équation. 9-1). La discussion qui suit sur « Comment la FFT fonctionne » utilise ce jargon de notation complexe. Autrement dit, les termes singuliers: le signal, le point, l'échantillon. et la valeur. reportez-vous à la combinaison de la partie réelle et la partie imaginaire.
L'étape suivante de l'algorithme de FFT est de trouver les spectres de fréquence des signaux dans le domaine temporel des points 1. Rien de plus facile; le spectre de fréquences d'un signal de point de 1 est égal à lui-même. Cela signifie que rien ne doit faire cette étape. Bien qu'il n'y ait pas de travail en cause, ne pas oublier que chacun des 1 signaux de point est maintenant un spectre de fréquences, et non un signal de domaine.
8 signal de point, puis ajouter les signaux ensemble. Autrement dit, ABCD devient a0b0c0d0. et EFGH devient 0e0f0g0h. L'ajout de ces deux signaux de points 8 produit aebfcgdh. Comme le montre la Fig. 4/12, en diluant le domaine temporel avec des zéros correspond à une duplication du spectre de fréquences. Par conséquent, les spectres de fréquence sont combinés dans la FFT en les dupliquant, puis en ajoutant les spectres dupliquée ensemble.
Afin de faire correspondre lorsqu'il est ajouté, les deux signaux de domaine de temps sont dilués avec des zéros d'une manière légèrement différente. Dans un signal, les points impairs sont nuls, tandis que dans l'autre signal, les points pairs sont nuls. En d'autres termes, l'un des signaux de domaine de temps (0e0f0g0h sur la Fig. 12-4) est décalée vers la droite d'un seul échantillon. Ce changement de domaine de temps correspond à la multiplication du spectre par une sinusoïde. Pour voir cela, rappelons que le passage dans le domaine temporel est équivalent à une convolution du signal avec une fonction delta décalée. Cela multiplie le spectre du signal avec le spectre de la fonction delta décalé. Le spectre d'une fonction delta décalée est une sinusoïde (voir la figure 11-2).
La figure 12-5 montre un organigramme destiné à combiner deux spectres de 4 points en un seul spectre de 8 points. Afin de réduire encore plus la situation, notez que la figure. 12-5 est formé à partir du modèle de base de la figure 12-6 répétée à plusieurs reprises.
Ce schéma simple flux est appelé un papillon en raison de son aspect ailé. Le papillon est l'élément de base de calcul de la FFT, en transformant deux points complexes en deux autres points complexes.
La synthèse de domaine de fréquence nécessite trois boucles. La boucle externe traverse les étages de log2n (à savoir chaque niveau sur la Fig. 12-2, en partant du bas et se déplaçant vers le haut). Les mouvements de la boucle du milieu à travers chacun des spectres de fréquences individuelles dans l'étape en cours de travail (à savoir chacune des cases sur un seul niveau sur la Fig. 2.12). La boucle la plus interne utilise le papillon pour calculer les points dans chaque spectre de fréquences (à savoir une boucle à travers les échantillons à l'intérieur une zone à la Fig. 2.12). Les boîtes en tête dans la figure. 12-7 déterminent le début et les indices de fin pour les boucles, ainsi que le calcul des sinusoïdes nécessaires dans les papillons. Maintenant, nous arrivons au cœur de ce chapitre, les programmes de FFT réels.