PeakLab v1 Documentation Contents            AIST Software Home            AIST Software Support

FFT Algorithms

PeakLab offers four different FFT algorithms and a composite procedure that minimizes computation time.

FFT Radix 2

This is the conventional power of 2 FFT procedure. PeakLab 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, and 16777216. If the data size is not a power of 2, zeros are appended to the next larger n.

Prime Factor

The prime factor FFT procedure used in PeakLab processes primes through 13. PeakLab uses an implementation of Temperton's Prime Factor FFT (C. Temperton, "Implementation of a Self-Sorting In-Place Prime Factor FFT Algorithm", Journal of Computational Physics, v. 58, p. 283, 1985). 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. For other sizes, zeros are appended to the next larger n. This is the second fastest of the FFT procedures. If the data size exceeds 1441440, the Chirp-Z algorithm is automatically used.

Mixed Radix

The mixed radix FFT algorithm processes any size n exactly. PeakLab uses a modification of Singleton's mixed radix algorithm (R. C. Singleton, "An Algorithm for Computing the Mixed Radix Fast Fourier Transform", IEEE Trans. Audio Electroacoust., v. AU-17, p. 93, June 1969) that removes the size limitation. This algorithm is slower than the radix 2 and prime factor procedures.

Chirp-Z

The Chirp-Z FFT algorithm (L. R. Rabiner, R. W. Schafer, C. M. Rader, "The Chirp z-Transform Algorithm and Its Application", BSTJ, 48, p.1249, May-June 1969) can also be used to exactly process any size n. The PeakLab 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.

Best Exact N

This is the recommended algorithm for most procedures within PeakLab that use the FFT. If the data size is a power of 2, the FFT Radix 2 algorithm is used. If not and the size is included in the prime-factor set, then the Prime Factor procedure is used. Otherwise, the Mixed Radix algorithm is used if the largest prime <= 509 and the Chirp-Z is used if the largest prime >= 521. This produces the fastest possible exact-n FFT.