A simple fast fourier transformation algorithm to microcontrollers and mini computers

The fast Fourier transformation (FFT) is one of the most important algorithm in the world. The FFT efficiently calculates the frequency components of time-varying signals. In most cases, the digital signal processor and other applications use the FFT algorithm periodically. Consequently, even a small acceleration of the FFT algorithm greatly speeds up the whole application. This article presents an algorithm to the FFT which contains a reduced number of logical and elementary (addition, subtraction, multiplication) operations. Therefore, it is optimized to the low level programming and hardware description languages and it is well applicable in field programmable gate arrays (FPGAs), microcontrollers, digital signal processors and any type of computers.