Generation of All Radix-2 Fast Fourier Transform Algorithms Using Binary Trees and Its Analysis
2011 (English)In: Proceedings of ECCTD 2011: 20th EuropeanConference on Circuit Theory and Design (ECCTD), IEEE , 2011, 677-680 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
IEEE , 2011. 677-680 p.
IdentifiersURN: urn:nbn:se:liu:diva-74756DOI: 10.1109/ECCTD.2011.6043634ISBN: 978-1-4577-0616-5 (www)ISBN: 978-1-4577-0617-2 (print)OAI: oai:DiVA.org:liu-74756DiVA: diva2:491952
20th European Conference on Circuit Theory and Design (ECCTD), 29-31 August, Linköping, Sweden