La meilleure FFT exacte-n de FlexPro utilise quatre algorithmes FFT différents pour minimiser le temps de calcul en fonction de la taille des données d'entrée. Si la taille des données ou la longueur de la FFT sélectionnée est une puissance de 2, l'algorithme FFT Radix 2 est utilisé. Si ce n'est pas le cas et que la taille est incluse dans l'ensemble des facteurs principaux, l'algorithme des facteurs principaux est utilisé. Sinon, l'algorithme Mixed Radix est utilisé si le plus grand facteur premier <= 509 et l'algorithme Chirp-Z est utilisé si le plus grand facteur premier >= 521. Cela produit la FFT exacte-n la plus rapide possible.
FFT Radix 2
Il s'agit de la procédure FFT classique de puissance 2. FlexPro prend en charge les n suivants : 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728 et 268435456 = 2^28.
Prime Factor
La procédure FFT de facteur premier utilisée dans FlexPro traite les facteurs premiers jusqu'à 13. FlexPro utilise une implémentation de la FFT à facteur premier de Temperton. 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 36, 40, 42, 44, 48, 52, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 104, 110, 112, 120, 126, 130, 132, 140, 144, 154, 156, 160, 168, 176, 180, 182, 198, 208, 210, 220, 224, 234, 240, 252, 260, 264, 280, 286, 288, 308, 312, 330, 336, 352, 360, 364, 390, 396, 416, 420, 440, 462, 468, 480, 504, 520, 528, 546, 560, 572, 616, 624, 630, 660, 672, 720, 728, 770, 780, 792, 840, 858, 880, 910, 924, 936, 990, 1008, 1040, 1056, 1092, 1120, 1144, 1170, 1232, 1248, 1260, 1320, 1386, 1430, 1440, 1456, 1540, 1560, 1584, 1638, 1680, 1716, 1760, 1820, 1848, 1872, 1980, 2002, 2016, 2080, 2184, 2288, 2310, 2340, 2464, 2520, 2574, 2640, 2730, 2772, 2860, 2912, 3080, 3120, 3168, 3276, 3360, 3432, 3640, 3696, 3744, 3960, 4004, 4290, 4368, 4576, 4620, 4680, 5040, 5148, 5280, 5460, 5544, 5720, 6006, 6160, 6240, 6552, 6864, 6930, 7280, 7392, 7920, 8008, 8190, 8580, 8736, 9240, 9360, 10010, 10080, 10296, 10920, 11088, 11440, 12012, 12320, 12870, 13104, 13728, 13860, 14560, 15840, 16016, 16380, 17160, 18018, 18480, 18720, 20020, 20592, 21840, 22176, 22880, 24024, 25740, 26208, 27720, 30030, 32032, 32760, 34320, 36036, 36960, 40040, 41184, 43680, 48048, 51480, 55440, 60060, 65520, 68640, 72072, 80080, 90090, 96096, 102960, 110880, 120120, 131040, 144144, 160160, 180180, 205920, 240240, 288288, 360360, 480480, 720720, et 1441440.
Radix mélangé
L'algorithme FFT à radix mixte traite n'importe quelle taille n exactement. FlexPro utilise une modification de l'algorithme radix mixte de Singleton qui supprime la limitation de taille. Cet algorithme est plus lent que les procédures radix 2 et facteur premier.
Chirp-Z
L'algorithme FFT Chirp-Z peut traiter toute quantité n. L'implémentation Chirp-Z de FlexPro calcule la transformée Z en n points également répartis sur le cercle unitaire, reproduisant ainsi la FFT. La convolution rapide nécessite deux transformations avant FFT radix-2 et une transformation inverse FFT. En présence de très grands nombres premiers, cet algorithme est plus rapide que la procédure radix mixte.
Références
•C. Temperton, "Implementation of a Self-Sorting In-Place Prime Factor FFT Algorithm", Journal of Computational Physics, v. 58, p. 283, 1985
•R. C. Singleton, "An Algorithm for Computing the Mixed Radix Fast Fourier Transform", IEEE Trans. Audio Electroacoust., v. AU-17, p. 93, June 1969
•L. R. Rabiner, R. W. Schafer, C. M. Rader, "The Chirp z-Transform Algorithm and Its Application", BSTJ, 48, p.1249, May-June 1969