0.8 The cooley-tukey fast fourier transform algorithm  (Page 6/8)

In [link] Mi and Ai refer to the number of real multiplications and real additions used by an FFT with i separately written butterflies.The first block has the counts for Radix-2, the second for Radix-4, the third for Radix-8, thefourth for Radix-16, and the last for the Split-Radix FFT. For the split-radix FFT, M3 and A3 refer to the two- butterfly-plus programand M5 and A5 refer to the three-butterfly program.

The first evaluations of FFT algorithms were in terms of the number of real multiplications required as that was the slowestoperation on the computer and, therefore, controlled the execution speed. Later with hardware arithmetic both the number ofmultiplications and additions became important. Modern systems have arithmetic speeds such that indexing and data transfer times becomeimportant factors. Morris [link] has looked at some of these problems and has developed a procedure called autogen to writepartially straight-line program code to significantly reduce overhead and speed up FFT run times. Some hardware, such as theTMS320 signal processing chip, has the multiply and add operations combined. Some machines have vector instructions or have parallelprocessors. Because the execution speed of an FFT depends not only on the algorithm, but also on the hardware architecture andcompiler, experiments must be run on the system to be used.

In many cases the unscrambler or bit-reverse-counter requires 10% of the execution time, therefore, if possible, it should beeliminated. In high-speed convolution where the convolution is done by multiplication of DFT's, a decimation-in-frequency FFT can becombined with a decimation-in-time inverse FFT to require no unscrambler. It is also possible for a radix-2 FFT to do theunscrambling inside the FFT but the structure is not very regular [link] , [link] . Special structures can be found in [link] and programs for data that are real or have special symmetries are in [link] , [link] , [link] .