Abstract—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 2n-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 2n-1 multipliers, with delay adaptable to the RNS multiplier delay, is proposed. The modulo 2n-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 2n-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 2n-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 divisib le by three, respectively. Our synthesis results show that the proposed radix-8 Booth encoded modulo 2n-1 multiplier saves substantial area and power consumption over the radix-4 Booth encoded multiplier in medium to large word-length RNS multiplication.

Index Terms—Residue Number System (RNS), Booth algorithm, Multiplier, Radix-8

Cite: N Niranjan and P Sreenivasa Rao, "DESIGN OF BOOTH ENCODED MODULO 2n-1 MULTIPLIER USING RADIX-8 WITH HIGH DYNAMIC RANGE RESIDUE NUMBER SYSTEM," International Journal of Electrical and Electronic Engineering & Telecommunications, Vol. 3, No. 1, pp. 92-103, January 2014.