Data-canonic real FFT flow-graphs for composite lengths

Yingjie Lao, Keshab K Parhi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


This paper presents a novel algorithm to compute real-valued fast Fourier transform (RFFT) that is canonic with respect to the number of signal values. A signal value can correspond to a purely real or purely imaginary value, while a complex signal consists of 2 signal values. For an N-point RFFT, each stage need not compute more than N signal values, since the degrees of freedom of the input data is N. Any more than N signal values computed at any stage is inherently redundant. Canonic RFFT algorithms are defined as those RFFT algorithms that have the least number of signals at each FFT stage. In order to reduce the redundant samples, a sample removal lemma, and two types of twiddle factor transformations are proposed: pushing and modulation. We consider 4 different cases. Canonic RFFT for any composite length can be computed by applying the proposed algorithm recursively. Performances of different RFFTs are also discussed in this paper. The major advantages of the canonic RFFTs are that they require the least butterfly operations, lead to more regular sub-blocks in the data-flow, and only involve real datapath when mapped to architectures.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Workshop on Signal Processing Systems, SiPS 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781509033614
StatePublished - Dec 9 2016
Event2016 IEEE International Workshop on Signal Processing Systems, SiPS 2016 - Dallas, United States
Duration: Oct 26 2016Oct 28 2016


Other2016 IEEE International Workshop on Signal Processing Systems, SiPS 2016
Country/TerritoryUnited States


Dive into the research topics of 'Data-canonic real FFT flow-graphs for composite lengths'. Together they form a unique fingerprint.

Cite this