An efficient FFT algorithm based on building on-line butterfly sub-structure

In most electrophysiological signals like EEG (electroencephalograph), frequency characteristics play an important role in quantifying the signals. This paper presents a new method of implementing the fast Fourier transform (FFT), the “real-time FFT algorithm”, which efficiently utilizes the computer time to perform the FFT computation while the data acquisition proceeds. The main idea is to build the local butterfly modules using the data points available. The algorithm is based on the decimation-in-time split-radix FFT (DIT sr-FFT) butterfly structure. The algorithm is superior to the conventional whole-block FFT algorithm in synchronizing with the on-line process. The time delay is about 2/r that of the whole-block algorithm considering the FFT size N=2^r