Radix-8 Booth Encoded Modulo 2 ^ -1 Multipliers With Adaptive Delay for High Dynamic Range Residue Number System

• Published in: IEEE transactions on circuits and systems. I, Regular papers Regular papers, 2011-05, Vol.58 (5), p.982-993
• Main Authors: Muralidharan, R, Chip-Hong Chang
• Format: Article
• Language: English
• Subjects: Adders; Booth algorithm; Complexity theory; Cryptography; Delay; design space exploration; Encoding; modulo arithmetic; multiplier; residue number system (RNS); Voltage control
• ISSN: 1549-8328; 1558-0806
• DOI: 10.1109/TCSI.2010.2092133

A special moduli set Residue Number System (RNS) of high dynamic range (DR) can speed up the execution of very-large word-length repetitive multiplications found in applications like public key cryptography. The modulo 2 n -1 multiplier is usually the noncritical datapath among all modulo multipliers in such high-DR RNS multiplier. This timing slack can be exploited to reduce the system area and power consumption without compromising the system performance. With this precept, a family of radix-8 Booth encoded modulo 2 n -1 multipliers, with delay adaptable to the RNS multiplier delay, is proposed. The modulo 2 n -1 multiplier delay is made scalable by controlling the word-length of the ripple carry adder, k employed for radix-8 hard multiple generation. Formal criteria for the selection of the adder word-length are established by analyzing the effect of varying k on the timing of multiplier components. It is proven that for a given n , there exist a number of feasible values of k such that the total bias incurred from the partially-redundant partial products can be counteracted by only a single constant binary string. This compensation constant for different valid combinations of n and k can be precomputed at design time using number theoretic properties of modulo 2 n -1 arithmetic and hardwired as a partial product to be accumulated in the carry save adder tree. The adaptive delay of the proposed family of multipliers is corroborated by CMOS implementations. In an RNS multiplier, when the critical modulo multiplier delay is significantly greater than the noncritical modulo 2 n -1 multiplier delay, k = n and k = n /3 are recommended for n not divisible by three and divisible by three, respectively. Conversely, when this difference diminishes, k is better selected as n /4 and n /6 for n not divisible by three and divisible by three, respectively. Our synthesis results show that the proposed radix-8 Booth encoded modulo 2 n -1 multiplier saves substantial area and power consumption over the radix-4 Booth encoded multiplier in medium to large word-length RNS multiplication.