Schnelle Fourier-Transformation
Algorithmus zu Berechnung der diskreten Fourier-Transformation; Zerlegung eines zeitdiskreten Signals in seine Frequenzanteile
Die Fast-Fourier-Transformation (FFT) ist ein Algorithmus zur schnellen Berechnung der Werte aus der diskreten Fourier-Transformation. Die Beschleunigung gegenüber der direkten Berechnung beruht auf der Vermeidung mehrfacher Berechnung sich wiederholender Terme.
Die Stuktur des Datenflusses kann dabei durch einen Butterfly-Graphen beschrieben werden, der die Reihenfolge der Beschrechnung festlegt.
stub alarm