Fast Complex Convolution Using Number Theoretic Transforms,
NAVAL RESEARCH LAB WASHINGTON D C
Pagination or Media Count:
It is shown that discrete circular convolution of complex number sequences may be carried out without arithmetic roundoff error using a family of number theoretic transforms defined in a finite ring. In certain cases the arithmetic of this transform may involve only additions, subtractions, and circular bit shifts and may be implemented with an FFT type procedure. As an application it is shown that the discrete Fourier transform may be computed with these transforms.
- Non-Radio Communications