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, 268435456, 536870912, 1073741824 et 2147483648 = 2^31. C'est le plus rapide des algorithmes FFT.

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. Pour les données réelles, les n suivants sont traités exactement : 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. Il s'agit du deuxième algorithme FFT le plus rapide.

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 de Chirp-Z peut traiter n'importe quelle taille n. L'implémentation FlexPro Chirp-Z calcule la transformée en z en n points équidistants sur le cercle unitaire, reproduisant 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