TY - GEN

T1 - Canonic real-valued FFT structures

AU - Parhi, Megha

AU - Lao, Yingjie

AU - Parhi, Keshab K.

PY - 2015/4/24

Y1 - 2015/4/24

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

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

KW - Canonic FFT

KW - Decimation-in-frequency

KW - Decimation-in-time

KW - Fast fourier transform (FFT)

KW - Real-valued FFT

KW - Twiddle factor transformation

UR - http://www.scopus.com/inward/record.url?scp=84940561633&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84940561633&partnerID=8YFLogxK

U2 - 10.1109/ACSSC.2014.7094662

DO - 10.1109/ACSSC.2014.7094662

M3 - Conference contribution

AN - SCOPUS:84940561633

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 1261

EP - 1265

BT - Conference Record of the 48th Asilomar Conference on Signals, Systems and Computers

A2 - Matthews, Michael B.

PB - IEEE Computer Society

T2 - 48th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015

Y2 - 2 November 2014 through 5 November 2014

ER -