Bluestein-FFT-Algorithmus

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]

Inhaltsverzeichnis

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 = ( − (kn)2 + n2 + k2) / 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 an und bn 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 bn) 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 an erweitert wird auf ein Feld An der Länge M, wobei andernfalls An = an für 0 ≤ n < N und An = 0 ist—die ursprüngliche Bedeutung von „zero-padding“ (Auffüllen mit Nullen).

Dennoch werden wegen des bkn Terms in der Faltung sowohl positive als auch negative Werte von n benötigt für bn (beachte, dass b n = bn). Die periodischen Randbedingungen, die durch die DFT des mit Nullen aufgefüllten Feldes impliziert werden, bedeuten, dass −n äquivalent ist zu Mn. Folglich wird bn erweitert zu einem Feld Bn der Länge M, wobei B0 = b0, Bn = BMn = bn für 0 < n < N, und Bn = 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 bn 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 bn eine antiperiodische Funktion, und technisch gesehen haben wir eine negazyklische Faltung (engl. negacyclic convolution) der Länge N. Solche Unterscheidungen verschwinden, wenn man an 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 bn 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

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Schnelle Fourier-Transformation — Eine schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei solchen Algorithmen handelt es sich… …   Deutsch Wikipedia

  • Liste von Transformationen in der Mathematik — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel… …   Deutsch Wikipedia

  • Z-Transformation — Die Z Transformation wandelt ein zeitdiskretes Signal im Zeitbereich, also eine zeitliche Abfolge von im Allgemeinen komplexen Zahlen, in ein komplexes diskretes Signal im Frequenzbereich um. Die zeitdiskrete Z Transformation ist das Analogon zur …   Deutsch Wikipedia

  • Fast-Fourier-Transformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

  • Fast Fourier-Transformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

  • Schnelle Fouriertransformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”