A low-complexity RNS multiplier

Novel VLSI architectures and a design methodology for adder-based residue number system (RNS) multipliers are presented. In the proposed approach, the exploitation of the non-occurring combinations of input bits reduces the number of 1-bit full adders (FAs) required to compose a multiplier. In particular couples and triplets of input bits assigned to particular FAs are identified, which contain bits that cannot be simultaneously asserted for any valid input combination. It is shown that the particular couples or triplets can be assigned to OR gates instead of 1-bit adders, therefore reducing multiplier complexity. By comparing the performance and hardware complexity of the proposed multiplier to previously reported designs, it is found that the introduced architecture is more efficient in the area×time product sense. In fact, it is shown that more than 80% performance improvement can be achieved in certain cases