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

Owing 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(2) and radix-2(3) algorithms. Results show that radix-2(2) and radix-2(3) have significantly less computational complexity compared with radix-2. Another interesting result is that while the number of complex multiplications in radix-2(3) algorithm is slightly more than radix-2(2), the number of real multiplications for radix-2(3) is less than radix-2(2). This is because of the twiddle factors in the form of [Image: see text] which need less number of real multiplications and are more frequent in radix-2(3) algorithm.