Chimie

Transformée de Fourier Rapide


Transformée de Fourier discrète rapide

Lors du calcul de la transformée de Fourier discrète

F.(??m)=1Nm=0N-1F(tm)eje??mtm,m=0,1,,N-1

sont pour chacun m précisément 2N Multiplications nécessaires :

F(tm)car(??mtm),m=0,1,,N-1NMultiplicationF(tm)péché(??mtm),m=0,1,,N-1NMultiplication

Pour tous m sont tellement N2N=2N2 Multiplications nécessaires. Le calcul des coefficients de cette manière est dit avoir une complexité temporelle de O(N2). La méthode de la transformée de Fourier rapide a en fait une complexité temporelle de O(NJournal2(N))que nous voulons démontrer ci-dessous.

Exécutons le nombre complexe

w=eje2??N

un, alors est

eje??mtm=eje2??mTmTN=eje2??mmN=wmm

et

F.(??m)=1Nm=0N-1F(tm)wmm,m=0,1,,N-1.

La transformée de Fourier discrète peut être écrite comme la somme de deux transformées de Fourier discrètes :

F.(??m)=1Nm=0N-1F(tm)eje2??mmN=1Nm=0N/2-1F(t2m)eje2??m(2m)N+1Nm=0N/2-1F(t2m+1)eje2??m(2m+1)N=121N/2m=0N/2-1F(t2m)eje2??mmN/2+12wm1N/2m=0N/2-1F(t2m+1)eje2??mmN/2=12F.(e)(??m)+12wmF.(O)(??m)

par lequel F.(e)(??m) respectivement. F.(O)(??m) les m-ième composante de la transformée de Fourier discrète des composantes paires ou impaires de l'original F(tm)'s désignent chacun de la longueur N/2 sommes. Une propriété importante de (également connue sous le nom de lemme de Danielson-Lanczos) est qu'elle peut être appliquée de manière récursive. F.(e)(??m) peut être exprimé comme la somme de deux transformées de Fourier discrètes de demi-longueur (N/4) écrire, et il en va de même pour F.(O)(??m):

F.(e)(??m)=12F.(ee)(??m)+12wmF.(eo)(??m)F.(O)(??m)=12F.(oe)(??m)+12wmF.(oh)(??m)

Par exemple pour N=8 on calcule

F.(e)(??m)avec les points0,2,4,6F.(ee)(??m)avec les points0,4F.(eo)(??m)avec les points2,6F.(eee)(??m)avec la pointe0F.(eeo)(??m)avec la pointe4F.(eoe)(??m)avec la pointe2F.(euh)(??m)avec la pointe6F.(O)(??m)avec les points1,3,5,7F.(oe)(??m)avec les points1,5F.(oh)(??m)avec les points3,7F.(oee)(??m)avec la pointe1F.(oeo)(??m)avec la pointe5F.(ooe)(??m)avec la pointe3F.(ooo)(??m)avec la pointe7

Les données sont divisées en transformées de Fourier discrètes de longueur 1, que seules les opérations d'identité sont par ex.

F.(oeo)(??m)=F(t5).

Comment savoir lesquels tm une séquence donnée de e 's et o' s est-elle assignée ? Vous inversez la séquence et finalement échangez e pour 0 et o pour 1. La séquence résultante est maintenant la représentation binaire de la valeur souhaitée de mpar exemple.

ooeeoo011m=3.

La méthode de transformée de Fourier rapide est la suivante. tu les triesF(tm)n'est pas après m, mais selon la représentation binaire inverse de m:

Tab.1
Trier le F(tm)'s (N=8)
m01234567
Représentation binaire000001010011100101110111
vice versa000100010110001101011111
m re-trié04261537

Des paires adjacentes, par exemple 0 et 4 ou 2 et 6, sont combinées pour obtenir des transformations de longueur 2. Combinez ensuite les transformations résultantes pour obtenir des transformations de longueur 4, et ainsi de suite, à l'exception de la combinaison de la seconde moitié des données totales. La procédure fonctionne mieux lorsque N une puissance entière de 2 est, c'est-à-dire N=2M.. On calcule F.(??m) avec une complexité temporelle de O(Journal2(N)) et par conséquent le NF.(??m)'s avec une complexité temporelle de O(NJournal2(N)).


Vidéo: pt bilan sur la tfd transformée de fourier discrète et la fft fast fourier transform (Janvier 2022).