Split-Radix-FFT-Algorithmus - Split-radix FFT algorithm

Die Split-Radix-FFT ist ein schneller Fourier-Transformations- Algorithmus (FFT-Algorithmus) zur Berechnung der diskreten Fourier-Transformation (DFT). Sie wurde erstmals in einem anfangs wenig geschätzten Artikel von R. Yavne (1968) beschrieben und anschließend von verschiedenen Autoren gleichzeitig wiederentdeckt 1984. (Der Name "Split Radix" wurde von zwei dieser Neuerfinder, P. Duhamel und H. Hollmann, geprägt .) Insbesondere Split Radix ist eine Variante des Cooley-Tukey-FFT-Algorithmus , der eine Mischung der Radices 2 und 4 verwendet : Es drückt rekursiv eine DFT der Länge N als eine kleinere DFT der Länge N / 2 und zwei kleinere DFTs der Länge N / 4 aus.

Die Split-Radix-FFT hatte zusammen mit ihren Variationen lange Zeit die Auszeichnung, die niedrigste veröffentlichte Anzahl arithmetischer Operationen (genaue Gesamtzahl der erforderlichen reellen Additionen und Multiplikationen) zu erreichen, um eine DFT mit einer Potenz von zwei Größen N zu berechnen . Die arithmetische Zählung des ursprünglichen Split-Radix-Algorithmus wurde 2004 verbessert (mit den anfänglichen Gewinnen, die J. Van Buskirk in unveröffentlichten Arbeiten durch Handoptimierung für N = 64 [1] [2] erzielt hat ), aber es stellt sich heraus, dass dies der Fall ist kann durch eine Modifikation des geteilten Radix immer noch die neue niedrigste Anzahl erreichen (Johnson und Frigo, 2007). Obwohl die Anzahl der arithmetischen Operationen nicht der einzige Faktor (oder sogar notwendigerweise der dominierende Faktor) bei der Bestimmung der Zeit ist, die zur Berechnung einer DFT auf einem Computer erforderlich ist , ist die Frage nach der minimal möglichen Anzahl von langjährigem theoretischem Interesse. (Derzeit wurde keine enge Untergrenze für die Anzahl der Operationen nachgewiesen.)

Der Split-Radix-Algorithmus kann nur angewendet werden, wenn N ein Vielfaches von 4 ist. Da er jedoch eine DFT in kleinere DFTs zerlegt, kann er nach Wunsch mit jedem anderen FFT-Algorithmus kombiniert werden.

Split-Radix-Zerlegung

Denken Sie daran, dass die DFT durch die Formel definiert ist:

${\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} \ omega _ {N} ^ {nk}}$

wo ist eine ganze Zahl von bis und bezeichnet die primitive Wurzel der Einheit : ${\ displaystyle k}$${\ displaystyle 0}$${\ displaystyle N-1}$${\ displaystyle \ omega _ {N}}$

${\ displaystyle \ omega _ {N} = e ^ {- {\ frac {2 \ pi i} {N}}},}$

und damit : . ${\ displaystyle \ omega _ {N} ^ {N} = 1}$

Der Split-Radix-Algorithmus drückt diese Summation in drei kleineren Summationen aus. (Hier geben wir die "Dezimierung in der Zeit" -Version der Split-Radix-FFT an; die doppelte Dezimierung in der Frequenzversion ist im Wesentlichen genau die Umkehrung dieser Schritte.)

Zunächst eine Summierung über die geraden Indizes . Zweitens eine Summierung über die ungeraden Indizes, die in zwei Teile geteilt sind: und je nachdem, ob der Index 1 oder 3 Modulo 4 ist. Bezeichnet hier einen Index, der von 0 bis läuft . Die resultierenden Summierungen sehen wie folgt aus: ${\ displaystyle x_ {2n_ {2}}}$${\ displaystyle x_ {4n_ {4} +1}}$${\ displaystyle x_ {4n_ {4} +3}}$${\ displaystyle n_ {m}}$${\ displaystyle N / m-1}$

${\ displaystyle X_ {k} = \ sum _ {n_ {2} = 0} ^ {N / 2-1} x_ {2n_ {2}} \ omega _ {N / 2} ^ {n_ {2} k} + \ omega _ {N} ^ {k} \ sum _ {n_ {4} = 0} ^ {N / 4-1} x_ {4n_ {4} +1} \ omega _ {N / 4} ^ {n_ {4} k} + \ omega _ {N} ^ {3k} \ sum _ {n_ {4} = 0} ^ {N / 4-1} x_ {4n_ {4} +3} \ omega _ {N / 4} ^ {n_ {4} k}}$

wo wir die Tatsache genutzt haben, dass . Diese drei Summen entsprechen Teilen der Cooley-Tukey-Schritte Radix-2 (Größe N / 2) bzw. Radix-4 (Größe N / 4). (Die zugrunde liegende Idee ist, dass die Subtransformation mit geradem Index von Radix-2 keinen multiplikativen Faktor vor sich hat, daher sollte sie unverändert bleiben, während die Subtransformation mit ungeradem Index von Radix-2 durch die Kombination einer zweiten rekursiven Unterteilung Vorteile bietet .) ${\ displaystyle \ omega _ {N} ^ {mnk} = \ omega _ {N / m} ^ {nk}}$

Diese kleineren Summierungen sind nun genau DFTs der Länge N / 2 und N / 4, die rekursiv durchgeführt und dann rekombiniert werden können.

Insbesondere bezeichnen wir das Ergebnis der DFT der Länge N / 2 (für ) und bezeichnen und bezeichnen die Ergebnisse der DFTs der Länge N / 4 (für ). Dann ist die Ausgabe einfach: ${\ displaystyle U_ {k}}$${\ displaystyle k = 0, \ ldots, N / 2-1}$${\ displaystyle Z_ {k}}$${\ displaystyle Z '_ {k}}$${\ displaystyle k = 0, \ ldots, N / 4-1}$${\ displaystyle X_ {k}}$

${\ displaystyle X_ {k} = U_ {k} + \ omega _ {N} ^ {k} Z_ {k} + \ omega _ {N} ^ {3k} Z '_ {k}.}$

Dies führt jedoch unnötige Berechnungen durch, da sich herausstellt, dass viele Berechnungen mit geteilt werden . Insbesondere wenn wir N / 4 zu k addieren , werden die DFTs der Größe N / 4 nicht geändert (weil sie in k periodisch sind ), während die DFT der Größe N / 2 unverändert bleibt, wenn wir N / 2 zu k addieren . Die einzigen Dinge, die sich ändern, sind die und Begriffe, die als Twiddle-Faktoren bekannt sind . Hier verwenden wir die Identitäten: ${\ displaystyle k \ geq N / 4}$${\ displaystyle k <N / 4}$${\ displaystyle \ omega _ {N} ^ {k}}$${\ displaystyle \ omega _ {N} ^ {3k}}$

${\ displaystyle \ omega _ {N} ^ {k + N / 4} = - i \ omega _ {N} ^ {k}}$

${\ displaystyle \ omega _ {N} ^ {3 (k + N / 4)} = i \ omega _ {N} ^ {3k}}$

um endlich zu erreichen:

${\ displaystyle X_ {k} = U_ {k} + \ left (\ omega _ {N} ^ {k} Z_ {k} + \ omega _ {N} ^ {3k} Z '_ {k} \ right) ,}$

${\ displaystyle X_ {k + N / 2} = U_ {k} - \ left (\ omega _ {N} ^ {k} Z_ {k} + \ omega _ {N} ^ {3k} Z '_ {k }\Recht),}$

${\ displaystyle X_ {k + N / 4} = U_ {k + N / 4} -i \ left (\ omega _ {N} ^ {k} Z_ {k} - \ omega _ {N} ^ {3k} Z '_ {k} \ right),}$

${\ displaystyle X_ {k + 3N / 4} = U_ {k + N / 4} + i \ left (\ omega _ {N} ^ {k} Z_ {k} - \ omega _ {N} ^ {3k} Z '_ {k} \ right),}$

Dies gibt alle Ausgaben an, wenn wir in den obigen vier Ausdrücken von bis reichen . ${\ displaystyle X_ {k}}$${\ displaystyle k}$${\ displaystyle 0}$${\ displaystyle N / 4-1}$

Beachten Sie, dass diese Ausdrücke so angeordnet sind, dass wir die verschiedenen DFT-Ausgaben durch Paare von Additionen und Subtraktionen kombinieren müssen, die als Schmetterlinge bezeichnet werden . Um die minimale Operationszahl für diesen Algorithmus zu erhalten, müssen Sonderfälle für (wo die Twiddle-Faktoren Eins sind) und für (wo die Twiddle-Faktoren sind und schneller multipliziert werden können) berücksichtigt werden ; siehe z . B. Sorensen et al. (1986). Multiplikationen mit und werden normalerweise als frei gezählt (alle Negationen können absorbiert werden, indem Additionen in Subtraktionen umgewandelt werden oder umgekehrt). ${\ displaystyle k = 0}$${\ displaystyle k = N / 8}$${\ displaystyle (1 \ pm i) / {\ sqrt {2}}}$${\ displaystyle \ pm 1}$${\ displaystyle \ pm i}$

Diese Zerlegung wird rekursiv durchgeführt, wenn N eine Zweierpotenz ist. Die Basisfälle der Rekursion sind N = 1, wobei die DFT nur eine Kopie ist , und N = 2, wobei die DFT eine Addition und eine Subtraktion ist . ${\ displaystyle X_ {0} = x_ {0}}$${\ displaystyle X_ {0} = x_ {0} + x_ {1}}$${\ displaystyle X_ {1} = x_ {0} -x_ {1}}$

Diese Überlegungen führen zu einer Zählung: reelle Additionen und Multiplikationen, für N > 1 eine Zweierpotenz. Diese Zählung setzt voraus, dass für ungerade Potenzen von 2 der verbleibende Faktor von 2 (nach allen Split-Radix-Schritten, die N durch 4 teilen ) direkt von der DFT-Definition (4 reelle Additionen und Multiplikationen) oder äquivalent von a behandelt wird Radix-2 Cooley-Tukey-FFT-Schritt. ${\ displaystyle 4N \ log _ {2} N-6N + 8}$

Verweise

• R. Yavne, "Eine wirtschaftliche Methode zur Berechnung der diskreten Fourier-Transformation", in Proc. AFIPS Fall Joint Computer Conf. 33 , 115–125 (1968).
• P. Duhamel und H. Hollmann, "Split-Radix-FFT-Algorithmus", Electron. Lette. 20 (1), 14–16 (1984).
• M. Vetterli und HJ Nussbaumer, "Einfache FFT- und DCT-Algorithmen mit reduzierter Anzahl von Operationen", Signal Processing 6 (4), 267–278 (1984).
• JB Martens, "Rekursive zyklotomische Faktorisierung - ein neuer Algorithmus zur Berechnung der diskreten Fourier-Transformation", IEEE Trans. Acoust., Speech, Signal Processing 32 (4), 750–761 (1984).
• P. Duhamel und M. Vetterli, "Fast Fourier Transforms: Ein Tutorial Review und ein Stand der Technik", Signal Processing 19 , 259–299 (1990).
• SG Johnson und M. Frigo, " Eine modifizierte Split-Radix-FFT mit weniger arithmetischen Operationen ", IEEE Trans. Signalprozess. 55 (1), 111–119 (2007).
• Douglas L. Jones, " Split-Radix-FFT-Algorithmen ", Connexions -Website (2. November 2006).
• HV Sorensen, MT Heideman und CS Burrus, "Zur Berechnung der Split-Radix-FFT", IEEE Trans. Acoust., Speech, Signal Processing 34 (1), 152–156 (1986).