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

Rasoul Amirfattahi

DOI:

Abstract


Due to its simplicity radix-2 is a popular algorithm to implement Fast Fourier Transform. Radix-2p 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-2p algorithms. The methodology is described for radix-2, radix-22 and radix-23 algorithms. Results show that radix-22 and radix-23 have significantly less computational complexity compared to radix-2. Another interesting result is that while the number of complex multiplications in radix-23 algorithm is slightly more than radix-22, the number of real multiplications for radix-23 is less than radix-22.


Keywords


Fast Fourier Transform; radix-2p; Computational Complexity; Medical Signals

Full Text:

PDF

Refbacks

  • There are currently no refbacks.