On the design of modulo 2n±1 residue generators

In this paper, we propose an efficient residue generator which concurrently computes the residues modulo 2ⁿ+1 and modulo 2ⁿ-1. The input operands are divided into n-bit vectors which are then grouped into two sets and added by two separate Carry Save Adder (CSA) trees. The output carry of each stage of the first CSA tree is used as input to the corresponding stage of the second CSA tree, while the output vectors of the trees are finally added modulo 2ⁿ+1 and 2ⁿ-1 to compute the residues. The proposed residue generator is well suited for Residue Number System (RNS) based applications which use both modulo 2ⁿ+1 and 2ⁿ-1 residues. An efficient configurable modulo 2ⁿ±1 residue generator is also proposed.