3
$\begingroup$

Does FFT method input argument have to be power of 2, i.e, $2^n$
I just realized there are many algorithm for FFT implementation, is there any algorithm that takes arbitrary amount of samples as input argument?
if yes, what is their advantages amongst each other? namely, what algorithm does Matlab apply?

$\endgroup$
6
$\begingroup$

It is a common misconception that all FFT algorithms require their inputs to have a length that is a power of 2. The radix-2 Cooley-Tukey algorithm, the first to be widely known, has this limitation, but there are mixed-radix versions of the algorithm that don't require a power-of-2-sized input. In addition to Cooley-Tukey, there are a number of other FFT algorithms that have differing requirements on their input size; there are even techniques like Rader's algorithm that work on inputs whose sizes are prime.

Good, general purpose FFT implementations like MATLAB's fft() or FFTW support a wide range of algorithms and select one that is most appropriate for the specific situation. For more details on the specifics, go to the MATLAB documentation itself:

> doc fft

Algorithms

The FFT functions (fft, fft2, fftn, ifft, ifft2, ifftn) are based on a library called FFTW [3],[4]. To compute an N-point DFT when N is composite (that is, when N = N1N2), the FFTW library decomposes the problem using the Cooley-Tukey algorithm [1], which first computes N1 transforms of size N2, and then computes N2 transforms of size N1. The decomposition is applied recursively to both the N1- and N2-point DFTs until the problem can be solved using one of several machine-generated fixed-size "codelets." The codelets in turn use several algorithms in combination, including a variation of Cooley-Tukey [5], a prime factor algorithm [6], and a split-radix algorithm [2]. The particular factorization of N is chosen heuristically.

When N is a prime number, the FFTW library first decomposes an N-point problem into three (N – 1)-point problems using Rader's algorithm [7]. It then uses the Cooley-Tukey decomposition described above to compute the (N – 1)-point DFTs.

For most N, real-input DFTs require roughly half the computation time of complex-input DFTs. However, when N has large prime factors, there is little or no speed difference.

The execution time for fft depends on the length of the transform. It is fastest for powers of two. It is almost as fast for lengths that have only small prime factors. It is typically several times slower for lengths that are prime or which have large prime factors.

Note You might be able to increase the speed of fft using the utility function fftw, which controls the optimization of the algorithm used to compute an FFT of a particular size and dimension.

References

[1] Cooley, J. W. and J. W. Tukey, "An Algorithm for the Machine Computation of the Complex Fourier Series,"Mathematics of Computation, Vol. 19, April 1965, pp. 297-301.

[2] Duhamel, P. and M. Vetterli, "Fast Fourier Transforms: A Tutorial Review and a State of the Art," Signal Processing, Vol. 19, April 1990, pp. 259-299.

[3] FFTW (http://www.fftw.org)

[4] Frigo, M. and S. G. Johnson, "FFTW: An Adaptive Software Architecture for the FFT,"Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Vol. 3, 1998, pp. 1381-1384.

[5] Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, 1989, p. 611.

[6] Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, 1989, p. 619.

[7] Rader, C. M., "Discrete Fourier Transforms when the Number of Data Samples Is Prime," Proceedings of the IEEE, Vol. 56, June 1968, pp. 1107-1108.

$\endgroup$
1
  • $\begingroup$ Tnx @jason-r do they all have the same time complexity? $\endgroup$ – SAH Feb 21 '14 at 12:36
2
$\begingroup$

The simplest FFT to explain in a short text book chapter recursively factors a DFT length by 2, log2(N) times, thus only seems to work for lengths that are powers of 2. But you don't have to recursively divide-and-conquer all the way down to the last 2 elements, and you can also use the same basic algorithm to divide the length by other small factors, such as 3 or 5, etc. Thus, the "time" (actually number of arithmetic ops) complexity for any length that can be decomposed into mostly a lot of tiny prime factors is roughly the same.

There are also other methods for larger prime factors that require longer textbook chapters.

Thus, most advanced modern FFT libraries (FFTW, Accelerate/vDSP, etc.) can handle lot of lengths other than powers of 2. Anyway, the actual order of execution time performance on modern processors is more due to data cache and instruction scheduling issues than just the number of arithmetic operations, so lots of other things have to done to compute a Fast DFT equivalent, not just radix-2 reduction. Matlab uses one of these modern libraries.

But many simple canonical-looking (student exercise, minimal lines of code, etc.) FFTs only use the short textbook chapter methods for lengths that are powers of 2 (and ignore CPU cache, etc. issues). These short FFTs were also useful on older or tiny processors with very limited instruction memory. Thus the common misconception.

$\endgroup$
0
$\begingroup$

The basic idea of most "FFT" algorithms is to decompose the DFT of a non-prime length N = KM sequence into M DFTs of length K sequences and K DFTs of length M sequences, interconnected with N complex "twiddle factor" multiplications.

Since the multiplicative complexity of the direct realization is N^2 and the resulting complexity is MK^2 + KM^2 + N = N(K + M + 1) there will be savings as N > K + M + 1. Now, K and M can possibly be decomposed again and so on. If not, the DFT is evaluated straightforwardly (which for length 2 is really simple).

If N is prime there are other methods, Bluestein, Rader etc.

If M and K are coprime one can avoid the twiddle factor multiplications at the expense of a bit more complicated ordering of the sequences.

For short (but longer than two) lengths, there are more efficient methods in terms of multiplications than direct evaluation such that the Winograd short length DFT.

There are "split-radix" FFT algorithms, which divides the length into more than two parts. This is the case for FFTW, which splits the sequence in lengths N/2, N/4, and N/4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.