Efficient Implementations of Residue Generators Mod 2n + 1 Providing Diminished-1 Representation

The moduli of the form 2n+1 belong to a class of low-cost odd moduli, which have been frequently selected to form the basis of various residue number systems (RNS). The most efficient computations modulo (mod) 2n+1 are performed using the so-called diminished-1 (D1) representation. Therefore, it is desirable that the input converter from the positional number system to RNS (composed of a set of residue generators) generate the residues mod 2n+1 in D1 form. In this paper, we propose a new universal architecture of the residue generator mod 2n+1 with D1 output composed of two basic blocks. Its first block with p primary inputs can be easily designed for any p≥4n, whereas its final block—the 4-operand adder mod 2n+1—preserves the same structure for any p. If a pair of conjugate moduli 2n±1 belongs to the RNS moduli set, the latter architecture can be easily extended to build p-input bi-residue generators mod 2n±1, which not only save hardware by sharing p−4n full-adders, but also generate the residue mod 2n+1 directly in D1 form.