High-performance implementation of convolution on multiple field-programmable gate array boards using number theoretic transforms defined over the Eisenstein residue number system

摘要

Abstract: 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 (2$+q$/ $PLU 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(q$+2$/) area requirement, can be replaced by a q $YLD 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 j$+2$/ $PLU j $PLU 1 $EQ 0, instead of j$+2$/ $PLU 1 $EQ 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.!20