Real-time implementation of the split-radix FFT - An algorithm to efficiently construct local butterfly modules

Pei-Chen Lo, Yu Yun Lee

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

This paper presents a new technique of real-time Fourier spectral analysis based on the decimation-in-time split-radix fast-Fourier-transform (DIT sr-FFT) butterfly structure. The new algorithm (to be called the 'real-time FFT algorithm'), designed in a multi-tasking environment, efficiently utilizes the computer time. It simultaneously constructs the sr-FFT butterfly structure while the data acquisition proceeds. Hence, it provides a practical, useful approach to analyzing the on-line, time-varying Fourier spectra for the multi-channel electrophysiological signals. The authors propose a strategy of identifying the local butterfly sub-structures (modules) ready to be constructed when only a portion of the input data array is available. In addition, we develop an alternative way to analyze the computational complexity of the real-time FFT algorithm. To evaluate the efficiency of the algorithm, we calculate the number of complex arithmetic operations required to complete the rest butterfly sub-structures upon receipt of the last data point. The result shows that the efficiency of the algorithm increases with N (the FFT size).

Original languageEnglish
Pages (from-to)291-299
Number of pages9
JournalSignal Processing
Volume71
Issue number3
DOIs
StatePublished - 18 Dec 1998

Keywords

  • Local butterfly sub-structure
  • Multi-channel electrophysiological signal processing
  • Real-time frequency analysis
  • Split-radix FFT

Fingerprint Dive into the research topics of 'Real-time implementation of the split-radix FFT - An algorithm to efficiently construct local butterfly modules'. Together they form a unique fingerprint.

  • Cite this