Design and Implementation of 128 x 128 Bit multiplier by Ancient Mathematics

Design and Implementation of 128 x 128 Bit multiplier by Ancient Mathematics

Nagaraju Golla ECE Department GRIET

Hyderabad, India

G. V. Subba Reddy

ECE Department GRIET

Hyderabad, India

Abstract This paper proposed the design and implementation of 128×128 bit Multiplier using the techniques of Ancient Indian Vedic Mathematics that have been modified to improve performance. Vedic Mathematics is the ancient system of mathematics which has a unique technique of calculations based on 16 Sutras. The work has proved the efficiency of Urdhva Triyagbhyam Vedic method for multiplication which strikes a difference in the actual process of multiplication itself.Urdhva tiryakbhyam Sutra is most efficient Sutra, giving minimum delay for multiplication of all types of numbers, either small or large.

Keywords vedic mathematics, urdhva triyakbhyam sutra,

1. . INTRODUCTION

   Multiplication is an important fundamental function in arithmetic operations. Multiplication-based operations such as Multiply and Accumulate(MAC) and inner product are among some of the frequently used Computation- Intensive Arithmetic Functions(CIAF) currently implemented in many Digital Signal Processing (DSP) applications such as convolution, Fast Fourier Transform(FFT), filtering and in microprocessors in its arithmetic and logic unit.

   Vedic mathematics – a gift given to this world by the ancient sages of India. A system which is far simpler and more enjoyable than modern mathematics. The simplicity of Vedic Mathematics means that calculations can be carried out mentally though the methods can also be written down. There are many advantages in using a flexible, mental system. Pupils can invent their own methods, they are not limited to one method. This leads to more creative, interested and intelligent pupils. Vedic Mathematics refers to the technique of Calculations based on a set of 16 Sutras, or aphorisms, as algorithms and their upa-sutras or corollaries derived from these Sutras. Any mathematical problems (algebra, arithmetic, geometry or trigonometry) can be solved mentally with these sutras. Vedic Mathematics is more coherent than modern mathematics. Vedic Mathematics offers a fresh and highly efficient approach to mathematics covering a wide range – starts with elementary multiplication and concludes with a relatively advanced topic, the solution of non-linear partial differential equations. But the Vedic scheme is not simply a collection of rapid methods; it is a system, a unified approach. Vedic Mathematics extensively exploits the properties of numbers in every practical application

2. . 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 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 The product of the sum is equal to the sum of the product.

7. Nikhilam Navatashcaramam Dashatah All from 9 and 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 the same that sum is zero.

13. Sopaantyadvayamantyam The ultimate and twice the penultimate.

14. Urdhva-tiryagbhyam Vertically and crosswise.

15. Vyashtisamanstih Part and Whole.

16. Yaavadunam Whatever the extent of its deficiency.

    In this, Urdhva tiryakbhyam Sutra is first applied to the binary number system and is used to develop digital multiplier architecture. This is shown to be very similar to the popular array multiplier architecture. This Sutra also shows the effectiveness of to reduce the NXN multiplier structure into an efficient 4X4 multiplier structures. The proposed multiplication algorithm is then illustrated to show its computational efficiency by taking an example of reducing a 4X4-bit multiplication to a single 2X2-bit multiplication operation. This work presents a systematic design

    methodology for fast and area efficient digit multiplier based on Vedic mathematics .The Multiplier Architecture is based on the Vertical and Crosswise algorithm of ancient Indian Vedic Mathematics.

    1. URDHVA TRIYAGBHYAM ALGORITHM

1. Urdhva triyagbhyam

   Urdhva tiryagbhyam Sutra is a general multiplication formula applicable to all cases of multiplication. It literally means Vertically and Crosswise. To illustrate this multiplication scheme, let us consider the multiplication of two decimal numbers (3451 × 6723).

2. Steps involved for multiplication using vedic mathematics Step 1:

   Step 5:

   3*2+4*7+5*6=6+28+30+6(previous carry)=70

   New carry=7

   Step 6:

   3*7+4*6=21+24+7 (previous carry)=52

   New carry=5

   Step 2:

   5*3+1*2=15 +2+0(previous carry)=17 New carry=1

   Step 3:

   4*3+5*2+1*7=12+10+7+1(previous carry)=30

   New carry=3

   Step 7:

   3*6=18+5(previous carry)=23

   Fig . 1 mltiplication steps

   In the above example, the first step is to multiply, the LSB of multiplicand with LSB of multiplier. If the carry is generated than add carry with next result of cross multipliers. If carry is not generated than write the answer of product as a result. The product is carried out crosswise & vertically as it is shown in figure. The line diagram for four bit multiplication is given as follows and it shows how to multiply two 4-bit binary numbers

   Step 4:

   3*3+4*2+5*7+1*6=9+8+35+6+3(previous carry)=61

   New carry=6

   The design starts first with Multiplier design, that is 2×2 bit multiplier as shown in figure 2. Here, Urdhva Tiryakbhyam Sutra or Vertically and Crosswise Algorithm for multiplication has been effectively used to develop digital multiplier architecture. This algorithm is quite different from the traditional method of multiplication, which is to add and shift the partial products.

   Fig . 2 2×2 Vedic multiplier

3. 4×4 Bit Vedic Multiplier module:

   The 4×4 bit Vedic multiplier module is implemented using four 2×2 bit Vedic multiplier modules as discussed in fig. Lets analyze 4×4 multiplications, say A=A1A2A3A4 and b=B1B2B3B4 and the output line for the multiplication result is S7S6S5S4S3S2S1S0. Lets divide A&B into two parts say A1A2 & A3A4 for a and B1B2 &B3B4 for B. Using the fundamental of Vedic Multiplication, taking two bit at a time and using 2 bit multiplier block, we can have the following structure for multiplication as shown in the below fig

4. Design of 8×8 Vedic Multiplier module:

   The 8×8 bit Vedic multiplier module is implemented as shown in the below block diagram in fig. using four 4×4 bit Vedic multiplier modules as discussed in fig.

   Lets analyze 8×8 multiplications, say A=A7A6A5A4A3A2A1A0 and B=B7B6B5B4B3B2B1B0.

   The output line for the multiplication resultis S15S14S13S12S11S10S9S8S7S6S5S4S3S2S1S0. Lets divide

   A&B into two parts say AL=A3A2A1A0 & AH=A7A6A5A4 for A and BL=B3B2B1B0 & BH=B7B6B5B4 for B. Using the fundamental of Vedic Multiplication, taking four bit at a time and using 4 bit multiplier block, we can have the following structure for multiplication as shown in the below fig

   Fig . 4 8×8 vedic multiplier module

   Here before writing the verilog code for 8×8 Vedic multiplier we need to write the code for 8-bit and 12-bit adders.

   Fig . 3 4×4 vedic multiplier module

   In the above fig to complete the design We have to first write code for 4bit and 6 bit adders. Here we can use any adders according to our requirements. For better performance use CSA. In this design we used the + operator for a simpler design and which is supported by the XST synthesis tool which by default selects a low hardware adder.

5. 8×128 bit Vedic Multiplier module design:

To design 128×128 bit Vedic multiplier, we need to design 16×16 bit Vedic module by using four 8×8 modules. After designing of 16×16 bit Vedic module we have to design 32×32 bit Vedic module. In the same way 64×64 bit Vedic module also design by using four 32×32 bit Vedic modules.

In the 128 x128 bit Vedic module design we divide the two numbers into two 64 bit numbers like AL=A[0:63]A,AH=[64:127]A of A &

BL=[0:63]B,BH=[64:127]B of B. The multiplication result as S=[0:255]S. The block diagram is show in the below fig.

Fig . 5 128×128 bit vedic multiplier module

VI . IMPLEMENTATION OF 128X128 BIT VEDIC MULTIPLIER

The 128×128-bit Vedic multiplier is implemented in Xilinx ISE 14.2 and the simulation result is shown in the below fig.

The fpga implementation of 128×128 bit multiplier is anlysed in Chipscope in Xilinx ISE 14.2. The complete combinational path delay of one 4×4 bit vedic multiplier is 3.96ns .

In the design we used 4×4 bit multipliers to implement 128x 128 bit vedic multplier, so the delay in this design is less compared with the conventional multipliers.

V . CONCLUSION

The designs of 128×128 bit Vedic multiplier implemented on Xilinx Spartan 3E-250. The design is based on Vedic method of multiplication. The Vedic multipliers are much faster than the conventional multipliers. This gives us method for hierarchical multiplier design. So the design complexity gets reduced for inputs of large no of bits and modularity gets increased. Urdhva tiryakbhyam, Nikhilam and Anurupye sutras are such algorithms which can reduce the delay, power and hardware requirements for multiplication of numbers. FPGA implementation of this multiplier shows that hardware realization of the Vedic mathematics algorithms is easily possible. The high speed multiplier algorithm exhibits improved efficiency in terms of speed. We can use these multiplier modules in DSP applications like MAC, ALU etc.

REFERENCES

1. P. Saha, A. Banerjee, A. Dandapat, P. Bhattacharyya, Vedic Mathematics Based 32-Bit Multiplier Design for High Speed Low Power Processors international journal on smart sensing and intelligent systems vol. 4, no. 2, june 2011

2. Harpreet Singh Dhillon and Abhijit Mitra, A Digital Multiplier Architecture using UrdhvaTiryakbhyam Sutra of Vedic Mathematics

3. G.Ganesh Kumar, V.Charishma , Design of High Speed Vedic Multiplier using Vedic Mathematics TechniquesInternational Journal of Scientific and Research publications, Volume 2, Issue 3, March 2012 1 ISSN 2250-3153

4. Jagadguru Swami Sri Bharath, Krishna Tirathji, Vedic Mathematics or Sixteen Simple Sutras from The Vedas, Motilal Banarsidas, Varanasi (India), 1992.

5. Jeganathan Sriskandarajah, Secrets of Ancient Maths: Vedic Mathematics, Journal of Indic Studies Foundation, California

6. Vedic Maths Sutras – Magic Formulae [Online]. Available: http://hinduism.about.com/library/weekly/extra/blvedicmathsutras.htm.

7. A.P. Nicholas, K.R Williams, J. Pickles, Application of Urdhava Sutra, Spiritual Study Group, Roorkee (India),1984.

8. Himanshu Thapliyal, Vedic Mathematics for Faster Mental Calculations and High Speed VLSI Arithmetic, Invited talk at IEEE Computer Society Student Chapter, University of South Florida, Tampa, FL, Nov 14 2008.