Modified Architecture of Vedic Multiplier for High Speed Applications

Modified Architecture of Vedic Multiplier for High Speed Applications

D.Kishore Kumar A.Rajakumari, Associate Professor

M.Tech Dept of ECE M.Tech(Ph.D),Dept of ECE

B.V.Raju Institute of Technology B.V.Raju Institute of Technology

Andhra Pradesh Andhra Pradesh

Abstract :

This paper proposes the implementation of Multiplier algorithm using the algorithms of Ancient Indian Vedic Mathematics (Nikhilam) that have been modified to improve performance for high speed applications. It shows the Modified architecture for a 16×16 Vedic multiplier module using Nikhilam Sutra" technique. The design implementation is described in both at gate level and high level RTL code (Structural level) using Verilog Hardware Description Language. The design code is Simulated and Synthesized using Xilinx ISE

1. Simulator, using Xilinx Family: Vertex5, Device: XC5VLX30,Speed Grade: -3. The performance evaluation results in terms of speed and device utilization are compared with earlier multiplier architecture. The proposed design has speed improvements as compared to multiplier architecture presented.

   Key Words Multiplier, Vedic Formals, airthematic.

   1. INTRODUCTION:

      Multipliers are the core components of all the digital signal processors (DSPs) and the speed of the DSP is largely determined by the speed of its multipliers. Higher throughput arithmetic operations are important to achieve the desired performance in many real time signal and image processing applications. One of the important arithmetic operations in such applications is to perform a large no of mathematical calculations in a very less time. Since in performing mathematical calculations especially multiplication a compute spends a considerable amount of its processing time, an improvement in the speed of a math coprocessor for performing multiplication will increase the overall speed of the computer.

      This paper proposes a new modified Vedic multiplier based on Vedic algorithm (Nikhilam Sutra) for high speed applications, and this Modified Multiplier is

      faster than proposed Vedic multiplier ,array multiplier and Booth multiplier, and Wallace tree multiplier

      1. Vedic Sutras:

         The word Vedic is derived from the word

         Veda which means the store-house of all knowledge. Vedic mathematics is mainly based on 16 Sutras (or aphorisms) dealing with various branches of mathematics like arithmetic, algebra, geometry etc.These Sutras along with their brief meanings are enlisted below alphabetically.

         1. (Anurupye) Shunyamanyat If one is in ratio, the other is zero

         2. Chalana-Kalanabyham Differences and Similarities.

         3. Ekadhikina Purvena By one more than the previousone

         4. Ekanyunena Purvena By one less than the previous one

         5. Gunakasamuchyah The factors of the sum is equal to the sum of the factors

         6. Gunitasamuchyah The product of the sum is equal to the sum of the product

         7. Nikhilam Navatashcaramam Dashatah All from 9 and the last from 10

         8. Paraavartya Yojayet Transpose and adjust.

         9. Puranapuranabyham By the completion or noncompletion

         10. Sankalana-vyavakalanabhyam By addition and by subtraction

         11. Shesanyankena Charamena The remainders by the last digit

         12. Shunyam Saamyasamuccaye When the sum is thesame that sum is zero

         13. Sopaantyadvayamantyam The ultimate and twice

         14. Urdhva-tiryakbyham Vertically and crosswise

         15. Vyashtisamanstih Part and Whole

         16. Yaavadunam Whatever the extent of its deficiency.

      2. Nikhilam Sutra:

         Nikhilam Sutra literally means all from 9 and last from 10. Although it is applicable to all cases of multiplication, it is more efficient when the numbers involved are large. It finds out the compliment of the large number from its nearest base to perform the multiplication operation on it, hence larger the original number, lesser the complexity of the multiplication.

         Fig 1 : Multiplication of 89 x 92

         As shown in Fig.1, we write the multiplier and the multiplicand in two rows followed by the differences of each of them from the chosen base, i.e., their compliments. We can now write two columns of numbers, one consisting of the numbers to be multiplied (Column 1) and the other consisting of their compliments (Column 2). The product also consists of two parts which are demarcated by a vertical line for the purpose of illustration. The right hand side (RHS) of the product can be obtained by simply multiplying the numbers of the Column 2 (11 x 8 = 88). The left hand side (LHS) of the product can be found by cross subtracting the second number of Column 2 from the first number of Column 1 or vice versa, i.e., 89 8 =81 or 92 11 =81. The final result is obtained by concatenating RHS and LHS (Answer = 8188).

   2. Proposed Vedic Multiplier Architecture:

      Broadly this architecture is divided into three

      parts.

      1. Radix Selection Unit

      2. Exponent Determinant

      3. Multiplier.

      Hardware implementation of this mathematics is shown in Fig The architecture can be decomposed into three main subsections: (i) Radix Selection Unit (RSU) (ii) Exponent Determinant (ED) and (iii) Multiplier. The RSU is required to select the proper radices corresponding to the input numbers.

      Fig 2 : Proposed Architecture of Vedic Multiplier Using

      Nikhilam Sutra

      1. Radix Selection Unit :

         The Block level architecture of RSU is shown in Fig..RSU consists of three main subsections: (i) Exponent Determinant (ED), (ii) Mean Determinant (MD) and (iii) Comparator. 'n' number bit from input N1 is fed to the ED block. The maximum power of N1 is extracted at the output which is again fed to shifter and the adder block. The second input to the shifter is the (n+ 1) bit representation of decimal '1 '.If the maximum power of N1 from the ED unit is (n-1) then the output of the shifter is 2n-

         1. The adder unit is needed to increment the value of the maximum power of N1 by '1'. The second shifter is needed

         to generate the value of 2n.Here n is the incremented value

         taken from the adder block. The Mean Determinant unit is required to compute the mean of (2n-l + 2n). The Comparator compares the actual input with the mean value of (2n-l + 2n). If the input is greater than the mean then 2n is selected as the required radix. If the input is less than the mean then 2n-1 is selected as the radix.

         Fig 3 : Proposed Architecture of Radix Selection Unit

      2. Exponent Determinant :

         The hardware implementation of the exponent determinant is shown in Fig. For the nonzero input, shifting operation is executed using parallel in parallel out (PIPO) shift registers. as per the binary representation of the number (N-1)10. 'Shift' pin is assigned in PIPO shifter to check whether the number is to be shifted or not (to initialize the operation 'Shift' pin is initialized to low). A decrementer has been integrated in this architecture to follow the maximum power of the radix. A sequential searching procedure has been implemented here to search the first '1' starting from the MSB side by using shifting technique. For an N bit number, the value (N-1)10is fed to the input of decrementer. The decrementer is decremented based on a control signal which is generated by the searched result. If the searched bit is '0' then the control signal becomes low then decremeter start decrementing the input value (Here the decrementer is operating in active low logic). The searched bit is used as a controller of the decrementer. When the searched bit is '1' then the control signal becomes high and the decrementer stops further decrementing and shifter also stops shifting operation. The output of the decrementer shows the integer part (exponent) of the number.

         Fig 4.Exponent Determinant

   3. Modified Vedic Multiplier Architecture

      Architecture of Modified Vedic Multiplier is as shown in fig 5. The modified architecture will consists of extra a comparator, so that first we will check the big number of the applied two numbers, then first no will be applied to first RSU block. And one more modification is here we will use only ADDER in the Place of ADDER SUBSTRACTOR, so that delay of this architecture can be reduced. RSU block is also modified to get good performance over conventional methods.

      Fig 5: Modified Architecture of Vedic Multiplier Using Nikhilam Sutra

      1. Modified Radix Selection Unit:

The modified Radix selection unit will consists of two blocks (i) Exponent Determinant (ED), (ii) Shifter.

Exponent determinant block will be same as in proposed Vedic multiplier. When a input no is applied to RSU block, first it will calculate the value of exponent determinant, the output will be given to the shifter, and other input to the shifter is (n+1) bit representation of 1, and shifter output will give you the value of Radix of a given number .For example if the output of the exponent determinant block is n, then the output of the shifter is 2n. which will give the output of RSU Block.

Fig 6: Modified Radix selection Unit

4 . Results And Discussion.

The proposed square architecture achieves significant improvement in performance over the conventional multipliers and proposed Vedic multiplier Table-1 displays the comparison of synthesis results of the Modified 16×16 Vedic multiplier using Nikhilam Sutra with The proposed 16×16 Vedic multiplier using Nikhilam Sutra. Its been observed that the results of modified Vedic multiplier using Nikhilam sutra is having a delay of ns with compared to the proposed vedic multiplier that of ns. And also the delay of the modified Vedic multiplier is less when compared to conventional multipliers.

TABLE 1. Comparison of Simulation and Synthesis Results:

Fig 7. Simulation results of Modified Vedic Multiplier

Table 1 shows the comparison results of the Modified Vedic multiplier over the proposed Vedic and other conventional multipliers. From the table we proved there is a huge percentage of increment in the delay with

16.245 for Modified Vedic multiplier, where as for

proposed is 21.387, and for Booth Multiplier it is noted as 26.231.

TABLE 2. HDL Synthesis Report

pp. 757-765

1. H. D. Tiwari, G. Gankhuyag, C. M. Kim, and Y. B. Cho, "Multiplier design based on ancient Indian Vedic Mathematics," in Proceedings

   IEEE International SoC Design Cotiference, Busan, Nov. 24-25, 2008, pp. 65-68.

2. C. S. Wallace, "A suggestion for a fast multiplier," lEE Trans. Electronic Comput., vol. EC-\3, pp. 14-17, Dec. 1964.

3. P. Mehta, and D. Gawali, "Conventional versus Vedic mathematical method for Hardware implementation of a multiplier," in Proceedings

   IEEE International Cotiference on Advances in Computing, Control, and Telecommunication Technologies, Trivandrum, Kerala, Dec. 28-29, 2009, pp. 640-642.

4. A New Low Power 32×32- bit Multiplier Pouya Asadi and Keivan Navi, World Applied

   Sciences Journal 2(4):341:347, 2007, IDOSI Publication.

5. Low Power High Performance Multiplier C.N. Marimuthu and P.Thiangaraj, ICGST-PDCS,

   Volume 8, December 2008.

6. Lifting Scheme Discrete Wavelet Transform Using Vertical and Crosswise Multipliers

   Anthony OBrien and Richard Conway, ISSC, 2008,Galway, June 18-19.

7. Morris Mano, Computer System Architecture,PP. 346-347, 3rd edition,PHI. 1993.

8. Tam Anh Chu, Booth Multiplier with Low Power High Performance Input Circuitary, US

   Patent, 6.393.454 B1,May 21, 2002.

9. Purushottam D. Chidgupkar and Mangesh T. Karad, The Implementation of Vedic Algorithms in Digital Signal Processing, Global J. of Engng. Educ., Vol.8, No.2 © 2004 UICEE .

1. Conclusion:

   The modified Vedic multiplier architecture shows speed improvements over proposed and other conventional multiplier architecture. The 16×16 modified Vedic multiplier using Nikhilam Sutra found to be better than 16×16 proposed Vedic multiplier using Nikhilam Sutra Sutra in terms of speed. This approach may be well suited for multiplication of numbers with more than 16 bit size for high speed applications. The power of Vedic Mathematics can be explored to implement high performance multiplier in VLSI applications. Nikhilam Sutra in Vedic Mathematics is very a good technique for high speed applications, its implementation with different logics in VLSI. Further the work can be extended for optimization of said multiplier to improve the power.

2. References:

1. Jagadguru Swami Sri Bharath, Krsna Tirathji, Vedic Mathematics Or Sixteen Simple Sutras From The Vedas, Motilal Banarsidas , Varanasi (India),1986.

2. Walter C.D.; Exponentiation Using Division Chains; IEEE Transactions on Computers, IEEE Inc.; New York, U.S.; vol. 47, No. 7; Jul. 1, 1998,