Generation of All Radix-2 Fast Fourier Transform Algorithms Using Binary Trees and Its Analysis
(English)Manuscript (preprint) (Other academic)
This paper presents a systematic method to generate number of possible algorithms that can be used to calculate the fast Fourier transform. 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. We analyze the differences among these algorithms in terms of switching activity, which is related to the power consumption of the circuit, size of the coefficient memories, which is related to the area of the circuit, and round-off effect, which is related to accuracy of circuit.
Experimental results show which are the most efficient algorithms in term of area, power consumption, and accuracy. Furthermore, the paper shows the importance of a proper selection of the algorithm, since efficient algorithms can lead to savings of 45% in the coefficient memory and even greater than 50% in switching activity and total round-off noise with respect to other less efficient ones.
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-74757OAI: oai:DiVA.org:liu-74757DiVA: diva2:491958