Implementation of Hybrid Vedic Multiplier Nikhilam Sutra and Karatsuba Algorithm for N-bit Multiplier Using Successive Approximation of N-1 Bit Multiplier

摘要

Vedic mathematics is the technique to solve complex arithmetic computations. Using this technique,complex problems can be solved easily. Normally, Urdhva Tiryakbhyam Sutra is generally known as VedicMultiplier. Nikhilam Sutra is a special case in Vedic Mathematics. But there is no proper implementationhardware for Nikhilam Sutra for binary multiplication. The aim of this study is to design hardware for NikhilamSutra using Karatsuba algorithm using successive approximation of N-1 bit multiplier. Multipliers are the basiccomponents used in many digital systems, digital signal processing operations and multimedia applications.Digital multipliers are the major source of power dissipation. Multiplications are often implemented withshift-and-add operations. In this study, we propose a method that combines the principles of Nikhilam sutraand Karatsuba sutra for the multiplication of binary numbers. The calculation of remainder is based on Nikhilamsutra using complement method and the weight reduction is carried out in the remainder by removing the MSB.The numerical transformation of the numbers is done by Karatsuba algorithm. For the remainder multiplication,only N-1 bit multiplier is required. Therefore, the algorithm requires only (N-1) x (N-1) bit multiplier for thecalculation remainder. By combining both algorithms, the number of multiplier is reduced and also the numberof bit for multiplier is also reduced. By applying this modification in the algorithm, strength of the multiplier isreduced. The research is implemented in Xilinx vertex device. The power, area and delay are measured usingCadence tool with 180 and 90nm technology. From the results?, the product of delay and area is reduced.