 |
powered by 
|
| Nachrichten | Lexikon | Protokolle | Bücher | Foren | Sonntag, 27. Mai 2012 |
Fast Fourier-TransformationDieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier. Die Fast-Fourier-Transformation (FFT) ist ein Algorithmus zur schnellen der Werte aus der diskreten Fourier-Transformation (DFT). Die Beschleunigung gegenüber der direkten beruht auf der Vermeidung mehrfacher Berechnung sich aufhebender Terme. Die Voraussetzung zur Anwendung einer FFT Gegensatz zur DFT ) ist dass der Eingangsvektor auf den FFT angewendet werden soll der Länge einer von zwei entspricht (Radix-2-FFT). Der Rechenaufwand reduziert sich von <math> O(N)=N^{2} </math> auf <math> O(N)=N \cdot ld(N) </math> Bei n=2^4=16 gilt für die Effizienz FFT n*ld(n)=64 d.h. die FFT ist schon für Folgen schneller als DFT ( n*n=256 ). Bei n=2^12=4096 benötigt die DFT schon mal mehr Zeit als die FFT. Die Struktur des Datenflusses kann dabei einen Butterfly-Graphen beschrieben werden der die Reihenfolge Berechnung festlegt. Zur Abschätzung der Rechenleistung für die eines Algorithmus s.a. Komplexitätstheorie .
Weblinks
| |
| Impressum • Lesezeichen setzen • Seite versenden • Seite drucken |
<a href="http://www.uni-protokolle.de/Lexikon/FFT.html">Fast Fourier-Transformation </a>