A Low-Complexity High-Radix RNS Multiplier

A graph-based technique is introduced for the design of a class of residue arithmetic multipliers, as well as a family of new high-radix digit adders. A proposed design technique derives simple high-radix modulo-r ⁿ multipliers by optimally selecting among the variety of introduced digit adders the ones that compose a minimal-area multiplier. The proposed technique minimizes multiplier complexity by selecting digit adders that observe the constraints imposed on the maximum values of the various intermediate digits. The proposed technique leads to significant area and time improvements over previously published architectures for practical modulus cases.