TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

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

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Otsikko2011 20th European Conference on Circuit Theory and Design, ECCTD 2011
Sivut677-680
Sivumäärä4
DOI - pysyväislinkit
TilaJulkaistu - 2011
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
Tapahtuma2011 20th European Conference on Circuit Theory and Design, ECCTD 2011 - Linkoping, Ruotsi
Kesto: 29 elokuuta 201131 elokuuta 2011

Conference

Conference2011 20th European Conference on Circuit Theory and Design, ECCTD 2011
MaaRuotsi
KaupunkiLinkoping
Ajanjakso29/08/1131/08/11

Tiivistelmä

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.