Efficient Decomposition of Multistage Composite Length FFT for Complex and Real Signals
- 16 February 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 74 (1053587X) , 892-903
Abstract
Fast Fourier Transform (FFT) algorithms play a fundamental role in modern digital signal processing (DSP). A composite length FFT decomposes a longer-length FFT into multiple shorter-length FFTs, enabling a bottom-up construction approach. If the input signal is complex-valued (real-valued), the DFT computation is referred as CFFT (RFFT). If the input is real-valued, redundancies and symmetries in the RFFT can be exploited to design more efficient algorithms. In this work, we extend the concept of two-stage composite FFTs to multistage composite FFTs. In a multistage FFT, the decomposition and parenthesization of sub-blocks significantly affect the structure’s efficiency. Although the set of sub-blocks remains the same, different parenthesizations lead to varying numbers of twiddle factor multiplications in the interconnect stages. We adopt radix-2 FFTs as the fundamental building blocks and apply dynamic programming to determine the optimal decomposition and parenthesization for arbitrary power-of-two FFT lengths. Our work presents optimal strategies for both complex-valued and real-valued FFTs. Compared to the radix-2 FFT, our multistage FFT reduces the number of complex multiplications by approximately 20% for complex-valued inputs and 30% for real-valued inputs. These results demonstrate that the multistage FFT approach not only simplifies the design process but also improves computational efficiency by significantly reducing the number of complex multiplications. Furthermore, the composite multistage structure enables an efficient bottom-up design methodology, requiring only two types of sub-blocks for CFFT and four types for RFFT implementations. Designers can follow the proposed straightforward design strategies, which guarantee the construction of optimal CFFT and RFFT structures.Keywords
Funding Information
- National Science Foundation (CCF-2243053)
This publication has 24 references indexed in Scilit:
- An Efficient Real-Valued Cross-Correlator via Fast Fourier Transform2024
- Canonic Composite Length Real-Valued FFTJournal of Signal Processing Systems, 2017
- Canonic real-valued radix-2n FFT computations2015
- Catalan Numbers2015
- Canonic real-valued FFT structures2014
- Fast fourier transforms: A tutorial review and a state of the artSignal Processing, 1990
- Real-valued fast Fourier transform algorithmsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1987
- ‘Split radix’ FFT algorithmElectronics Letters, 1984
- The design of optimal DFT algorithms using dynamic programmingIEEE Transactions on Acoustics, Speech, and Signal Processing, 1983
- The Fast Fourier Transform1982