FlexPro's best-exact-n FFT uses four different FFT algorithms to minimizes computation time based on the size of the input data. If the data size or the selected FFT length is a power of 2, then the FFT Radix 2 algorithm is used. If this is not the case and the size is included in the prime-factor set, then the Prime Factor algorithm is used. Otherwise, the Mixed Radix algorithm is used if the largest prime <= 509 and the Chirp-Z algorithm is used if the largest prime factor >= 521. This produces the fastest possible exact-n FFT.

FFT Radix 2

This is the conventional power of 2 FFT procedure. FlexPro supports the following 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, 268435456, 536870912, 1073741824 and 2147483648 = 2^31. This is the fastest of the FFT algorithms.

Prime Factor

The prime factor FFT procedure used in FlexPro processes primes through 13. FlexPro uses an implementation of Temperton's Prime Factor FFT. For real data, the following n are processed exactly: 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, and 1441440. This is the second fastest FFT algorithm.

Mixed Radix

The mixed radix FFT algorithm processes any size n exactly. FlexPro uses a modification of Singleton's mixed radix algorithm that removes the size limitation. This algorithm is slower than the radix 2 and prime factor procedures.

Chirp-Z

The Chirp-Z FFT algorithm can process any size n. The FlexPro Chirp-Z implementation computes the z-transform at n equally spaced points on the unit circle, reproducing the FFT. The fast convolution requires two radix-2 FFT forward transforms and 1 FFT inverse. When very large primes are present, this algorithm is faster than the mixed radix procedure.

References

•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