Skip to main navigation Skip to search Skip to main content

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

Research output: Contribution to journal › Article › peer-review

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 to 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.

Original languageEnglish (US)
Pages (from-to)892-903
Number of pages12
JournalIEEE Transactions on Signal Processing
Volume74
DOIs
StatePublished - 2026

Bibliographical note

Publisher Copyright:
© 2026 IEEE. All rights reserved.

Keywords

  • Catalan numbers
  • Fast Fourier transform (FFT)
  • composite length FFT
  • dynamic programming
  • multistage decomposition
  • parenthesization
  • real FFT

Fingerprint

Dive into the research topics of 'Efficient Decomposition of Multistage Composite Length FFT for Complex and Real Signals'. Together they form a unique fingerprint.

Cite this