Share Email Print

Proceedings Paper

High-performance implementation of convolution on multiple field-programmable gate array boards using number theoretic transforms defined over the Eisenstein residue number system
Author(s): Uwe Meyer-Baese; Stefan Wolf; Jonathon Mellott; Fred J. Taylor
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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 (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.

Paper Details

Date Published: 28 July 1997
PDF: 12 pages
Proc. SPIE 3068, Signal Processing, Sensor Fusion, and Target Recognition VI, (28 July 1997); doi: 10.1117/12.280825
Show Author Affiliations
Uwe Meyer-Baese, Technische Univ. Darmstadt (FRG) and Univ. of Florida (United States)
Stefan Wolf, Technische Univ. Darmstadt (Germany)
Jonathon Mellott, Univ. of Florida (United States)
Fred J. Taylor, Univ. of Florida (United States)

Published in SPIE Proceedings Vol. 3068:
Signal Processing, Sensor Fusion, and Target Recognition VI
Ivan Kadar, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?