Relative evaluation of various number theoretic transforms for digital filtering applications
H. Nussbaumer · IEEE Transactions on Acoustics Speech and Signal Processing · 1978
The main existence conditions for pseudo Mersenne and pseudo Fermat number transforms defined in a ring submultiple of a pseudo Mersenne or pseudo Fermat number are defined. The computational complexity of various multiplication-free number theoretic transforms (NTT's) used for implementing digital filters is evaluated. It is shown that Fermat number transforms (FNT's) with root\sqrt{2}and some complex pseudo Mersenne and pseudo Fermat number transforms with root 1 + j yield optimum processing efficiency and allow significant computational savings over direct filter evaluation.