3
$\begingroup$

There are many algorithms that can calculate FFT. Even with Cooley–Tukey FFT algorithm, different radix can be used and the algorithms can divided into decimation in time and decimation in frequency. Any comment on how to choose these algorithms in practice?

$\endgroup$
  • 4
    $\begingroup$ just get FFTW and let it learn its "wisdom" on your machine and it will pick the best combination of algs. $\endgroup$ – robert bristow-johnson Apr 24 '14 at 3:50
  • 2
    $\begingroup$ @kattern - It depends. Some people need a rocket ship - others need a bicycle. For example: at one research review for a radar processor in the late 1980's, they had, among other things, requirements for: continuous operation, very low latency, 10 nanosecond time between samples, etc. Good luck trying to do that in software. The researchers chose a very specific modified algorithm and a pipeline architecture to do the job. A review of the many hundreds of FFT processors in the patent literature might be helpful. $\endgroup$ – Kevin McGee Apr 25 '14 at 6:20
8
$\begingroup$

Both Cooley-Tukey and Radix DIT & DIF are based on the same principle, dividing the N samples into two groups, and doing the same for the resulting two groups recursively. DIT and DIF generally use Radix2, that is, split N into two N/2 groups and provide a $N\log{N}$ time, while Cooley-Tukey is a generalization which splits it into $N_1$ and $N_2$ groups, where $N=N_1\cdot N_2$. Cooley-Tukey also provides $N\log{N}$ time in most cases.

Now, Radix DIT and DIF (both special cases of the Cooley-Tukey) are very similar and provide the same optimization in terms of operation savings, with the difference being bit reversed samples either on the input or the output. These can be done in $O(N)$ time, either before (DIT) or after (DIF) calculating the DFT.

Moreover, in some cases you don't even have do to the bit-reversal. Some applications (such as convolution) work equally well on bit-reversed data, so one can perform forward transforms, processing, and then inverse transforms all without bit reversal to produce final results in the natural order.

Finally, as an answer to your question, you can use Radix2 DIT or DIF FFT, depending on the application (see above paragraph), with the same result: Instead of:

$4N^2 \quad\text{real multiplications}\\ 4N^2-2N \quad\text{real additions}.$

We achieved:

$2N\log_2{N}-7N+12 \quad\text{real multiplications}\\ 3N\log_2{N}-3N+4 \quad \text{real additions}.$

Please note that Radix DIT and DIF algorithms require that $N=2^p$, which is generally easy to satisfy. Increasing the radix gives us $\log_4$ for radix4, etc., which increases the calculation complexity on hardware, and in turn decreases the number of operations by ~$25\%$. Radix 2 and 4 are considered the most common, while Radix 8 (~$8\%$ optimization) and up generally demand too complex hardware for too small optimizations. Cooley-Tukey gives similar results, with more room for tweaking - in case of a specific $N$, for example.

For further optimizations, there are the split-radix algorithm which uses both Radix 2 and Radix 4 , and many more application-specific algorithms.

Update: Other algorithms include:

  • Bruun's algorithm:

It's not used much because Cooley-Tukey algorithm offers at least the same, and often better optimization. It was developed as a means to calculate DFT of real data (as opposed to complex).

  • Rader's algorithm:

Rader's algorithm is used for cases where $N$ is a prime number, often a big prime number. Note that above mentioned algorithms require $N = 2^k$, so they don't really work for other $N$. Rader's algorithm guarantees $N\log{N}$ time for prime $N$.

  • Bluestein's algorithm:

Bluesten's algorithm calculates the DFT via convolution, and is another way of dealing with $N \neq 2^k$. For prime numbers, it offers $N\log{N}$ time, for even numbers Cooley-Tukey algorithm is better, and for odd numbers it offers a somewhat better time than Cooley-Tukey.

Please note, however, that for all such cases for $N$ it's possible to zero-pad the input series until we get an $N = 2^k$ and then use the Cooley-Tukey's algorithm. Of course, for prime $N$ it's more efficient to use Rader's or Bluestein's algorithms.

Moreover, these algorithms were developed at different points in time, so some are more efficient than the others.

$\endgroup$
  • $\begingroup$ Does Rader have any benefits over the more general Bluestein for prime lengths? $\endgroup$ – endolith Feb 16 '16 at 1:20

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.