Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Was ist die Idee der Faktorisierung der DFT?
(Merkmale)

Faktorisierung bedeutet die Zerlegung eines Objektes in mehrere nichttriviale Faktoren die zu dem gleichen Ergebnis führen.
"Teile und Hersche" => Divide and Conquer
Kann rekursiv implementiert werden => Fast Fourier Transformation
gleichartige Zwischenergebnisse sind auf diese Weise mehrfach wiederverwendbar
Berechnung der DFT der Größe 2n zunächst in zwei Berechnungen der Größe n aufteilen
=> Vektoren mit geraden bzw. ungeraden Indizes
und beide Teilergebnisse nach der Transformation wieder zu einer zusammenzufügen
=> Berechnung DFT halbe Länge nur ein viertel der komplexen Multiplikationen und Additionen und diese Vorschrift mehrfach hintereinander anwendbar ist (rekursives Vorgehen) ...
... Aufwand (rekursive Berechnung)

Karteninfo:

Autor: JanBo

Veröffentlicht: 13.09.2012