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

Uwe Meyer-Baese; Stefan Wolf; Jonathon Mellott; Fred J. Taylor

doi:10.1117/12.280825

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

Uwe Meyer-Baese, Stefan Wolf, Jonathon Mellott, Fred J. Taylor

Author Affiliations +

Proceedings Volume 3068, Signal Processing, Sensor Fusion, and Target Recognition VI; (1997) https://doi.org/10.1117/12.280825
Event: AeroSense '97, 1997, Orlando, FL, United States

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 + 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²) 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 j² + j + 1 equals 0, instead of j² + 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.

Citation Download Citation

Uwe Meyer-Baese, Stefan Wolf, Jonathon Mellott, and Fred J. Taylor "High-performance implementation of convolution on multiple field-programmable gate array boards using number theoretic transforms defined over the Eisenstein residue number system", Proc. SPIE 3068, Signal Processing, Sensor Fusion, and Target Recognition VI, (28 July 1997); https://doi.org/10.1117/12.280825

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Transform theory

Field programmable gate arrays

Convolution

Digital signal processing

Fourier transforms

Radon

Signal processing

Show All Keywords

Keywords/Phrases

Search In:

Publication Years