A VLSI Implementation of Modulo 2n-1Multiplier by using Radix-8 Modified Booth Algorithm
M. Ashokchakravarthi1, K.V. Ramana Rao2
1M. Ashokchakravarthi, M.tech ECE Department, JNTU Kakinada University, Pydah College of Engineering and Technology, Visakhapatnam, India.
2K.V. Ramana Rao, Associate Professor & Head of the Department, ECE, Pydah College of Engineering and Technology, Visakhapatnam, India.
Manuscript received on October 01, 2012. | Revised Manuscript received on October 05, 2012. | Manuscript published on October 10, 2012. | PP: 74-80 | Volume-1 Issue-5 October 2012. | Retrieval Number: E0301091512 /2012©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
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 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 2n -1 arithmetic and hardwired as a partial product to be accumulated in the carry save adder tree. 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.
Keywords: Booth algorithm, design space exploration, modulo arithmetic, multiplier, residue number system (RNS).