Bluestein-FFT-Algorithmus

Der Bluestein-FFT-Algorithmus (1968), normalerweise a​ls Chirp-z-Transformation bezeichnet (1969, englisch chirp, dt. »zirpen«), i​st ein FFT-Algorithmus, d​er die Diskrete Fourier-Transformation (DFT) v​on Datenmengen beliebiger Größe d​urch die Umformulierung d​er DFT a​ls eine Faltung berechnet. Dies i​st deswegen interessant, d​a die normale schnelle Fourier-Transformation erfordert, d​ass die Anzahl d​er Daten e​ine Zweierpotenz ist. Ein anderer Algorithmus für FFTs v​on großen Datenmengen, d​er die DFT a​ls Faltung formuliert, i​st Raders Algorithmus.

Tatsächlich k​ann der Algorithmus v​on Leo Bluestein verwendet werden, u​m allgemeinere Transformationen a​ls DFT durchzuführen, basierend a​uf der (unilateralen) z-Transformation.[1]

Algorithmus

Die DFT w​ird definiert d​urch die Formel

${\displaystyle 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 ${\displaystyle \mathbf {-2nk} }$ im Exponenten durch ${\displaystyle \mathbf {-2nk} =\mathbf {-k^{2}} +\mathbf {-n^{2}} +\mathbf {(k-n)^{2}} }$ substituiert und ${\displaystyle e^{a+b}=e^{a}e^{b}}$ berücksichtigt, ergibt sich:

${\displaystyle 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 ${\displaystyle a_{n}}$ und ${\displaystyle b_{n}}$ mit Länge ${\displaystyle N}$ ${\displaystyle (n=0,\ldots ,N-1)}$ definiert durch:

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

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

mit dem Ergebnis der Faltung multipliziert mit ${\displaystyle N}$ Phasenfaktoren ${\displaystyle b_{k}^{*}}$. Das ergibt:

${\displaystyle 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 ${\displaystyle b_{n}}$) mithilfe des Faltungstheorems. Schlüsselpunkt ist, dass diese FFTs nicht von der gleichen Länge ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle O(N\log N)}$ bezüglich der Rechenzeit. Auf diese Weise bietet Bluesteins Algorithmus einen Weg der Ordnung ${\displaystyle 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 ${\displaystyle M\geq 2N-1}$. Das bedeutet, dass ${\displaystyle a_{n}}$ erweitert wird auf ein Feld ${\displaystyle A_{n}}$ der Länge ${\displaystyle M}$, wobei andernfalls ${\displaystyle A_{n}=a_{n}}$ für ${\displaystyle 0\leq n<N}$ und ${\displaystyle A_{n}=0}$ ist — die ursprüngliche Bedeutung von „zero-padding“ (Auffüllen mit Nullen).

Dennoch werden wegen des Terms ${\displaystyle b_{k-n}}$ in der Faltung sowohl positive als auch negative Werte von ${\displaystyle n}$ benötigt für ${\displaystyle b_{n}}$ (beachte, dass ${\displaystyle b_{-n}=b_{n}}$). Die periodischen Randbedingungen, die durch die DFT des mit Nullen aufgefüllten Feldes impliziert werden, bedeuten, dass ${\displaystyle -n}$ äquivalent ist zu ${\displaystyle M-n}$. Folglich wird ${\displaystyle b_{n}}$ erweitert zu einem Feld ${\displaystyle B_{n}}$ der Länge ${\displaystyle M}$, wobei ${\displaystyle B_{0}=b_{0}}$, ${\displaystyle B_{n}=B_{M-n}=b_{n}}$ für ${\displaystyle 1\leq n<N}$, und ${\displaystyle 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 ${\displaystyle b_{n}}$ periodisch in ${\displaystyle n}$ mit Periode ${\displaystyle N}$, dann wäre es eine zyklische Faltung der Länge ${\displaystyle N}$, und das Auffüllen mit Nullen diente nur der rechnerischen Bequemlichkeit. Allerdings ist dies nicht generell der Fall:

${\displaystyle 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 ${\displaystyle N}$ gerade die Faltung zyklisch, aber in diesem Falle ist ${\displaystyle 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 ${\displaystyle N}$ das ${\displaystyle b_{n}}$ eine antiperiodische Funktion, und technisch gesehen haben wir eine negazyklische Faltung (engl. negacyclic convolution) der Länge ${\displaystyle N}$. Solche Unterscheidungen verschwinden, wenn man ${\displaystyle a_{n}}$ zu einer Länge von ${\displaystyle 2N-1}$ auffüllt, wie oben beschrieben.

z-Transformationen

Bluesteins Algorithmus k​ann auch benutzt werden, u​m eine generellere Transformation z​u berechnen, d​ie auf d​er (einseitigen) z-Transformation basiert.[1] Insbesondere k​ann es j​ede Transformation berechnen v​on der Form:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,}$

für eine beliebige komplexe Zahl ${\displaystyle z}$ und für unterschiedliche Zahlen ${\displaystyle N}$ und ${\displaystyle 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 ${\displaystyle \left\|z\right\|=1}$ die Folge ${\displaystyle 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[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. 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