Radix-4 FFT kontra Radix-2

Czy implementacja Radix-4 jest szybsza niż równoważnie dobrze zakodowana FFT Radix-2? A jeśli tak, to dlaczego miałoby być szybsze?

To zależy. Teoretycznie możesz zapisać kilka pomnożeń za pomocą radix-4, ponieważ radix-4 ma 1/4 liczbę motyli i 3 mpy + 8 dodanych na motyla (jeśli jest odpowiednio skonstruowany), a radix 2 ma 1 mpy + 2 dodanych na motyla .

Pod względem mnożników jest to nieco lepsze, jednak występuje większa złożoność pod względem struktury kodu, obsługi wyjątków, zarządzania współczynnikami, zarządzania rejestrami, adresowania odwrotnego cyfr itp.

Zatem zaletą jest to, że liczba mpy jest czynnikiem ograniczającym, co w przypadku większości urządzeń w dzisiejszych czasach nie ma miejsca.

tutaj ! można znaleźć wyjaśnienie głównych różnic między dwoma algorytmami dla FFT. Na końcu dokumentu znajduje się kilka tabel, w których można zauważyć, że jeśli rozmiar danych wzrośnie, wydajność radix-4 fft jest lepsza niż radix-2.

$\frac{\pi}{2}$$\sin(\cdot)$$\cos(\cdot)$

myślę, że liczba mnożeń i dodatków netto jest taka sama, ale motyl Radix-4 można zrobić w banku rejestrów procesora (wydaje mi się, że istnieje około 16 różnych rejestrów zmiennoprzecinkowych i potrzebujesz 8 dla części rzeczywistych i imagowych z 4 wartości, 2 rejestry dla grzechu sinus i cosinus, a może jakiś inny rejestr lub dwa dla zera). jest to szybsze niż robienie tego w pamięci.

W radix 2 liczba próbek jest pod względem mocy 2 mocy, ale w Radix 4 liczba próbek należy do potęgi 4.