Design and Implementation of Vedic Multiplier using Compressors

Design and Implementation of Vedic Multiplier using Compressors

Harish Kumar

Department of ECE Bangalore Institute of Technology

Bangalore, India

Hemanth Kumar A R

Department of ECE Bangalore Institute of Technology

Bangalore, India

Abstract It is a well-known fact that the multiplier unit forms an integral part of processor design. Hence high speed multiplier architectures become essential. This paper presents a technique to modify the architecture of the Vedic (Urdhva Tiryakbhyam) multiplier by using compressor in order to reduce area and delay to improve overall performance when compared with earlier existing architecture of Vedic multiplier and some common multipliers. The proposed design shows very good results in terms of time delay and area. The designs were synthesized and examined in Cadence RTL compiler in 45 nm technology.

Index Terms Vedic multiplier, High-speed, Low area, Urdhva-Tiryakbhyam, compressor.

I. INTRODUCTION

While using computers and smart phones sometimes we face a situation where the device (hangs) stops responding. One of the reasons behind it is processor speed that motivated us to go for a high speed multiplier design. Multiplier in special application processors like Digital Signal Processor (DSPs) improves the speed of operation since the entire signal and data processing operations involve multiplication. Multiplication plays a vital role in DSP applications (like DFT, convolution, FFT etc.), Arithmetic and logic unit (ALU), and Multiply and Accumulate (MAC) unit. High Speed Multiplication thus becomes a necessity to increase the performance of processor.

Quite a few multipliers [1] have been designed and proposed over last few decades but for multiplication these designs need several intermediate stages to calculate the final result due to which critical path length increases hence cause more delay. Moreover, the intermediate stages need additional hardware which becomes reason for increased area and power consumption. In [2], [3] and [4] a new approach for multiplier design based on Vedic Mathematics is explored to overcome these disadvantages. Vedic Mathematics is an ancient and prominent approach that serves as base to solve many mathematical challenges experienced nowadays. Swami Bharati Krishna Tirthaji Maharaja (1884-1960) [5], a popular mathematician rediscovered and segregated ancient Vedic mathematics into 16 simple sutras (formulae) that are related to Arithmetic, Algebra, Geometry, Trigonometry, Analytical Geometry etc. These sutras are very simple and hence can be applied in various fields of engineering like computing, Signal Processing and VLSI [6].

In Vedic mathematics approach the partial products are calculated well in advance, even before the beginning of actual operations of multiplication. Then the final product is obtained by adding these partial products according to Vedic algorithm. This approach in turn provides a very high speed multiplication [4].

In this paper, we introduce modified compressor based multiplier architecture. This modified structure uses the 3:2 compressor, 4:2 compressor and 7:2 compressor architectures to construct 8-bit multiplier using Vedic Mathematics (Urdhva Tiryagbhyam sutra).Use of compressors instead of half adders and full adders help to improve the speed. Compressors, are logic circuits capable of adding more than 3 bits at a time with a lesser gate count and higher speed in contrast with an equivalent full adder circuit [7].

In this paper Section II describes Urdhva Tiryakbhyam Sutra for 8-bit multiplication. Explanations for compressors used for proposed multiplier architecture are given in Section

1. Section IV is description of the proposed multiplier. In Section V and Section VI the comparative results and conclusions are discussed.

   1. VEDIC FORMULA – URDHVA TIRYAKBHYAM Veda is a Sanskrit word derived from the root Vid, which

      means to know without limit. There are four main Vedas among which Atharva Veda is source of The 16 Sutras (or aphorisms) of Vedic Mathematics.

      Vedic mathematics is not only limited to India but has become an interesting topic of research abroad because of the fact that it reduces the calculations which appears complex to us in conventional mathematics to a very simple one. The reason behind this is the Vedic formulae are claimed to be based on the natural principles of the working of human mind. Among these 16 formulae, Urdhva Tiryakbhyam proves to be quite useful concept through which all partial products are generated concurrently and applicable to all cases of multiplication. Urdhva Tiryakbhyam is term in Sanskrit language that literally means Vertically and Crosswise [5]. Fig.1 gives the clear picture of the method in which the black dots at tops and bottoms of each steps represent multiplier and multiplicand bits, and the two-way arrows are indication for the bits to be multiplied to get the individual bits of the final product. Each step shown in the figure results in individual bits

      of the final 16 bit product. If we consider two 8 bit numbers A7-A0 and B7-B0 then step 1 shows that we have to multiply A0 and B0 to get P0. In step 2 the second bit of product P1 will be calculated by adding (A1*B0) and (A0*B1) as given in equation (2) .the carry will be added to the next step. The process continues till we get all the bits of final product. The final computed product is represented by P0 to P15 which are calculated by adding partial products obtained earlier using logical AND operation. C1 to C32 are the carry bits generated during the calculation of the individual bits of the final product. The carry bits generated in the last can be ignored if they are superfluous.

      P0 =A0 * B0 (1)

      C1P1 = (A1 * B0) + (A0 * B1) (2) C3C2P2 = (A2 * B0) + (A0 * B2) + (A1 * B1)

      + C1 (3)

      C5C4P3 = (A3 * B0) + (A2 * B1) + (A1 * B2)

      + (A0 * B3) +C2 (4)

      C7C6P4 = (A4 * B0) + (A3 * B1) + (A2 * B2)

      + (A1 * B3) + (A0 * B4) +C3 + C4 (5)

      C10C9C8P5 = (A5 * B0) + (A4 * B1) + (A3

      * B2) + (A2 * B3) + (A1 * B4) +

      (A0 * B5) +C5 + C6 (6)

      C13C12C11P6 = (A6 * B0) + (A5 * B1) + (A4

      * B2) + (A3 * B3) + (A2 * B4) +

      (A1 * B5) + (A0 * B6) +C7 + C8 (7)

      C16C15C14P7 = (A7 * B0) + (A6 * B1) + (A5

      * B2) + (A4 * B3) + (A3 * B4)

      + (A2 * B5) + (A1 * B6) +

      (A0 * B7) +C9 + C11 (8)

      C19C18C17P8 = (A7 * B1) + (A6 * B2) + (A5

      * B3) + (A4 * B4) + (A3 * B5)

      + (A2 * B6) + (A1 * B7) +

      C10 +C12 + C14 (9)

      C22C21C20P9 = (A7 * B2) + (A6 * B3) + (A5

      * B4) + (A4 * B5) + (A3 * B6)

      + (A2 * B7) + C13 +C15 +C17 (10)

      C25C24C23P10 = (A7 * B3) + (A6 * B4) + (A5

      * B5) + (A4 * B6) + (A3 * B7)

      +C16 + C18 + C20 (11)

      C27C26P11 = (A7 * B4) + (A6 * B5) + (A5 * B6)

      + (A4 * B7) + C19 +C21 + C23 (12)

      C29C28P12 = (A7 * B5) + (A5 * B6) + (A5 *

      B7) + C22 + C24 +C26 (13)

      C31C30P13= (A7 * B6) + (A6 * B7) + C25 +

      C27 + C28 (14)

      C32P14 = (A7 * B7) + C29 + C30 (15)

      P15 = C31 + C32 (16)

      The architecture of the 8×8 Urdhva Multiplier using full adders and half adders is shown in Fig.2.

      Fig. 1. Pictorial representation of Urdhva Tiryakbhyam Sutra for multiplication of 2 eight bit numbers

      Fig. 2. Architecture of Urdhva Tiryakbhyam multiplier using full adders and half adders. The gray colored blocks are full adders and the white colored blocks is shown for half adders

   2. COMPRESSORS

      Compressor or a compressor adder is a combinational circuit, used to add more than three bits at a time. Here by using 4:2 compressors and 7:2compressors we can easily replace the combination of some full adders and half adders that is used in the normal Urdhva-Tiryakbhyam multiplier architecture, hence it gives scope for design of high speed

      performance processors. The related compressors circuits are deliberated below.

      1. 3:2 Compressor

         The 3:2 compressors is a combinational circuit that can add 3 single bit inputs and produces 2 bit output. In Fig. 3 the gate level structure of 3:2 compressor is depicted [8].

         Fig. 3. Gate level diagram of 3:2 compressor.

      2. 4:2 Compressor

         The 4:2 compressors is a combinational circuit that can add 4 single bit inputs and one carry input bit to produce 3 bit output. In Fig. 4 the gate level structure of 4:2 compressor is depicted [13].It uses 3:2 compressor and it was shown in Fig 4. We can observe that the critical path is smaller when compared with an equivalent circuit that can add 5 bits by using full adders and half adders [9].

         Fig. 4. 4:2 Compressor structure by using 3:2 compressor.

      3. 7:2 Compressor

      The 7:2 compressors is capable of adding 7 single bit inputs and two carry inputs from previous stage at a time, and as a result produces 4 bit output. The 7:2 compressor here utilizes the five 3:2 compressors. We can see the architecture for 7:2 compressor in Fig 5 [9].

      Fig. 5. 7:2 Compressor structure by utilizing 3:2 compressors

   3. PROPOSED MULTIPLIER

      Urdhva Tiryakbhyam method based multiplier uses several full adders and half adders for partial products addition and results in large propagation delay. This propagation delay can be reduced by using compressors in the basic Urdhva Tiryakbhyam multiplier architecture. [9] Suggests one of the possible architecture but when we look at the number of parallel stages it can still be improved. Therefore we have proposed an architecture for the multiplier by using compressors and half adders that consists of just 2 parallel stages whereas the previous design have 12 parallel stages

      .The significant amount of reduction in the number of parallel stages is a major improvement as we are going for low area and high speed design. The proposed architecture is shown in Fig. 6.

      Fig. 6. Hardware architecture of proposed multiplier

   4. RESULTS

      To compare the performance among various multipliers such as Array multiplier, Urdhva multiplier, Karatsuba algorithm optimized multiplier [10] and modified compressor based Urdhva multiplier were designed using Verilog coding and evaluated by Cadence Encounter RTL Compiler in 45 nm technology by mapping the design to the fast library. Effectiveness of the proposed multiplier design can be clearly observed by looking at Table 1, where the results have been tabulated.

      Fig. 7. RTL schematic of proposed 8 bit multiplier

      Table 1. Comparison of speed and area occupied by different multiplier architectures

      The delay is minimum for proposed multiplier and also the area occupied by this design is reduced since the compressor based adders reduces the number of gates as compared to a full adder or half adder.

   5. CONCLUSION

Hence In this paper, a high speed multiplier architecture for multiplication of two 8 bit numbers that includes the advantages of compressor based adders and the ancient Vedic maths methodology is proposed. The proposed multiplier is compared with that of existing Urdhva multiplier and two other popular multipliers. After comparison of its speed and area occupied by the multiplier we can deduce that the proposed architecture of compressor based Vedic maths multiplier is better than conventional multipliers used in several complex VLSI circuits. As a future work, the multiplier can be expanded for 16 bits and 32 bits and can be tested for its performance after implementing in an ALU.

REFERENCES

1. Swee, K. L. S. , Lo Hai Hiung, Performance Comparison Review of 32-Bit Multiplier Designs, 4th International Conference on Intelligent and Advanced Systems (ICIAS), 2012

   , IEEE proc. , vol. 2, pp 836-841

2. L. Sriraman, T.N. Prabakar, Design and Implementation of Two Variable Multiplier Using KCM and Vedic Mathematics, 1st Int. Conf. on Recent Advances in Information Technology, Dhanbad, India, 2012, IEEE Proc., pp. 782-787.

3. M. Ramalatha, K. Deena Dayalan, S. Deborah Priya, High Speed Energy Efficient ALU Design using Vedic Multiplication Techniques, Advances in Computational Tools for Engineering Applications, 2009, IEEE Proc., pp 600-603.

4. Honey Durga Tiwari, et al., "Multiplier design based on ancient Indian Vedic Mathematics, " Int. SoC Design Conf., 2008, vol.

   2. IEEE Proc., pp. II-65 – II-68.

5. Jagadguru Swami Sri Bharati Krisna Tirthaji Maharaja, Vedic Mathematics: Sixteen Simple Mathematical Formulae from the Veda,pp. 5-45, Motilal Banarasidas Publishers, Delhi, 2009

6. Himanshu Thapliyal and M. B. Srinivas, An efficient method of elliptic curve encryption using Ancient Indian Vedic Mathematics, 48th IEEE Int. Midwest Symp. on Circuits and Systems, 2005, vol. 1, pp. 826-828.

7. Hsiao, Shen-Fu, Ming-Roun Jiang, and Jia-Sien Yeh, "Design of highspeed low-power 3-2 counter and 4-2 compressor for fast multipliers, IEEE Electronics Letters, vol. 34, no.4, pp. 341- 343, Feb. 1998.

8. Naveen Kr. Gahlan, PrabhatShukla, JasbirKaur, Implementation of Wallace Tree Multiplier Using Compressor

   IJCTA, vol 3 (3), pp. P1194-1199, MAY-JUNE 2012

9. Sushma R. Huddar Sudhir Rao , Kalpana M and Surabhi Mohan , Novel High Speed Vedic Mathematics Multiplier using Compressors

   IEEE Conf.VLSI, pp.465-469, 2013

10. G.Ganesh Kumar, V.Charishma,Design of High Speed Vedic Multiplier using Vedic Mathematics Technique International Journal of Scientific and Research Publications, Volume 2, Issue 3, March 2012.

Author Profile

Harish Kumar received his B.E. degree in Electronics and Communication Engineering from East Point College of Engineering and Technology in 2012. He is presently pursuing his final year M.Tech in VLSI Design and Embedded Systems from Bangalore Institute of Technology and the proposed research work in this paper is part of his M.Tech thesis. His area of interests includes very-large-scale integration digital circuit design, embedded systems and Verilog based projects.

Dr. Hemanth Kumar A. R is presently working as Professor & Principal Investigator R&D, ECE, at BIT, Bangalore. He completed his B.E in E&C from Manipal Institute of Technology in the year 1999. He specialized in Digital Communication from B.M.S College of Engineering in 2003 and received hi PhD from Manipal University in 2011. His area of interest includes MANETS, Clustering the network, Path Planning and Routing algorithms. He has published 24 international papers in various indexed

journals, and national conference in India, Singapore, and Thailand.