Efficient Decomposition of Multistage Composite Length FFT for Complex and Real Signals

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.