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.

Algorithmus

Die DFT wird definiert durch die Formel

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}=\sum _{n=0}^{N-1}x_{n}e^{{\mathbf {-2nk} }{\frac {\pi i}{N}}}\qquad k=0,\dots ,N-1.$

Wird das Produkt $\mathbf {-2nk}$ im Exponenten durch $\mathbf {-2nk} =\mathbf {-k^{2}} +\mathbf {-n^{2}} +\mathbf {(k-n)^{2}}$ substituiert und $e^{a+b}=e^{a}e^{b}$ berücksichtigt, ergibt sich:

$X_{k}=e^{\mathbf {-k^{2}} {\frac {\pi i}{N}}}\sum _{n=0}^{N-1}\left(x_{n}e^{\mathbf {-n^{2}} {\frac {\pi i}{N}}}\right)e^{\mathbf {+(k-n)^{2}} {\frac {\pi i}{N}}}\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,\ldots ,N-1)$ definiert durch:

$a_{n}=x_{n}e^{-n^{2}{\frac {\pi i}{N}}}$

$b_{k-n}=e^{+(k-n)^{2}{\frac {\pi i}{N}}},$

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 vorausberechneten 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\geq 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\leq n<N$ und $A_{n}=0$ ist – die ursprüngliche Bedeutung von „zero-padding“ (Auffüllen mit Nullen).

Dennoch werden wegen des Terms $b_{k-n}$ 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_{0}=b_{0}$, $B_{n}=B_{M-n}=b_{n}$ für $1\leq 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

Bluesteins Algorithmus kann auch benutzt werden, um eine generellere Transformation zu berechnen, die auf der (einseitigen) z-Transformation basiert. 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 Bluesteins 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 wird als Chirp-z-Transformationsalgorithmus bezeichnet, weil im Falle der Fourier-Transformation mit $\left\|z\right\|=1$ die Folge $b_{n}$ von oben eine komplexe Sinuskurve mit linear anwachsender Frequenz ist, 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 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).