Volume 13, Issue 4
The Multiplicative Complexity and Algorithm of the Generalized Discrete Fourier Transform(GFT)

J. Comp. Math., 13 (1995), pp. 351-356

Preview Full PDF BiBTex 0 351
• Abstract

In this paper, we have proved that the lower bound of the number of real multiplications for computing a length $2^{t}$ real GFT(a,b) $(a=\pm 1/2,b=0\ or\ b=\pm 1/2,a=0)$ is $2^{t+1}-2t-2$ and that for computing a length $2^{t}$ real GFT(a,b)$(a=\pm 1/2, b=\pm 1/2)$ is $2^{t+1}-2$. Practical algorithms which meet the lower bounds of multiplications are given.

• History

Published online: 1995-08

• Keywords