Canonic Composite Length Real-Valued FFT

Yingjie Lao, Keshab K Parhi

Research output: Contribution to journalArticle

Abstract

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 needs not compute more than N signal values, since the degrees of freedom of the input data are N. Any more than N signal values computed at any stage is inherently redundant. 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 for an N = P × Q point canonic RFFT: 1) P is odd, Q is odd; 2) P is odd, Q is even; 3) P is even, Q is odd; and 4) P is even, Q is even. No twiddle factor transformation is required when P is odd. It is shown that the number of twiddle factors can be reduced by performing modulation transformation when P is even and Q is odd, while 2 real twiddle factor operations are pushed to 1 complex twiddle factor operation when P and Q are both even. 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 number of butterfly operations, lead to more regular sub-blocks in the data-flow, and only involve real datapath when mapped to architectures. However, we also show that canonic RFFTs may not be desirable when taking the cost of twiddle factor operations as the major consideration.

Original languageEnglish (US)
Pages (from-to)1401-1414
Number of pages14
JournalJournal of Signal Processing Systems
Volume90
Issue number10
DOIs
StatePublished - Oct 1 2018

Fingerprint

Fast Fourier transforms
Odd
Composite
Fast Fourier transform
Composite materials
Modulation
Data Flow
Lemma
Degree of freedom
Costs

Keywords

  • Canonic data-graph
  • Composite length
  • Decimation-in-frequency (DIf)
  • Decimation-in-time (DIT)
  • Fast fourier transform (FFT)
  • Real-valued FFT (RFFT)
  • Sample removal lemma
  • Twiddle factor transformation

Cite this

Canonic Composite Length Real-Valued FFT. / Lao, Yingjie; Parhi, Keshab K.

In: Journal of Signal Processing Systems, Vol. 90, No. 10, 01.10.2018, p. 1401-1414.

Research output: Contribution to journalArticle

@article{7f04803242304be199076ddb48e01498,
title = "Canonic Composite Length Real-Valued FFT",
abstract = "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 needs not compute more than N signal values, since the degrees of freedom of the input data are N. Any more than N signal values computed at any stage is inherently redundant. 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 for an N = P × Q point canonic RFFT: 1) P is odd, Q is odd; 2) P is odd, Q is even; 3) P is even, Q is odd; and 4) P is even, Q is even. No twiddle factor transformation is required when P is odd. It is shown that the number of twiddle factors can be reduced by performing modulation transformation when P is even and Q is odd, while 2 real twiddle factor operations are pushed to 1 complex twiddle factor operation when P and Q are both even. 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 number of butterfly operations, lead to more regular sub-blocks in the data-flow, and only involve real datapath when mapped to architectures. However, we also show that canonic RFFTs may not be desirable when taking the cost of twiddle factor operations as the major consideration.",
keywords = "Canonic data-graph, Composite length, Decimation-in-frequency (DIf), Decimation-in-time (DIT), Fast fourier transform (FFT), Real-valued FFT (RFFT), Sample removal lemma, Twiddle factor transformation",
author = "Yingjie Lao and Parhi, {Keshab K}",
year = "2018",
month = "10",
day = "1",
doi = "10.1007/s11265-017-1296-9",
language = "English (US)",
volume = "90",
pages = "1401--1414",
journal = "Journal of Signal Processing Systems",
issn = "1939-8018",
publisher = "Springer New York",
number = "10",

}

TY - JOUR

T1 - Canonic Composite Length Real-Valued FFT

AU - Lao, Yingjie

AU - Parhi, Keshab K

PY - 2018/10/1

Y1 - 2018/10/1

N2 - 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 needs not compute more than N signal values, since the degrees of freedom of the input data are N. Any more than N signal values computed at any stage is inherently redundant. 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 for an N = P × Q point canonic RFFT: 1) P is odd, Q is odd; 2) P is odd, Q is even; 3) P is even, Q is odd; and 4) P is even, Q is even. No twiddle factor transformation is required when P is odd. It is shown that the number of twiddle factors can be reduced by performing modulation transformation when P is even and Q is odd, while 2 real twiddle factor operations are pushed to 1 complex twiddle factor operation when P and Q are both even. 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 number of butterfly operations, lead to more regular sub-blocks in the data-flow, and only involve real datapath when mapped to architectures. However, we also show that canonic RFFTs may not be desirable when taking the cost of twiddle factor operations as the major consideration.

AB - 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 needs not compute more than N signal values, since the degrees of freedom of the input data are N. Any more than N signal values computed at any stage is inherently redundant. 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 for an N = P × Q point canonic RFFT: 1) P is odd, Q is odd; 2) P is odd, Q is even; 3) P is even, Q is odd; and 4) P is even, Q is even. No twiddle factor transformation is required when P is odd. It is shown that the number of twiddle factors can be reduced by performing modulation transformation when P is even and Q is odd, while 2 real twiddle factor operations are pushed to 1 complex twiddle factor operation when P and Q are both even. 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 number of butterfly operations, lead to more regular sub-blocks in the data-flow, and only involve real datapath when mapped to architectures. However, we also show that canonic RFFTs may not be desirable when taking the cost of twiddle factor operations as the major consideration.

KW - Canonic data-graph

KW - Composite length

KW - Decimation-in-frequency (DIf)

KW - Decimation-in-time (DIT)

KW - Fast fourier transform (FFT)

KW - Real-valued FFT (RFFT)

KW - Sample removal lemma

KW - Twiddle factor transformation

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

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

U2 - 10.1007/s11265-017-1296-9

DO - 10.1007/s11265-017-1296-9

M3 - Article

VL - 90

SP - 1401

EP - 1414

JO - Journal of Signal Processing Systems

JF - Journal of Signal Processing Systems

SN - 1939-8018

IS - 10

ER -