Fast Fourier transform: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
Geen bewerkingssamenvatting |
Geen bewerkingssamenvatting |
||
Regel 5:
Voor de toegepassing van een dergelijke recursie is vereist dat <math>N</math> een macht van 2 is. Later is deze methode gegeneraliseerd naar een ontbinding in willekeurige [[priemfactor]]en, waardoor een meer algemene toepasbaarheid ontstond. Gebruik van grote priemfactoren kan echter zeer nadelige gevolgen hebben voor de rekentijd. Voor praktische toepassing zoals in [[signaalanalyse]] heeft de beperking tot machten van twee nauwelijks gevolgen. Wanneer een 3-dimensionale FFT wordt gebruikt, zoals in de [[kristallografie]], kan het echter leiden tot bijna 8 keer meer geheugengebruik en 24 keer meer rekentijd dan strikt noodzakelijk.
== Het algoritme van Cooley en Tukey ==
Aan de hand van het algoritme van Cooley en Tukey is goed te zien hoe een discrete fouriertransformatie van dimensie 2n gereduceerd kan worden tot 2 transformaties van dimensie n.
Laat <math>(x_0, \ldots, x_{2n-1})</math> een discreet signaal zijn van dimensie 2n. De DFT van dit signaal is:
:<math>X_m =\sum_{k=0}^{2n-1} x_k \, e^{-\frac{2\pi i}{2n}mk }=\sum_{k=0}^{2n-1} x_k w_{km}(2n),
\quad
m = 0,\ldots,2n-1</math>
Noem de ingangsdata met even index:
:<math>x'_r = x_{2r}, \quad r = 0,\ldots,n-1</math>
met DFT <math>X'</math>,
en die met oneven index
:<math>x''_r = x_{2r+1}, \quad r = 0,\ldots,n-1</math>
met DFT <math>X''</math>.
Dan is:
:<math>
\begin{align}
X_m & = \sum_{r=0}^{n-1} x_{2r } w_{2r,m}(2n)
+ \sum_{r=0}^{n-1} x_{2r+1} w_{2r+1,m}(2n) \\
& = \sum_{r=0}^{n-1} x' _r w_{r,m}(n)
+ w_{1,m}(n) \sum_{r=0}^{n-1} x''_r w_{r,m}(n)\\
& =
\begin{cases}
X'_m + w_{1,m}(n) X''_m & \text{ als } m<n \\
X'_{m-n} - w_{1,n-m}(n)X''_{m-n} & \text{ als } m \geq n
\end{cases}
\end{align}
</math>
Merk ook op dat de wegingsfactoren <math>w_{r,m}(n)</math> slechts eenmaal berekend hoeven te worden voor de beide n-dimensionale transformaties.
== Zie ook ==
| |||