Radix-4 FFT contre Radix-2

Une implémentation radix-4 est-elle plus rapide qu'une FFT radix-2 codée de manière équivalente? Et si oui, pourquoi serait-ce plus rapide?

Ça dépend. Théoriquement, vous pouvez enregistrer quelques multiplications avec un radix-4 car radix-4 a un 1/4 du nombre de papillons et 3 mpy + 8 ajouts par papillon (s'il est correctement structuré) et le radix 2 a 1 mpy + 2 ajouts par papillon .

Donc, en termes de multiplications, c'est un peu mieux, mais la complexité est plus grande en termes de structure de code, de gestion des exceptions, de gestion des coefficients, de gestion des registres, d'adressage numérique inverse, etc.

Ce n'est donc un avantage que si le nombre de mpy est le facteur limitant qui pour la plupart du matériel de nos jours n'est pas le cas.

ici ! vous pouvez trouver une explication des principales différences entre les deux algorithmes pour la FFT. À la fin du document, il y a quelques tableaux dans lesquels il est possible de noter que, si la taille des données augmente, les performances du radix-4 fft sont meilleures que celles du radix-2.

une façon simple de voir une FFT radix-4 est de penser à un papillon radix-4 comme contenant 4 papillons radix-2; 2 papillons dans une passe et 2 papillons dans la passe suivante. et les facteurs de torsion sont les mêmes sauf que le facteur de torsion complexe pour les papillons est désactivé par une différence de phase de . mais tout cela signifie échanger avec et échanger des signes plus et moins. ainsi votre radix-4 FFT alg n'a besoin de lire les 4 valeurs complexes qu'une seule fois, de les charger une fois dans le twiddle complexe, de faire un tas d'arithmétique et de stocker les 4 résultats une fois. vous effectuez une passe radix-4 et vous accomplissez la même tâche que deux passes radix-2. sin(⋅)cos(⋅$\frac{\pi}{2}$$\sin(\cdot)$$\cos(\cdot)$

Je pense que le nombre net de multiplications et d'additions est le même, mais le papillon radix-4 peut être fait dans la banque de registres du processeur (je pense qu'il y a environ 16 registres à virgule flottante différents et vous avez besoin de 8 pour les parties réelle et imagée des 4 valeurs, 2 registres pour les twiddles sin et cosinus, et peut-être un autre registre ou deux pour scratch). c'est plus rapide que de le faire en mémoire.

Dans radix 2, le nombre d'échantillons est en termes de puissance de 2 puissances mais dans radix 4 le nombre d'échantillons appartient est une puissance de 4.