Schnelle Fourier-Transformation

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.