A Modulo (2^n)+1 Multiplier with Faithful Representation of Residues

Modulo (2^n)+1 adders and/or multipliers are used in digital filters, cryptographic systems, and digital signal processors based on residue number systems (RNS). The module set {(2^n)–1, 2^n, (2^n)+1} is popular in RNS applications, where the design of modulo (2^n)+1 multipliers is more challenging than the case of other two module. One reason is that the natural representation of residues in the range [0, 2n] requires n+1 bit. However, a number of modulo (2^n)+1 addition or multiplication schemes have used n-bit diminished-1 representation of residues, where zero operands are supposed to be treated separately. On the other hand, double-LSB encoding of modulo (2^n)+1 residue (i.e., an n-bit code word with a second least significant bit) has been used in the design of an efficient modulo (2^n)+1 adder. We are therefore, motivated to study the impact of the double-LSB encoding of residues on the design of modulo (2^n)+1 multipliers. We describe the operation of such multipliers in dot-notation representation and show that the corresponding circuitry uses only standard off the shelf arithmetic cells such as full adders, half adders and carry look-ahead logic. Synthesis based comparison with previously reported multipliers shows the advantages of the proposed design.