La FFT "best-exact-n" utilizada en FlexPro emplea cuatro algoritmos de FFT diferentes en función del tamaño del conjunto de datos para minimizar el tiempo de cálculo. Si el tamaño del conjunto de datos o la longitud FFT seleccionada es una potencia de 2, se utiliza el algoritmo FFT Radix 2. Si no es el caso, se utiliza el algoritmo Prime Factor si el tamaño se encuentra en el conjunto de los factores primos. En caso contrario, se utiliza el algoritmo Mixed Radix si el mayor factor primo es menor o igual a 509, y el algoritmo Chirp-Z si el mayor factor primo es mayor o igual a 521. Esto representa la FFT más rápida posible para cualquier n.
FFT Radix 2
Se trata del algoritmo FFT de potencia de 2 convencional. FlexPro soporta n: 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 y 268435456 = 2^28. Es el algoritmo FFT más rápido.
Prime Factor
La FFT Prime Factor utilizada en FlexPro procesa factores primos hasta 13. FlexPro utiliza una implementación de la FFT de factor primo de Temperton. Para los datos reales, se procesan los n siguientes: 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, y 1441440. Es el segundo algoritmo FFT más rápido.
Mixed Radix
El algoritmo FFT Mixed Radix procesa cada n exactamente. FlexPro utiliza una modificación del algoritmo FFT Mixed Radix de Singleton, que elimina la restricción de tamaño para n. Este algoritmo es más lento que el de Radix 2 y el de Prime Factor.
Chirp-Z
El algoritmo FFT Chirp-Z puede procesar cualquier tamaño n. La implementación Chirp-Z de FlexPro calcula la transformación Z en n puntos distribuidos equitativamente en el círculo unitario y reproduce así la FFT. La convolución rápida requiere dos transformaciones hacia delante FFT de radix 2 y una FFT inversa. Si se dispone de factores primos muy grandes, este algoritmo es más rápido que el algoritmo Mixed Radix.
Bibliografía
•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, junio de 1969
•L. R. Rabiner, R. W. Schafer, C. M. Rader, "The Chirp z-Transform Algorithm and Its Application", BSTJ, 48, pág. 1249, mayo-junio de 1969