Performance Evaluation and Comparison of Multipliers using Vedic Algorithms

Performance Evaluation and Comparison of Multipliers using Vedic Algorithms

V V S Vijaya Krishna

School of electronics, Vignan University, Vadlamudi, India

Abstract This paper Compares two multipliers which are based on Vedic Mathematics. Vedic Mathematics is the ancient method of mathematics which has techniques for calculations based on certain sutra or principles. In this paper multipliers are designed based on sutras called Urdhva-Tiryagbhyam (vertically and cross wise) and Nikhilam Sutra(all from 9 and last from 10). The multipliers uses Compressor in place of carry save adders, to decrease the delay by increasing the speed of addition of partial products. The Multipliers are designed for both 8 bit and 16 bit. The architecture design entry is done using Verilog HDL and simulated using Xilinx ISE. It is then synthesized and implemented on Xilinx Virtex 5 FPGA Kit. The Performance evaluation results in terms of speed and device utilization are compared among two sutras. Comparision declares that the multiplier based on Nikhilam Sutra is better than the other in terms of speed and area.

Keywords-: Vedic Mathematics; Urdhva-Tiryagbhyam; Nikhilam Sutra;Compressor; Verilog; Xilinx ISE; FPGA; VIRTEX 5

1. INTRODUCTION

   Multiplier is one of the key hardware blocks in designing arithmetic, signal and image processors. Many transform algorithms like Fast Fourier transforms, Discrete Fourier transforms etc make use of multipliers. Since multiplication dominates the execution time of most DSP algorithms, so there is a need of high speed multiplier. Currently, multiplication time is still the dominant factor in determining the instruction cycle time of a DSP chip. Reducing the time delay and power consumption are very essential requirements for many applications. The proposed multiplier is designed based on Vedic mathematics for attaining fast and low power multiplier.

   Vedic mathematics is the name given to the ancient Indian system of mathematics that was rediscovered in early twentieth century. Vedic Mathematics is mainly based on sixteen principles which are termed as Sutras. The Power of Vedic Mathematics is not only confined to simplicity, regularity, but also it is logical. VM steps can be applied to problems involving trigonometric functions, plane and sphere geometry, conics, differential calculus, integral calculus and applied mathematics of various kind. The importance of VM lies in the fact that it simplifies the complicated looking calculations in conventional mathematics to a simple one in a much faster and efficient manner. In this paper multipliers are designed based on sutras called Urdhva-Tiryagbhyam and Nikhilam sutra. A

   verilog code has developed based on the sutras and it is realized using a FPGA chip. Here the sutras are used to design multipliers separately. A compressor is used as an alternative for addition which reduces the delay. Different compressors can be used, but in the present design a 4:2 compressor is used. The results indicate that multiplier based on Urdhva-Tiryagbhyam is better than the multiplier based on Nikhilam Sutra, in terms of delay and area.

   FPGA based machines are less time consuming, flexible and programmable and reduces hardware as it is reprogrammable. Use of such machines saves time and cost. The conceptual model for the proposed multipliers are implemented using Virtex 5 XC5VLX50T FPGA board. The remaining part of the paper is arranged as, introduction to Vedic Mathematics in section 2 followed by description of Urdhva-Tiryagbhyam and Nikhilam Sutra in section 3.

   Section 4 describes the proposed architectures followed by results and conclusion in section 5 and 6.

2. VEDIC MATHEMATICS

   Vedic Mathematics is a part of sthapatya, which is an upa veda of Atharva veda. It covers explanation of several modern mathematical terms including factorization,quqdratic equations,trigonometry. His holiness jagadguru shankaracharya bahrati Krishna teerthaji maharaja comprised all this work together and gave its mathematical explanation while discussing it for various applications. Swmiji constructed 16 sutras (formulae) and 16 upasutras (subformulae) after extensive research in atharva veda. The word veda has the derivational meaning i.ethe fountain head and illimitable storehouse of all knowledge. The Sutras along with their brief meanings are enlisted below.

   1. Shunyamanyat- If one is in ratio, the other is zero.

   2. Chalana-Kalanabyham- Difference and Similarities.

   3. Ekadhikina Purvena- By one more than the previous one

   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- Product of the sum is equal to the sum of the product

   7. Nikhilam Navatashcaramam Dashatah- All from nine and last from ten

   8. Paraavartya Yojayet- Transpose and adjust

   9. Puranapuranabyham- By the completion or non completion

   10. Sankalana- vyakalanabhyam- By addition and by subtraction

   11. Shesanyankena charamena- The remainders by the last digit

   12. Shunyam Saamyasamuccaye- When the sum is the same that sum is zero

   13. Sopaantyadvayamantyam- The ultimate and twice the penultimate

   14. Urthva-Thiryagbhyam- Vertically and cross wise

   15. Vyashtisamanstih- part and Whole

   16. Yaavadunam- Whatever the extent of its deficiency.

3. URDHVA TIRYAGBHYAM

   It is the general formula applicable to all cases of multiplication and also in the division of a large number by another large number. It means vertically and crosswire. The same principle can be used for binary numbers.

   The method is illustrated using an example. The product of 1111 and 1111 Decimal numbers is calculated using Urdhva Tiryagbhyam.

   Methodology of Parallel calculation 1 1 1 1

   1 1 1 1

   1*1=1

   1 1 1 1

   1 1 1 1

   1*1+1*1=2

   1 1 1 1

   1 1 1 1

   1*1+1*1+1*1=3

   1 1 1 1

   1 1 1 1

   1*1+1*1+1*1+1*1=4

   1 1 1 1

   1 1 1 1

   1*1+1*1+1*1=3

   1 1 1 1

   1 1 1 1

   1*1+1*1=2

   1 1 1 1

   1 1 1 1

   1*1=1

4. NIKHILAM SUTRA

   The Nikhilam Sutra literally means all from 9 and last from 10.The same principle can be applied for binary numbers. It is more efficient when the numbers involved are large. This sutra is efficient for multiplication only when the magnitudes of both operands are more than half their maximum values.

   The method is illustrated using an example. The product of 8 and 7 with chosen base 10 which is nearest to greater than both these two numbers is as follows.

   Methodology for Nikhilam Sutra Nearest Base=10

   Column1 Column2

   8 (10-8)=2

   7 (10-7)=3

   5 6

   (common Difference) (multiplication of compliments) Result :56

   As shown in fig the multiplier and multiplicand are written in two rows followed by the differences of each of them from chosen base that is their compliments. There are two columns of numbers, one consisting of the numbers to be multiplied (column10 and the other consisting of their compliments (column 20.The product also consists of two parts which are demarked by a vertical line for the purpose of illustration. The right hand side of the product can be obtained by multiplying the numbers of the column 2. The surplus will be carried over to the left. The left hand side of the product can be found by cross subtracting the second number of column 2 from the first number of column 1or vice ersa. The final result is obtained by concatenating both the parts. The same method can be applied to Binary numbers.

5. PROPOSED ARCHITECTURES

   The Methodology of Urdhva Tiryagbhyam can be implemented using the following proposed structure.

   B[n] A[n] B[0] A[0]

   .

   Product Terms

   Product Terms

   4:2 Compressor

   4:2 Compressor

   Final Adder Stage

   Final Adder Stage

   Answer=1234321

   The Same Metho

   plied to Binary

   Product

   numbers.

   dology can be ap

   Figure 1. Block Diagram for Proposed Multiplier using Urdhva

   tiryagbhyam

   The Methodology indicates that there are two operations. One is generating product terms and other is adding the terms. So this can be realized by using a series of AND gates and a compressor which reduces the n no of words to two words. Then the two words are added using an ordinary adder.

   Figure 2. 4:2 Compressor

   In this 4:2compressor the outputs generated at each stage are efficiently used by replacing the XOR blocks with multiplexer blocks. The select bits to the multiplexers are available much ahead of the inputs so that the critical delay path is minimized.

   The 2 bit Vedic multiplier is implemented using and gates and half adders.

   Half Adder

   Half Adder

   Half Adder

   Half Adder

   a1b1 a0b1 a1b0 a0b0 c1

   c2 s2 s1 s0

   Figure 3. 2×2 Multiplier

   AND gates are used to generate the product terms and adders are used to add the product terms. The same can be implemented to higher order bits. But if the bits are increased then no of product terms increases and more no of adders are required to add those terms. So instead of using adders it is proposed to use compressors. The reason for decrease in delay is because of its structure. It has 4 inputs and one carry bit which will be added to two bits. Such compressors are used in N bit multiplier which will reduce N product terms to two product terms. Finally the two product terms are added using an ordinary adder.

   The Method of Nikhilam Sutra can be implemented by following structure

   Multiplicand Multiplier

   2s compliment

   2s compliment

   2s compliment

   2s compliment

   Multiplier

   Multiplier

   4:2 Compressor

   4:2 Compressor

   Adder

   Adder

   LHS of Product RHS of Product

   Figure 4. Block Diagram for Proposed Multiplier using

   Nikhilam Sutra

6. RESULTS

   1. Simulation

      The proposed structure is first coded using verilog language and is simulated for functional verification. The verilog codes are simulated using Xilinx ISE. The codes are written for 8 and 16 bit multiplier.

      Figure 5. Simulation Waveform for proposed multiplier using

      Two techniques for 8 Bit

      Slice Logic Utilization	Used	Available	Utilization
      Number of 4 input LUTs	20	28,800	0%
      Number of Slice LUTs	20	28,800	0%
      Number of fully used LUT- FF pairs	24	753	3%
      Number of bonded IOBs	18	480	3%

      Slice Logic Utilization	Used	Available	Utilization
      Number of 4 input LUTs	20	28,800	0%
      Number of Slice LUTs	20	28,800	0%
      Number of fully used LUT- FF pairs	24	753	3%
      Number of bonded IOBs	18	480	3%

      Figure 6. Simulation Waveform for proposed multilier using

      both techniques for 16 bit

      Table 3 Summary Report of Multiplier based on Nikhilam Sutra (8 bit)

   2. Implementation

   After verifying the functionality of the circuit, it is synthesized and implemented on Virtex 5 XC5VLX50T FPGA Board. Both the circuits are synthesized and implemented on FPGA Board.

   Tables 1 to 4 shows the summary report of multipliers and table 5 gives the comparison results.

   Table 1 Summary Report of Multiplier based on Urdhva Tiryagbhyam

   (8 bit)

   Slice Logic Utilization	Used	Available	Utilization
   Number of 4 input LUTs	26	28,800	0%
   Number of Slice LUTs	26	28,800	0%
   Number of fully used LUT- FF pairs	28	753	4%
   Number of bonded IOBs	20	480	4%

   Table 2 Summary Report of Multiplier based on Urdhva Tiryagbhyam

   (16bit)

   Slice Logic Utilization	Used	Available	Utilization
   Number of 4 input LUTs	40	28,800	0%
   Number of Slice LUTs	40	28,800	0%
   Number of fully used LUT- FF pairs	80	753	10%
   Number of bonded IOBs	64	480	13%

   Table 4 Summary Report of Multiplier based on Nikhilam Sutra (16bit)

   Slice Logic Utilization	Used	Available	Utilization
   Number of 4 input LUTs	32	28,800	0%
   Number of Slice LUTs	32	28,800	0%
   Number of fully used LUT- FF pairs	65	753	8%
   Number of bonded IOBs	45	480	9%

   Table 5 Comparison of Multipliers

   (5 XC5VLX50T)		Delay(ns)	No of Slice LUT
   8 bit	Urdhva Tiryagbhyam	9.6	26
   	Nikhilam Sutra	6.7	20
   16 bit	Urdhva Tiryagbhyam	15.48	40
   	Nikhilam Sutra	11.24	32

   Comparison table indicates that the multiplier based on Urdhva Tiryagbhyam is better than Nikhilam Sutra in terms of delay and logic Utilization.

7. CONCLUSION

In this paper multipliers are designed based on sutras called Urdhva-Tiryagbhyam (vertically and cross wise) and Nikhilam Sutra(all from 9 and last from 10). The multipliers uses Compressor in place of carry save adders, to decrease the delay by increasing the speed of addition of partial products. The Multipliers are designed for both 8 bit and 16 bit. Both designs are implemented on Virtex 5XC5VLX50T FPGA board. Comparison concludes that the multiplier based on Nikhilam Sutra is better than the other in terms of speed and logic utilization. Future work includes the optimized design is to be used in designing a FIR filter and is to be implemented on a FPGA

REFERENCES

1. Jagadguru Swami, Sri Bharati Krisna, Tirthaji Maharaja, Vedic Mathematics or Sixteen Simple Mathematical Formulae from the Veda, Delhi(1965), Motilal banarasidas, Varanasi, India.

2. Ramalatha, M Dayala, K D Dharani, PPriya and Deoborah, High speed Energy Efficient ALU Design using Vedic Multiplication techniques, International conference on Advances in computational tools for Engineering Applications, pp640-642,2009.

3. Harpreet Singh Dhillon and Abijit Mishra, A Reduced bit multiplication Algorithm for Digital Arithmetics, International Journal of Computational and Mathematical Scinces.

4. A P Nicholas, K R Williams, J Picles, Application of Uedhva Sutra,Spiritual Study Group, Roorkee,1984.

5. Booth, A D, A Signed Binary multiplication technique, Quarterly Journal of mechanics and Applied Mathematics, vol.4, pt2.236- 240,1951.

6. S Kumaravel, RRamalatha, Marimuthu, VLSI impmementation of High performance RSA Algorithm using Vedic Mathematics, ICCIMA, vol 4, pp126-128(2007).

7. Neil H E Weste, David Harris, Ayan anerjee, CMOS VLSI Design, A Circuits and Systems perspective, Third Edition, Published by Pearson Education, pp-327-328.

8. C S wallace,A suggestion for a fast multiplier, Electronic computers,

   IEEE Transactions, vol13,pages 14-17,Feb 1964

9. T.G Noll,Carry save architectures for high speed digital signal processing, Journal of VLSI Signal Processing, 1991, Pp 121-140.

10. O.J Bedri, Carry Select Adder,IRE Trans.Electron.Comput..Pp340- 344,1962

11. Steve Kilts, Advanced FPGA Design : Architecture,Implementation, and optimization, Wiley-IEEE press, 2007.

12. www.Xilinx.com