A modulo 2n+1 multiplier with double-LSB encoding of residues

Modulo 2ⁿ+1 adders and/or multipliers are used in digital filters, cryptographic systems, and digital signal processors based on residue number systems (RNS). The moduli set {2ⁿ-1, 2ⁿ, 2ⁿ+1} is popular in RNS applications, where the design of modulo 2ⁿ+1 multipliers is more challenging than the case of other two moduli. One reason is that the natural representation of residues in the range [0, 2ⁿ] requires n+1 bits. However, a number of modulo 2ⁿ+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ⁿ+1 residues (i.e., an n-bit code word with a second least significant bit) has been used in the design of an efficient modulo 2ⁿ+1 adder. We are therefore motivated to study the impact of the double-LSB encoding of residues on the design of modulo 2ⁿ+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.