www.wikidata.de-de.nina.az

Bluestein FFT Algorithmus Der 1968 normalerweise als Chirp z Transformation bezeichnet 1969 englisch chirp dt zirpen ist

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 Bearbeiten

Die DFT wird definiert durch die Formel

Wird das Produkt im Exponenten durch substituiert und berücksichtigt, ergibt sich:

Diese Summation ist genau genommen eine Faltung der beiden Folgen und mit Länge definiert durch:

mit dem Ergebnis der Faltung multipliziert mit Phasenfaktoren . Das ergibt:

Diese Faltung kann wiederum durchgeführt werden mit einem Paar von FFTs (und der vorausberechneten FFT von ) mithilfe des Faltungstheorems. Schlüsselpunkt ist, dass diese FFTs nicht von der gleichen Länge 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 . 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 bezüglich der Rechenzeit. Auf diese Weise bietet Bluesteins Algorithmus einen Weg der Ordnung 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 . Das bedeutet, dass erweitert wird auf ein Feld der Länge , wobei andernfalls für und ist – die ursprüngliche Bedeutung von „zero-padding“ (Auffüllen mit Nullen).

Dennoch werden wegen des Terms in der Faltung sowohl positive als auch negative Werte von benötigt für (beachte, dass ). Die periodischen Randbedingungen, die durch die DFT des mit Nullen aufgefüllten Feldes impliziert werden, bedeuten, dass äquivalent ist zu . Folglich wird erweitert zu einem Feld der Länge , wobei , für , und sonst.

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

Folglich ist für gerade die Faltung zyklisch, aber in diesem Falle ist 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 das eine antiperiodische Funktion, und technisch gesehen haben wir eine negazyklische Faltung (engl. negacyclic convolution) der Länge . Solche Unterscheidungen verschwinden, wenn man zu einer Länge von auffüllt, wie oben beschrieben.

z-Transformationen Bearbeiten

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:

für eine beliebige komplexe Zahl und für unterschiedliche Zahlen und 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 die Folge von oben eine komplexe Sinuskurve mit linear anwachsender Frequenz ist, die in Radar-Systemen als (linearer) Chirp bezeichnet wird.

Literatur Bearbeiten

  • 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).

Einzelnachweise Bearbeiten

  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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Grosse 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 fur FFTs von grossen Datenmengen der die DFT als Faltung formuliert ist Raders Algorithmus Tatsachlich kann der Algorithmus von Leo Bluestein verwendet werden um allgemeinere Transformationen als DFT durchzufuhren basierend auf der unilateralen z Transformation 1 Inhaltsverzeichnis 1 Algorithmus 2 z Transformationen 3 Literatur 4 EinzelnachweiseAlgorithmus BearbeitenDie DFT wird definiert durch die Formel X k n 0 N 1 x n e 2 p i N n k n 0 N 1 x n e 2 n k p i N k 0 N 1 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 nbsp Wird das Produkt 2 n k displaystyle mathbf 2nk nbsp im Exponenten durch 2 n k k 2 n 2 k n 2 displaystyle mathbf 2nk mathbf k 2 mathbf n 2 mathbf k n 2 nbsp substituiert und e a b e a e b displaystyle e a b e a e b nbsp berucksichtigt ergibt sich X k e k 2 p i N n 0 N 1 x n e n 2 p i N e k n 2 p i N k 0 N 1 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 nbsp Diese Summation ist genau genommen eine Faltung der beiden Folgen a n displaystyle a n nbsp und b n displaystyle b n nbsp mit Lange N displaystyle N nbsp n 0 N 1 displaystyle n 0 ldots N 1 nbsp definiert durch a n x n e n 2 p i N displaystyle a n x n e n 2 frac pi i N nbsp b k n e k n 2 p i N displaystyle b k n e k n 2 frac pi i N nbsp mit dem Ergebnis der Faltung multipliziert mit N displaystyle N nbsp Phasenfaktoren b k displaystyle b k nbsp Das ergibt X k b k n 0 N 1 a n b k n k 0 N 1 displaystyle X k b k sum n 0 N 1 a n b k n qquad k 0 dots N 1 nbsp Diese Faltung kann wiederum durchgefuhrt werden mit einem Paar von FFTs und der vorausberechneten FFT von b n displaystyle b n nbsp mithilfe des Faltungstheorems Schlusselpunkt ist dass diese FFTs nicht von der gleichen Lange N displaystyle N nbsp sind solch eine Faltung kann von FFTs exakt nur berechnet werden durch Auffullen mit Nullen zu einer Lange grosser als oder gleich 2 N 1 displaystyle 2N 1 nbsp Insbesondere kann man zu einer Zweierpotenz oder einer anderen zusammengesetzten Zahl auffullen fur die die FFT effizient durchgefuhrt werden kann durch z B den Cooley Tukey FFT Algorithmus mit Ordnung O N log N displaystyle O N log N nbsp bezuglich der Rechenzeit Auf diese Weise bietet Bluesteins Algorithmus einen Weg der Ordnung O N log N displaystyle O N log N nbsp zur Berechnung von DFTs mit Primzahl Grosse auch wenn er um einige Faktoren langsamer ist als der Cooley Tukey Algorithmus fur zusammengesetzte Zahlen Das Auffullen mit Nullen fur die Faltung in Bluesteins Algorithmus benotigt eine zusatzliche Erlauterung Angenommen wir fullen Nullen auf bis zu einer Lange M 2 N 1 displaystyle M geq 2N 1 nbsp Das bedeutet dass a n displaystyle a n nbsp erweitert wird auf ein Feld A n displaystyle A n nbsp der Lange M displaystyle M nbsp wobei andernfalls A n a n displaystyle A n a n nbsp fur 0 n lt N displaystyle 0 leq n lt N nbsp und A n 0 displaystyle A n 0 nbsp ist die ursprungliche Bedeutung von zero padding Auffullen mit Nullen Dennoch werden wegen des Terms b k n displaystyle b k n nbsp in der Faltung sowohl positive als auch negative Werte von n displaystyle n nbsp benotigt fur b n displaystyle b n nbsp beachte dass b n b n displaystyle b n b n nbsp Die periodischen Randbedingungen die durch die DFT des mit Nullen aufgefullten Feldes impliziert werden bedeuten dass n displaystyle n nbsp aquivalent ist zu M n displaystyle M n nbsp Folglich wird b n displaystyle b n nbsp erweitert zu einem Feld B n displaystyle B n nbsp der Lange M displaystyle M nbsp wobei B 0 b 0 displaystyle B 0 b 0 nbsp B n B M n b n displaystyle B n B M n b n nbsp fur 1 n lt N displaystyle 1 leq n lt N nbsp und B n 0 displaystyle B n 0 nbsp sonst Betrachten wir also etwas genauer welcher Typ von Faltung in Bluesteins Algorithmus fur die DFT benotigt wird Ware die Folge b n displaystyle b n nbsp periodisch in n displaystyle n nbsp mit Periode N displaystyle N nbsp dann ware es eine zyklische Faltung der Lange N displaystyle N nbsp und das Auffullen mit Nullen diente nur der rechnerischen Bequemlichkeit Allerdings ist dies nicht generell der Fall b n N e p i N n N 2 b n e p i N 2 N n N 2 1 N b n 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 nbsp Folglich ist fur N displaystyle N nbsp gerade die Faltung zyklisch aber in diesem Falle ist N displaystyle N nbsp eine zusammengesetzte Zahl und normalerweise wurde man einen effizienteren FFT Algorithmus wie z B den nach Cooley Tukey wahlen Jedoch ist fur ungerade N displaystyle N nbsp das b n displaystyle b n nbsp eine antiperiodische Funktion und technisch gesehen haben wir eine negazyklische Faltung engl negacyclic convolution der Lange N displaystyle N nbsp Solche Unterscheidungen verschwinden wenn man a n displaystyle a n nbsp zu einer Lange von 2 N 1 displaystyle 2N 1 nbsp auffullt wie oben beschrieben z Transformationen BearbeitenBluesteins 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 n 0 N 1 x n z n k k 0 M 1 displaystyle X k sum n 0 N 1 x n z nk qquad k 0 dots M 1 nbsp fur eine beliebige komplexe Zahl z displaystyle z nbsp und fur unterschiedliche Zahlen N displaystyle N nbsp und M displaystyle M nbsp 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 Frequenzauflosung immer noch begrenzt wird durch die totale Messzeit Auch kann man beliebige Pole bei der Analyse von Ubertragungsfunktionen herausarbeiten usw Der Algorithmus wird als Chirp z Transformationsalgorithmus bezeichnet weil im Falle der Fourier Transformation mit z 1 displaystyle left z right 1 nbsp die Folge b n displaystyle b n nbsp von oben eine komplexe Sinuskurve mit linear anwachsender Frequenz ist die in Radar Systemen als linearer Chirp bezeichnet wird Literatur BearbeitenLeo 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 veroffentlicht 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 fur die z Transformation nicht standardgemass ist eine fraktionale Fourier Transformation 2 bezieht sich ublicherweise auf eine vollig 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 gepragter Kommentar Einzelnachweise Bearbeiten 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 veroffentlicht 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 siehe fractional Fourier transform in der englischen Wikipedia Abgerufen von https de wikipedia org w index php title Bluestein FFT Algorithmus amp oldid 229278723