Canonic real-valued FFT structures

Megha Parhi, Yingjie Lao, Keshab K. Parhi

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

5 Scopus citations

Abstract

An N-point FFT processes N complex signals to compute N output complex signals using decimation-in-time (DIT) or decimation-in-frequency (DIF) approach. The FFT makes use of n = log2N stages of computations where each stage computes N complex signals; N is assumed to be power-of-two. This paper considers implementation of a real signal of length N. Since the degrees of freedom of the input data is N, each stage of the FFT should not need to compute more than N signal values, where a signal value can corresponds to a purely real or purely imaginary value. Any more than N samples computed at any FFT stage is inherently redundant. This paper, for the first time, presents novel DIT and DIF structures for computing real FFT, referred as RFFT, that are canonic with respect to the number signal values computed at each FFT stage. In the proposed structure, in an N-point RFFT, exactly N signal values are computed at the output of each FFT stage and at the output. No prior canonic DIT RFFT structure was presented before. This paper, for the first time, presents a formal approach to compute RFFT using DIT in a canonic manner. While canonic FFT structures based on decimation-in-frequency were presented before, these structures were derived in an adhoc way. This paper presents a formal method to derive canonic DIF RFFT structures.

Original languageEnglish (US)
Title of host publicationConference Record of the 48th Asilomar Conference on Signals, Systems and Computers
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Pages1261-1265
Number of pages5
ISBN (Electronic)9781479982974
DOIs
StatePublished - Apr 24 2015
Event48th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 - Pacific Grove, United States
Duration: Nov 2 2014Nov 5 2014

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
Volume2015-April
ISSN (Print)1058-6393

Other

Other48th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
CountryUnited States
CityPacific Grove
Period11/2/1411/5/14

Keywords

  • Canonic FFT
  • Decimation-in-frequency
  • Decimation-in-time
  • Fast fourier transform (FFT)
  • Real-valued FFT
  • Twiddle factor transformation

Fingerprint Dive into the research topics of 'Canonic real-valued FFT structures'. Together they form a unique fingerprint.

Cite this