Multiply/Add tradeoffs in length-2>sup /sup
Michael T. Heideman, C.S. Burrus · 2005
The multiplicative complexity of the length-2ndiscrete Fourier Transform is derived. A constructive approach is followed which describes the set of algorithms that realize the minimum number of multiplications. The operation counts of minimum multiply algorithms are compared to other FFT algorithms. The basic method is extended to derive the multiplicative complexity of length-pnDFFs where p is an odd prime number.