A new DSP‐oriented FFT algorithm
Naoki Mikami, Masahiro Matsuoka · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1989
Abstract In the traditional fast‐Fourier trans form (FFT) algorithm, the design for high‐ speed operation is made based on the number of operations, especially the number of multiplications, which is time‐consuming in the general‐purpose processor. This is not necessarily reasonable in the digital signal processor (DSP), where the multiplication can be performed in the time equal to that of other operations. From such a viewpoint, this paper proposes an algorithm which matches the feature of DSP, where the pro cessing is fast when the multiply‐accumulate operations are continued in execution. the algorithm is applicable when the number of data IV can be factorized into mutually prime factors. DFT for smaller number (factor) of data is modified into the cyclic convolution, and is executed at a high speed (small‐ N algorithm). the proposed algorithm is composed of the small‐N algorithms and DFT for a large number of data (multidimensional algorithm), which combines small‐N algorithms into a multidimensional DFT. the number of operations is not necessarily reduced in the proposed algorithm, compared with the traditional FFT, but it was verified by an actual run of the program on DSP that the execution time is reduced.