Number Theoretic Transform Modular Residue Processors
G. Eichmann, Jaroslav Keybl, Richard J. Mammone · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1980
Finite digital convolution (FDC) appears in the implementation of finite impulse response digital filtering, in auto-aid cross-correlation, polynominal multiplication and the multiplication of very large numbers. While there are several methods to implement FDC, when the lengths of the sequences to be convolved is a highly composite number, the discrete fast Fourier transform (FFT) approach is used. This approach requires generating, storing and truncating a large number of complex exponentials. Recent interest has centered on finding real basis numbers that preserve the properties of the FFT. By working in a finite field of integers with arithmetic modulo an integer M, a large class of new transforms, called number theoretic transforms, can be generated. These transforms are useful in applications where integer arithmetic is already being considered, such as spread-spectrum encoding, digital error-correction and data encryption, or where the data is digitally encoded in a finite number of bits. In this paper, residue arithmetic based number theoretic transforms will be considered.