Fast Fourier transformation based on number theoretic transforms (Q1123580)

A technique, denoted as FFT/NTT \((FFT=fast\) Fourier transform, \(NTT=number\) theoretic transform), is proposed for the fast computation of DFT (discrete Fourier transform) of a real sequence with prime length \(p=2^ M+1\). This technique is essentially a modification of \textit{Rader}'s method [Proc. IEEE, Vol. 56, No.6, 1107-1108 (1968)] where DFT is computed via the cyclic convolution of size \(2^ M\) of a real sequence \(\{\) a(n)\(\}\) and a complex sequence \(\{b'(n)\}=\{b_ r')\}+j\{b_ i'(n)\}\), \(j=\sqrt{-1}\). Then normalization and quantization by \(a(n)=NINT[a'(n)\cdot NORM]\) and \(b_ r(n)+jb_ i(n)=NINT[b'(n)\cdot NORM]\) is performed (NORM is the scaling factor and NINT[\(\cdot]\) takes the nearest integer). Consequently two cyclic integer convolutions \(\{a(n)\}\cdot \{b_ r(n)\}\) and \(\{a(n)\}\cdot \{b_ i(n)\}\) are obtained which, due to the symmetry \(b_ r(n+N/2)=b_ r(n)\) and \(b_ i(n+N/2)=-b_ i(n)\), may be accomplished in parallel (as if computing \(\{a(n)\}*(\{b_ r(n)\}+\{b_ i(n)\}))\) and without bit reversal, when using two FORTRAN subroutines supplied in the appendix, one being the direct decimation-in-frequency NTT, the other the inverse decimation-in-time NTT (reviewer's cursory check on the code listing revealed a few errors). The use of the Chinese remainder theorem is suggested whenever a large NTT modulus is necessary. A graph shows the error versus values of NORM varying from 1000 to 20.000, when compared to a direct DFT using real arithmetic. Hence one concludes \(NORM>4000\) to be sufficient for a negligible error \((<0.05\%)\). No results of timing tests are included.