Ist eine Radix-4-Implementierung schneller als eine gleich gut codierte Radix-2-FFT? Und wenn ja, warum sollte es schneller sein?
10
Es hängt davon ab, ob. Theoretisch können Sie mit einem Radix-4 einige Multiplikationen speichern, da Radix-4 1/4 der Anzahl der Schmetterlinge und 3 Mpy + 8 Adds pro Schmetterling (wenn richtig strukturiert) und der Radix 2 1 Mpy + 2 Adds pro Schmetterling hat .
In Bezug auf Multiplikationen ist es etwas besser, jedoch gibt es eine höhere Komplexität in Bezug auf Codestruktur, Ausnahmebehandlung, Koeffizientenverwaltung, Registerverwaltung, Ziffernumkehradressierung usw.
Es ist also nur dann von Vorteil, wenn die Anzahl der MPY der begrenzende Faktor ist, was für die meisten Hardware heutzutage nicht der Fall ist.
hier ! Hier finden Sie eine Erklärung der Hauptunterschiede zwischen den beiden Algorithmen für die FFT. Am Ende des Dokuments befinden sich einige Tabellen, in denen festgestellt werden kann, dass die Leistung des radix-4 fft bei zunehmender Datengröße besser ist als die des radix-2.
Die Nettozahl der Multiplikationen und Additionen ist meiner Meinung nach gleich, aber der Radix-4-Butterfly kann alle in der Prozessorregisterbank ausgeführt werden (ich denke, es gibt ungefähr 16 verschiedene Gleitkommaregister und Sie benötigen 8 für den Real- und Imageteil von den 4 Werten 2 Register für die Sinus- und Cosinus-Twiddles und möglicherweise ein oder zwei andere Register für Scratch). Dies ist schneller als im Speicher.
In Radix 2 ist die Anzahl der Abtastwerte in Bezug auf die Leistung von 2 Potenzen angegeben, in Radix 4 ist die Anzahl der zugehörigen Abtastwerte eine Potenz von 4.