Fast Fourier transformation based on number theoretic transforms (Q1123580): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0016-0032(88)90031-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2063102759 / rank | |||
Normal rank |
Revision as of 22:48, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast Fourier transformation based on number theoretic transforms |
scientific article |
Statements
Fast Fourier transformation based on number theoretic transforms (English)
0 references
1988
0 references
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.
0 references
fast algorithm
0 references
fast Fourier transform
0 references
number theoretic transform
0 references
discrete Fourier transform
0 references
cyclic convolution
0 references
scaling
0 references
cyclic integer convolutions
0 references
Chinese remainder theorem
0 references