Bluestein-FFT-Algorithmus

Der Bluestein-FFT-Algorithmus (1968), normalerweise als Chirp-z-Transformation bezeichnet (1969, englisch chirp, dt. »zirpen«), ist ein FFT-Algorithmus, der die Diskrete Fourier-Transformation (DFT) von Datenmengen beliebiger Größe durch die Umformulierung der DFT als eine Faltung berechnet. Dies ist deswegen interessant, da die normale schnelle Fourier-Transformation erfordert, dass die Anzahl der Daten eine Zweierpotenz ist. Ein anderer Algorithmus für FFTs von großen Datenmengen, der die DFT als Faltung formuliert, ist Raders Algorithmus.

Tatsächlich kann der Algorithmus von Leo Bluestein verwendet werden, um allgemeinere Transformationen als DFT durchzuführen, basierend auf der (unilateralen) z-Transformation.^[1]

Algorithmus

Die DFT wird definiert durch die Formel

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk } \qquad k = 0,\dots,N-1.$

Wird das Produkt nk im Exponenten über die Gleichung nk = ( − (k − n)² + n² + k²) / 2 ersetzt, ergibt sich:

$X_k = e^{-\frac{\pi i}{N} k^2 } \sum_{n=0}^{N-1} \left( x_n e^{-\frac{\pi i}{N} n^2 } \right) e^{\frac{\pi i}{N} (k-n)^2 } \qquad k = 0,\dots,N-1.$

Diese Summation ist genau genommen eine Faltung der beiden Folgen a_n und b_n mit Länge N (n = 0, …,N−1) definiert durch:

$a_n = x_n e^{-\frac{\pi i}{N} n^2 }$

$b_n = e^{\frac{\pi i}{N} n^2 },$

mit dem Ergebnis der Faltung multipliziert mit N Phasenfaktoren $b_k^*$. Das ergibt:

$X_k = b_k^* \sum_{n=0}^{N-1} a_n b_{k-n} \qquad k = 0,\dots,N-1.$

Diese Faltung kann wiederum durchgeführt werden mit einem Paar von FFTs (und der voraus berechneten FFT von b_n) mithilfe des Faltungstheorems. Schlüsselpunkt ist, dass diese FFTs nicht von der gleichen Länge N sind: solch eine Faltung kann von FFTs exakt nur berechnet werden durch Auffüllen mit Nullen zu einer Länge größer als oder gleich 2N−1. Insbesondere kann man zu einer Zweierpotenz oder einer anderen zusammengesetzten Zahl auffüllen, für die die FFT effizient durchgeführt werden kann durch z. B. den Cooley-Tukey-FFT-Algorithmus mit Ordnung O(N log N) bezüglich der Rechenzeit. Auf diese Weise bietet Bluesteins Algorithmus einen Weg der Ordnung O(N log N) zur Berechnung von DFTs mit Primzahl-Größe, auch wenn er um einige Faktoren langsamer ist als der Cooley-Tukey-Algorithmus für zusammengesetzte Zahlen.

Das Auffüllen mit Nullen für die Faltung in Bluesteins Algorithmus benötigt eine zusätzliche Erläuterung. Angenommen, wir füllen Nullen auf bis zu einer Länge M ≥ 2N−1. Das bedeutet, dass a_n erweitert wird auf ein Feld A_n der Länge M, wobei andernfalls A_n = a_n für 0 ≤ n < N und A_n = 0 ist—die ursprüngliche Bedeutung von „zero-padding“ (Auffüllen mit Nullen).

Dennoch werden wegen des b_k−n Terms in der Faltung sowohl positive als auch negative Werte von n benötigt für b_n (beachte, dass b _{− n} = b_n). Die periodischen Randbedingungen, die durch die DFT des mit Nullen aufgefüllten Feldes impliziert werden, bedeuten, dass −n äquivalent ist zu M−n. Folglich wird b_n erweitert zu einem Feld B_n der Länge M, wobei B₀ = b₀, B_n = B_{M − n} = b_n für 0 < n < N, und B_n = 0 sonst.

Betrachten wir also etwas genauer, welcher Typ von Faltung in Bluesteins Algorithmus für die DFT benötigt wird. Wäre die Folge b_n periodisch in n mit Periode N, dann wäre es eine zyklische Faltung der Länge N, und das Auffüllen mit Nullen diente nur der rechnerischen Bequemlichkeit. Allerdings ist dies nicht generell der Fall:

$b_{n+N} = e^{\frac{\pi i}{N} (n+N)^2 } = b_n e^{\frac{\pi i}{N} (2Nn+N^2) } = (-1)^N b_n .$

Folglich ist für N gerade die Faltung zyklisch, aber in diesem Falle ist N eine zusammengesetzte Zahl und normalerweise würde man einen effizienteren FFT Algorithmus wie z. B. den nach Cooley-Tukey wählen. Jedoch ist für ungerade N das b_n eine antiperiodische Funktion, und technisch gesehen haben wir eine negazyklische Faltung (engl. negacyclic convolution) der Länge N. Solche Unterscheidungen verschwinden, wenn man a_n zu einer Länge von 2N−1 auffüllt, wie oben beschrieben.

z-Transformationen

Bluestein's Algorithmus kann auch benutzt werden, um eine generellere Transformation zu berechnen, die auf der (einseitigen) z-Transformation basiert.^[1] Insbesondere kann es jede Transformation berechnen von der Form:

$X_k = \sum_{n=0}^{N-1} x_n z^{nk} \qquad k = 0,\dots,M-1,$

für eine beliebige komplexe Zahl z und für unterschiedliche Zahlen N und M von Eingaben und Ausgaben. Angesichts Bluestein's Algorithmus kann eine solche Transformation zum Beispiel benutzt werden, um eine feinere Interpolation zu erhalten von einem Teil des Spektrums (obgleich die Frequenzauflösung immer noch begrenzt wird durch die totale Messzeit). Auch kann man beliebige Pole bei der Analyse von Übertragungsfunktionen herausarbeiten usw.

Der Algorithmus wurde als Chirp-Z-Transformations Algorithmus bezeichnet, weil im Falle der Fourier-Transformation mit |z| = 1 die Folge b_n von oben eine komplexe Sinuskurve ist mit linear anwachsender Frequenz, die in Radar-Systemen als (linearer) Chirp bezeichnet wird.

Literatur

• Leo I. Bluestein: A linear filtering approach to the computation of the discrete Fourier transform. In: Northeast Electronics Research and Engineering Meeting Record 10, 1968, S. 218–219.
• Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader: The chirp z-transform Algorithmus and its applicatio. In: Bell Syst. Tech. J. 48, 1969, S. 1249–1292. Ebenfalls veröffentlicht in: Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader: The chirp z-transform Algorithmus. In: IEEE Trans. Audio Electroacoustics. 17, Nr. 2, 1969, S. 86–92.
• D. H. Bailey, P. N. Swarztrauber: The fractional Fourier transform and applications. In: SIAM Review. 33, 1991, S. 389–404 (Beachte, dass diese Terminologie für die z-Transformation nicht standardgemäß ist: eine fraktionale Fourier-Transformation ^[2] bezieht sich üblicherweise auf eine völlig andere kontinuierliche Transformation.).
• Lawrence Rabiner: The chirp z-transform Algorithmus—a lesson in serendipity. In: IEEE Signal Processing Magazine. 24, 2004, S. 118–119 (Historisch geprägter Kommentar).

Einzelnachweise

1. ↑ ^{a b} Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader: The chirp z-transform Algorithmus and its application. In: Bell Syst. Tech. J. 48, 1969, S. 1249–1292. Ebenfalls veröffentlicht in: Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader: The chirp z-transform Algorithmus. In: IEEE Trans. Audio Electroacoustics. 17, Nr. 2, 1969, S. 86–92.
2. ↑ siehe „fractional Fourier transform“ in der englischen Wikipedia