A One-Step Modulo 2^n+1 Adder Based on Double-lsb Representation of Residues

A One-Step Modulo 2^n+1 Adder Based on Double-lsb Representation of Residues

Abstract

Efficient modulo 2^n±1 adders are desirable for computer arithmetic units based on residue number systems (RNS) with the popular moduli set {2^n–1, 2^n, 2^n+1}. Regular n-bit ripple-carry adders or their fast equivalents are suitable for modulo 2^n addition. But for the other two moduli a correcting increment/decrement step besides the primary n-bit addition is normally required. Several design efforts have tried to reduce the latency of the correcting step to a small delay not depending on the word length n, leading to one-step modular addition schemes. These include the use of alternative encoding of residues (e.g., diminished-1 representation of modulo 2^n+1 numbers), customized (vs. generic) adders (e.g., specialized parallel prefix adders), or compound adders. In this paper we investigate alternative modulo 2n+1 addition schemes, focus on generic one-step adder designs, and use the double-lsb representation of modulo 2^n+1 numbers. In a generic modular adder, the central abstract n-bit adder may be replaced by any concrete adder architecture meeting the designer’s prescribed measures in time, area and power consumption.

References