High-performance implementation of convolution on multiple field-programmable gate array boards using number theoretic transforms defined over the Eisenstein residue number system
Uwe H. Meyer-Baese, Stefan Wolf, J.D. Mellott, Fred J. Taylor · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1997
Fast implementation of convolution and discrete Fourier transform computations are frequent problems in signal and image processing. These operations typically use fast Fourier transform (FFT) algorithms. Number Theoretic Transforms (NTTs) over a finite group of primes can also be used for this purpose. Using the NTT over Fermat primes (2q + 1) in field programmable gate array (FPGA) designs is advantageous, because the arithmetic can be efficiently and fast realized. By using Fermat primes, all multiplications, which have a O(q2) area requirement, can be replaced by a q yields q (rotation) shift operation, which has only a O(q(DOT)log(q)) area requirement. The area requirement reduces to O(q) for a fully pipelined realization with hardwired shifts. Using the Eisenstein Residue Number System (ERNS), which defines complex number over the polynom j2 + j + 1 equals 0, instead of j2 + 1 equals 0 for Gaussian integers, gives the additional advantage that the transform length is extended from q to 6q by only one addition for each complex multiplication. An RNS-based multiple FPGA-board implementation is presented which demonstrates both the performance and packaging advantages of the new ERNS-FPGA- NTT paradigm.