Calculation of Computational Complexity for Radix-2p Fast Fourier Transform Algorithms for Medical Signals

Abstract

Due to its simplicity radix-2 is a popular algorithm to implement Fast Fourier Transform. Radix-2^p algorithms have the same order of computational complexity as higher radices algorithms, but still retain the simplicity of radix-2. By defining a new concept, Twiddle Factor Template, in this paper we propose a method for exact calculation of multiplicative complexity for radix-2^p algorithms. The methodology is described for radix-2, radix-2² and radix-2³ algorithms. Results show that radix-2² and radix-2³ have significantly less computational complexity compared to radix-2. Another interesting result is that while the number of complex multiplications in radix-2³ algorithm is slightly more than radix-2², the number of real multiplications for radix-2³ is less than radix-2².