Die in FlexPro verwendete "best-exact-n" FFT verwendet vier verschiedene FFT-Algorithmen in Abhängigkeit von der Größe des Datensatzes, um die Berechnungszeit zu minimieren. Wenn die Datensatzgröße bzw. die gewählte FFT-Länge eine Potenz von 2 ist, dann wird der FFT Radix 2 Algorithmus verwendet. Ist dies nicht der Fall, dann wird, wenn die Größe in der Menge der Primfaktoren liegt, der Prime Factor Algorithmus verwendet. Andernfalls wird der Mixed Radix Algorithmus verwendet, wenn der größte Primfaktor kleiner oder gleich 509 ist, und der Chirp-Z Algorithmus wird verwendet, wenn der größte Primfaktor größer oder gleich 521 ist. Dies stellt die schnellst-mögliche FFT für ein beliebiges n dar.

FFT Radix 2

Dies ist der konventionelle 2er-Potenz FFT Algorithmus. FlexPro unterstützt 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 und 2147483648 = 2^31. Dies ist der schnellste FFT-Algorithmus.

Prime Factor

Die in FlexPro verwendete Prime Factor FFT verarbeitet Primfaktoren bis 13. FlexPro verwendet eine Implementierung von Temperton's Primefaktoren FFT. Für reelle Daten, werden die folgenden n verarbeitet: 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, und 1441440. Dies ist der zweit-schnellste FFT-Algorithmus.

Mixed Radix

Der Mixed Radix FFT Algorithmus verarbeitet jedes n exakt. FlexPro verwendet eine Modifikation des Mixed Radix FFT Algorithmus von Singleton, welche die Größenbeschränkung für n aufhebt. Dieser Algorithmus ist langsamer als der Radix 2 und der Prime Factor Algorithmus.

Chirp-Z

Der Chirp-Z FFT Algorithmus kann jede Größe n verarbeiten. Die Chirp-Z Implementierung von FlexPro berechnet die Z-Transformation an n gleich verteilten Punkten auf dem Einheitskreis und reproduziert dadurch die FFT. Die schnelle Faltung benötigt zwei Radix 2 FFT Vorwärtstransformationen und eine inverse FFT. Wenn sehr große Primfaktoren vorhanden sind, ist dieser Algorithmus schneller als der Mixed Radix Algorithmus.

Literatur

•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