A Family of Modulo (2[power]n + 1) Multipliers

Jean-Luc Beuchat 1
1 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we first describe a novel modulo $(2^n+1)$ addition algorithm suited to FPGA and ASIC implementations, and discuss several architectures of multioperand modulo $(2^n+1)$ adders. Then, we propose three implementations of a modulo $(2^n+1)$ multiplication algorithm based on a paper by A. Wrzyszcz and D. Milford. The first operator is based on an $n\times n$ multiplication and a subsequent modulo $(2^n+1)$ correction, and takes advantage of the arithmetic logic embedded in Spartan or Virtex FPGAs. The second operator computes a sum of modulo-reduced partial products by means of a multioperand modulo $(2^n+1)$ adder. Then, radix-$4$ modified Booth recoding reduces the number of partial products, while making their generation more complex. Finally, we provide a comparison of this family of algorithms with existing solutions.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00070684
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 9:12:19 PM
Last modification on : Monday, April 29, 2019 - 11:11:19 AM

Identifiers

  • HAL Id : inria-00070684, version 1

Collections

Citation

Jean-Luc Beuchat. A Family of Modulo (2[power]n + 1) Multipliers. [Research Report] RR-5316, LIP RR-2004-39, INRIA, LIP. 2004, pp.16. ⟨inria-00070684⟩

Share

Metrics

Record views

209

Files downloads

387