Generation of all radix-2 fast Fourier transform algorithms using binary trees

Fahad Qureshi; Oscar Gustafsson

doi:10.1109/ECCTD.2011.6043634

Generation of all radix-2 fast Fourier transform algorithms using binary trees

Fahad Qureshi, Oscar Gustafsson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

25 Citations (Scopus)

Abstract

In this work a systematic method to generate all possible fast Fourier transform (FFT) algorithms is proposed based on the relation to binary trees. The binary tree is used to represent the decomposition of a discrete Fourier transform (DFT) into sub-DFTs. The radix is adaptively changed according to compute sub-DFTs in proposed decomposition. In this work we determine the number of possible algorithms for 2ⁿ-point FFTs with radix-2 butterfly operation and propose a simple method to determine the twiddle factor indices for each algorithm based on the binary tree representation.

Original language	English
Title of host publication	2011 20th European Conference on Circuit Theory and Design, ECCTD 2011
Pages	677-680
Number of pages	4
DOIs	https://doi.org/10.1109/ECCTD.2011.6043634
Publication status	Published - 2011
Publication type	A4 Article in conference proceedings
Event	2011 20th European Conference on Circuit Theory and Design, ECCTD 2011 - Linkoping, Sweden Duration: 29 Aug 2011 → 31 Aug 2011

Conference

Conference	2011 20th European Conference on Circuit Theory and Design, ECCTD 2011
Country/Territory	Sweden
City	Linkoping
Period	29/08/11 → 31/08/11

ASJC Scopus subject areas

Hardware and Architecture
Electrical and Electronic Engineering

Access to Document

10.1109/ECCTD.2011.6043634

Cite this

@inproceedings{9468ea93a5084cb889a927ecc116b800,

title = "Generation of all radix-2 fast Fourier transform algorithms using binary trees",

abstract = "In this work a systematic method to generate all possible fast Fourier transform (FFT) algorithms is proposed based on the relation to binary trees. The binary tree is used to represent the decomposition of a discrete Fourier transform (DFT) into sub-DFTs. The radix is adaptively changed according to compute sub-DFTs in proposed decomposition. In this work we determine the number of possible algorithms for 2n-point FFTs with radix-2 butterfly operation and propose a simple method to determine the twiddle factor indices for each algorithm based on the binary tree representation.",

author = "Fahad Qureshi and Oscar Gustafsson",

year = "2011",

doi = "10.1109/ECCTD.2011.6043634",

language = "English",

isbn = "9781457706189",

pages = "677--680",

booktitle = "2011 20th European Conference on Circuit Theory and Design, ECCTD 2011",

note = "2011 20th European Conference on Circuit Theory and Design, ECCTD 2011 ; Conference date: 29-08-2011 Through 31-08-2011",

}

TY - GEN

T1 - Generation of all radix-2 fast Fourier transform algorithms using binary trees

AU - Qureshi, Fahad

AU - Gustafsson, Oscar

PY - 2011

Y1 - 2011

N2 - In this work a systematic method to generate all possible fast Fourier transform (FFT) algorithms is proposed based on the relation to binary trees. The binary tree is used to represent the decomposition of a discrete Fourier transform (DFT) into sub-DFTs. The radix is adaptively changed according to compute sub-DFTs in proposed decomposition. In this work we determine the number of possible algorithms for 2n-point FFTs with radix-2 butterfly operation and propose a simple method to determine the twiddle factor indices for each algorithm based on the binary tree representation.

AB - In this work a systematic method to generate all possible fast Fourier transform (FFT) algorithms is proposed based on the relation to binary trees. The binary tree is used to represent the decomposition of a discrete Fourier transform (DFT) into sub-DFTs. The radix is adaptively changed according to compute sub-DFTs in proposed decomposition. In this work we determine the number of possible algorithms for 2n-point FFTs with radix-2 butterfly operation and propose a simple method to determine the twiddle factor indices for each algorithm based on the binary tree representation.

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

U2 - 10.1109/ECCTD.2011.6043634

DO - 10.1109/ECCTD.2011.6043634

M3 - Conference contribution

AN - SCOPUS:80355128275

SN - 9781457706189

SP - 677

EP - 680

BT - 2011 20th European Conference on Circuit Theory and Design, ECCTD 2011

T2 - 2011 20th European Conference on Circuit Theory and Design, ECCTD 2011

Y2 - 29 August 2011 through 31 August 2011

ER -

Generation of all radix-2 fast Fourier transform algorithms using binary trees

Abstract

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this