Fpga Implementation Of High Speed Vedic Multipliers

Fpga Implementation Of High Speed Vedic Multipliers

Fpga Implementation Of High Speed Vedic Multipliers

S.Karthik1, Priyanka Udayabhanu2

Department of Electronics and Communication Engineering, Sree Narayana Gurukulam College of Engineering, Kadayiruppu, Ernakulam, Kerala – 682311

Abstract:

High speed and efficient multipliers are required in day to day complex computational circuits like digital signal processing, cryptography algorithms and high speed processors. Among various methods of multiplication, recently Vedic multipliers are being more efficient. This paper presents a design of high speed 4X4 bit Vedic multiplier architectures based on two different Vedic sutras namely, Urdhva-Triyag and Nikhilam. These sutras meant for faster mental calculation. Among these two sutras Urdhva-Triyag is more efficient than Nikhilam and other multipliers with respect to speed. The most significant aspect of Urdhva-Triyag sutra is that, the developed multiplier generates all partial products in one step. High speed adders are used in the architecture instead of conventional Ripple carry adders thereby reducing the delay further. In Nikhilam multiplier architecture Urdhva-Triyag sutra is used for more efficiency. The Vedic multiplier architectures are coded in Verilog HDL and synthesized using Xilinx ISE 13.3. The proposed multiplier architectures are targeted to Spartan 3E FPGA. Finally the results are compared with conventional multipliers to show the efficiency in terms of speed.

Keywords – Urdhva-Triyag, Nikhilam, Carry select adder

1. INTRODUCTION

   The need of high speed and low power multipliers are increasing day by day in digital signal processing and high speed general purpose processor design. Two most common multiplication algorithms followed in the digital hardware are array multiplication algorithm and Booth multiplication algorithm. The computation time taken by the array multiplier is comparatively less because the partial products are calculated independently in parallel. The mathematical

   operations using Vedic Method are very fast and requires less hardware, this can be used to improve the computational speed of processors. Veda, by definition, is knowledge. Hence Vedic Math has a much ancient origin though attributed to the techniques rediscovered between 1911-1918 [1]. This paper describes the design and implementation of 4×4 bit Vedic multiplier based on Urdhva-Triyag sutra (Vertically and Crosswise technique) and Nikhilam sutra [2] of Vedic Mathematics using EDA (Electronic Design Automation) tool. In this, Urdhva- Triyag Sutra is first applied to the binary number system and is used to develop digital multiplier architecture. This Sutra shows the effectiveness to reduce the NXN multiplier structure into an efficient N/2XN/2 multiplier structures. Nikhilam Sutra is then discussed and is shown to be much more efficient in the multiplication of large numbers as it reduces the multiplication of two large numbers to that of two smaller ones. The proposed multiplication algorithms are then illustrated to show the computational efficiency by taking an example of reducing a 4X4-bit multiplication to a single 2X2-bit multiplication operation. A generalized NXN bit Vedic algorithm also discussed to implement higher end multipliers in future.

   The paper is organized as follows. Section II describes the Urdhva-Triyag Sutra of Vedic multiplication technique and its architecture. Section III focuses the Nikhilam sutra of Vedic multiplier architecture. Section IV is devoted to describe the design & implementation of Vedic multiplier modules in XilinxISE13.1. In Section V we present the Results and Discussion in which device utilization summary and computational path delay obtained for the proposed Vedic multiplier architectures (after synthesis) is discussed. Finally conclusions of present study is given in section VI.

2. 4X4 BIT VEDIC MULTIPLIER USING URDHVA-TIRYAG sutra

   The proposed Vedic multiplier is based on the Urdhva-Triyag sutra (algorithm). These Sutras have been traditionally used for the multiplication of two numbers in the decimal number system. Here we apply the same ideas to the binary number system to make the proposed algorithm compatible with the digital hardware. It 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 (325 * 728) which is shown in Figure.1 [2]. The digits on the two ends of the line are multiplied and the result is added with the previous carry. When there are more lines in one step, all the results are added to the previous carry.

   Figure 1. Multiplication of two numbers

   Vertically and Crosswise

   The least significant digit of the number thus obtained acts as one of the result digits and the rest act as the carry for the next step. Initially carry has to be taken as zero.

   Steps:

   1. 5 X 8 = 40: 4, the carried over digit is placed below the second digit.

   2. (3 X 5) + (8 x 2) = 31 + 4 = 35; 3, the carried over digit is placed below third digit.

      iii) (5 X 7) + (3 X 8) + (2 X 3) = 65+3 = 68; 6, the

      carried over digit is placed below fourth digit.

      iv) (2 X 7) + (3 X 3) = 14 + 9 = 29; 2, the carried over digit is placed below fifth digit.

      v) (3X7) =21+6..

      1. URDHVA-TIRYAG FOR 2X2 BINARY MULTIPLIER:

   The hardware architecture of 2×2 and 4×4 bit Vedic multiplier (VM) modules are given in the following sections. Here, Urdhva-Triyag (Vertically and Crosswise) sutra is used to propose such an architecture for the multiplication of two binary numbers. Then this Vedic multiplier is used to multiply two 4 bit numbers. The 2X2 Vedic multiplier module is implemented using four input AND gates & two half-adders which is displayed in its block diagram (Fig. 3). It is found that the hardware architecture of 2×2 bit Vedic multiplier is same as the hardware architecture of 2×2 bit conventional Array Multiplier.

   Figure 3 Architecture of 2X2 Urdhva-Triyag multiplier

   Specifically we can say that the total delay is only 2- half adder delays, after final bit products are generated, which is very similar to Array multiplier. So we change over to the implementation of 4×4 bit Urdhva-Triyag multiplier which uses the 2×2 bit multiplier as a basic building block. The same method can be extended for input bits 4 & 8.

   The 4×4 bit Vedic multiplier module is implemented using four 2×2 bit Vedic multiplier modules as discussed. Divide the no. of bits in the inputs equally in two parts. Let us analyze 4×4 bit multiplication, say multiplicand A=A3A2A1A0 and multiplier B= B3B2B1B0. Following are the output line for the multiplication result, S7S6S5S4S3S2S1S0. Let us divide A and B into two parts, say A3 A2 & A1

   A0 for A and B3 B2 & B1 B0 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 4×4 bit multiplication as shown in Figure 4.

   Figure 4 Structure for 4X4 Urdhva-Triyag multiplier

   Each block as shown above is 2×2 bit Vedic multiplier. First 2×2 bit multiplier inputs are A1A0 and B1B0. The last block is 2×2 bit multiplier with inputs A 3 A2 and B3 B2. The middle one shows two 2×2 bit multipliers with inputs A1A0 & B3 B2 and A3 A2 & B1 B0 respectively. So the final result of multiplication, which is of 8 bit, S7 down to S0. The block diagram of Urdhva-Triyag 4×4 bit Vedic mltiplier is shown in Figure 5. By using CSA in the design the delay is considerably reduced to 9ns. The comparison of Carry select adder with Ripple carry adder is given in below sections.

   Figure 5. Block diagram of Urdhva-Triyag 4×4 multiplier.

3. 4X4 BIT VEDIC MULTIPLIER USING NIKHILAM SUTRA

   1. This work focuses on the implementation of Nikhilam Sutra. The operation behind this type of sutra is very simple. The nearest base is chosen first. The multiplicand and the multiplier will be subtracted from the nearest base, which is equivalent to taking 2s complement. Then the product of the 2s complement and the common difference will give the final result. Figure 6 shows an example [4] for multiplying two numbers (96*93). In this case the common base is 100. Both 96 and 93 are subtracted from 100 which will give 4 and 7 respectively. The product of 4 and 7 is 28 and the common difference (96 7) and (93 4) is 89. By concatenating 89 and 28 the final result is obtained.

      Figure 6 Multiplication using Nikhilam sutra

      With this logic Manoranjan Pradhan et.al. [4] had proposed an architecture for Nikhilam sutra. Choosing a nearest base and subtracting the multiplicand and multiplier is equivalent to taking 2s complement of the numbers. Figure 6 shows the architecture of the Nikhilam Sutra multiplier.

      Figure 7. Architecture of the Nikhilam Sutra multiplier.

      The 2s complement is taken for the Multiplier and the Multiplicand. The output of the twos complement is then multiplied. If it is an N X N bit multiplication this multiplier will have 2N number of bits as output. The lower half i.e. the last (N) bits will be the result of the multiplier and the first N bits will be the result of the carry save adder.

      Nikhilam sutra multiplier will operate at high speed [7], but the power consumed by this multiplier will also be high. The power can be reduced by making modifications in the architecture shown in Fig.2. The architecture for the Nikhilam sutra is taken and implemented with little modifications in 2s complement, Multiplier and Adder blocks.

   2. Modification of blocks:

   In conventional way the binary number is complemented and one is added to the complemented number. In their proposed work the 2s complement is determined by directly assigning the values to the output as a lookup table. The advantage of finding 2s complement by this method is that the addition stage will not be necessary here. So the power consumed by the design will be reduced.

   The multiplier block proposed here makes use of 4X4 binary multiplier using Urdhva-Triyag discussed in the previous section. This greatly reduces the delay as compared to conventional multipliers. Finally in the last stage instead of using carry save adder a synthesized adder is used i.e., the addition is carried out directly using operator which then synthesized by the tool. This adder shows less delay (7.5 ns) when synthesized. All these amendments make this multiplier suitable for high speed applications.

4. DESIGN AND IMPLEMENTATION

   In this work, all the modules of the 4X4 bit Vedic multiplier architectures based on two different Vedic sutras namely, Urdhva-Triyag and Nikhilam are coded using Verilog HDL. Logic synthesis and simulation were done using EDA (Electronic Design Automation) tool in XilinxISE13.3i – Project Navigator and ISim simulator integrated in the Xilinx package. The performance of circuit is evaluated on the Xilinx device family Spartan3, package FG320 and speed grade -5.

   The RTL schematic of 4X4 bit Vedic multiplier architectures based on Urdhva-Triyag and Nikhilam sutras are shown in Figure 8. The RTL schematic of 4X4 Urdhva-Tiryag multiplier has four 2X2 Urdhva- Triyag multipliers and adder is carry select adder. The RTL schematic of 4X4 Nikhilam multiplier has 4X4 Urdhva-Triyag multiplier, modified 2s complement and adder blocks.

   The simulation result of the 4X4 bit Vedic multiplier architectures based on Urdhva-Triyag and Nikhilam sutras are shown in Figure 7. The simulation is done with ISim Simulator. In behavioral simulation we have tested for the following input bits

   Figure 7 Simulation results

   1. For 4X4 bit Urdhva-Triyag Vedic multiplier input, the multiplier a=1111 (decimal number system 15) and multiplicand b=1111 (decimal number system 15) and we get 8-bit output1= 11100001 (decimal number system 225). Next the multiplier a=1101(decimal number system 13) and multiplicand b= 0010(decimal number system 2) and we get 8-bit output1= 00011010.

   2. For 4X4 bit Nikhilam Vedic multiplier input, the multiplier a=1110 (decimal number system 14) and multiplicand b=1111 (decimal number system 15) and we get 8-bit output1= 11010010 (decimal number system 210).

Figure 8 . RTL Schematic V RESULTS AND DISCUSSION

The synthesis result obtained from proposed 4X4 bit Urdhva-Triyag Vedic multiplier is faster than Array and Booth multipliers. The proposed 4X4 bit Nikhilam Vedic multiplier is faster than Array multiplier and almost similar to Booth multiplier. Even the proposed 4X4 bit Nikhilam multiplier is not as fast as 4X4 bit Urdhva-Triyag Vedic multiplier the power consumed by the design can be reduced to some extent by modification of blocks in Nikhilam multiplier. The device utilization summary of 4X4 bit Vedic multipliers for Xilinx, Spartan family is shown below:

Table 1 shows the comparison of 4X4 bit conventional multipliers with Vedic multipliers in terms of computational path delay in nanoseconds (ns). The path delay for 4X4 bit Array and Booth multipliers have been taken from Umesh Akare et al [7]. The path delay for proposed 4X4 bit Urdhva- Triyag Vedic multiplier with carry select adder is lesser than the delay of 4X4 bit Urdhva-Triyag

multiplier with RCA taken from Pushpalatha Verma et al [6].The timing result shows that Vedic multiplier has the greatest advantage as compared to other multipliers in terms of execution time. Table.2 shows the comparison of the performance of Nikhilam multiplier in three cases taken from Sree nivas A et al [8]. From this it is clear that the modifications in Nikhilam multiplier blocks will reduce power to some extent. The output on Spartan board is shown in Figure 9

Table 2. Power comparison of Nikhilam multiplier

Figure 9 Output on Spartan 3E

VI CONCLUSION

In this paper a new architecture for high speed 4X4 bit Vedic multipliers based on two different Vedic sutras namely, Urdhva-Triyag and Nikhilam is presented. Simulation and synthesis is carried out for all the modules and the path delay is compared with other conventional multipliers. From this work it is clear that 4X4 bit Vedic multiplier using Urdhva- Triyag is most suitable for high speed applications. It is also clear that the power to proposed Nikhilam multiplier can also be reduced by further block modifications. These Vedic multipliers can be implemented for any number of bits by adopting the generalized algorithm discussed. Finally we conclude that our proposed Vedic multipliers are most suitable for high speed as well as low power digital signal processing and cryptography applications.

References:

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

2. VEDI MATH MULTIPLICATION by Sree

   N. Sreenath, Ph.D., The Vedic Math Guy Lotus, Indian -Community Monthly Newspaper, Cleveland, February 2003.

3. Asmita Haveliya FPGA IMPLEMENTATION OF A VEDIC CONVOLUTION ALGORITHM International Journal of Engineering Research and Applications (IJERA) Vol. 2, Issue 1 Jan-Feb 2012, pp.678-684

4. Manoranjan Pradhan, Rutuparna Panda, Sushanta Kumar Sahu, Speed Comparison of 16×16 Vedic Multipliers, International Journal of Computer Applications (0975 8887), vol 21 No.6, May 2011.

5. M. Morris Mano, Computer System Architecture, 3rd edition, Prentice-Hall, New Jersey, USA, 1993, pp. 346-348.

6. Pushpalata Verma, K. K. Mehta Implementation of an Efficient Multiplier based on Vedic Mathematics Using EDA Tool International Journal of Engineering and Advanced Technology (IJEAT) ISSN: 2249 8958, Volume-1, Issue-5, June 2012

7. Umesh Akare, T.V. More and R.S. Lonkar, Performance Evaluation and Synthesis of Vedic Multiplier, National Conference on Innovative Paradigms in Engineering & Technology (NCIPET-

   2012), Proceedings published by International Journal of Computer Applications (IJCA), 2012.

8. Sree Nivas A, Kayalvizhi N Implementation of Power Efficient Vedic Multiplier International Journal of Computer Applications (0975 8887) Volume 43 No.16, April 2012