High Performance Vedic Multiplier Using Han-Carlson Adder

Download Full-Text PDF Cite this Publication

Text Only Version

High Performance Vedic Multiplier Using Han-Carlson Adder

Gijin V George

Department of Electronics & Communication Engineering Rajagiri School of Engineering & Technology

Kochi, India

Anoop Thomas

Department of Electronics & Communication Engineering Rajagiri School of Engineering & Technology

Kochi, India

Abstract Multiplication is one of the main functions in a Digital Signal Processing System. The overall performance of the DSP system depends on the performance of the multiplier. Hence it is very important to develop an efficient and fast design to implement multiplier. Vedic mathematics can be used to transform tedious calculations into simpler and orally manageable operation. Vedic multiplication uses Urdhva Triyambakam multiplication algorithm. The Vedic multiplication algorithm generates partial products in parallel. In this work, we propose using Han-Carlson adder to improve the performance of Vedic multiplier. We compare the performance of the proposed design with Vedic multiplier that uses Kogge- Stone adder. A 24-bit Vedic multiplier is implemented, which can be used for mantissa multiplication in single-precision floating- point multiplier. The proposed multiplier is coded in Verilog HDL. Xilinx ISE 8.2i is used to simulate and synthesis the design.

Keywords Vedic mathematics; Parallel prefix adder; Vedic multiplier; Han-Carlson adder; Kogge-Stone adder.

  1. INTRODUCTION

    Multiplication is considered to be one of the most time consuming basic mathematical operation. In digital signal processing systems, multiplication is one of the most important functions and overall performance of the DSP system depends on the multiplier unit [1]. It is used in many algorithms such as FFT, DFT, and IDFT etc. Hence it is utmost important to develop an efficient and fast design to implement multiplier.

    Vedic mathematics hails from the ancient Indian system of calculation. The use of Vedic multiplication improves the speed of multiplier by producing partial products in parallel. The performance of the Vedic multiplier can be further improved by using parallel prefix adders. In this work we propose using Han-Carlson adder to improve the performance of Vedic multiplier. We compare our proposed design with the implementation of Vedic multiplier using Kogge-Stone adder and ripple carry adder. Here a 24-bit Vedic Multiplier is designed, which can be used for Mantissa multiplication in single-precision floating-point multiplier.

  2. VEDIC MATHEMATICS

    Vedic Mathematics is the name given to the ancient Indian system of calculations. The meaning of the Sanskrit word

    Veda is knowledge [2]. Vedic mathematics is based this sixteen principles or formulas known as Sutras. Vedic Sutras can be applied to almost every field of mathematics [3]. The beauty of Vedic mathematics is that its algorithms are designed in the same way as a human mind works. It can be used to

    transform the tedious calculations into simpler and orally manageable operation without much help of pen and paper.

    The Vedic system is interrelated and unified so that the simple multiplication methods can easily be reversed to allow one-line divisions, and the basic squaring method can easily be reversed to get one-line square roots.

  3. VEDIC MULTIPLICATION

    Vedic mathematics proposed various methods for multiplication. In this work, we use multiplication technique based on the Sutra Urdhva Triyambakam which means

    Vertically and Crosswise. It is a general algorithm applicable to all cases of multiplication and can also be used in the division of a large numbers. The Vedic multiplication was originally used for multiplication in decimal number system, the same can be adapted easily for binary numbers [4]. Fig. 1 explains the algorithm used for multiplication of two 3-bit binary numbers. The two binary operands A and B are represented respectively as A2 A1 A0 and B2 B1 B0.

    Fig. 1. Vedic multiplication steps for 3-bit binary numbers.

  4. N-BIT VEDIC MULTIPLIER

    An N-bit Vedic multiplier is designed using N/2-bit multipliers and N-bit adders. Fig. 2 illustrates the block diagram of an N-bit Vedic multiplier.

    It can be divided into three main stages.

    1. Propagate and Generate signal generation

    2. Carry generation network

    3. Sum calculation

      Fig. 4. Carry operator.

      The parallel prefix adder is constructed using carry operators, which is illustrated in the Fig. 4. The operation of carry operator is explained in (1), where P and G are propagate and generate signals respectively.

      P Pi Pj

      G Pi Gj Gi

      (1)

      Fig. 2. N-bit Vedic multiplier.

      Here N-bit multiplicands are decomposed into pairs of (N/2)-bit MSB and LSB. Using this design a 6-bit multiplier makes use of 3-bit Vedic multipliers and 6-bit adders. Consequently, this 6-bit multiplier can be used to design a 12- bit multiplier. In this work, we design a 24 bit Vedic multiplier. Our proposed design uses Han-Carlson adder in Vedic multiplier to improve its performance. We compare its performance with that of Kogge-Stone and ripple carry adder.

  5. PARALLEL PREFIX ADDER

    The Parallel Prefix Adder (PPA) is considered to be one of the fastest type of adder design possible. It is a commonly used adder type for high speed addition. It is flexible and well suited for VLSI implementation [5]. In parallel prefix adder generate and propagate signals are pre-computed. Fig. 3 shows the structure of a parallel prefix adder.

    Fig. 3. Parallel prefix adder structure.

    A parallel prefix graph consisting of carry operator nodes can be used to represent a parallel prefix adder. The structure of the parallel prefix graph determines the type of the parallel prefix adder [6]. Most commonly used parallel prefix adder are Kogge-Stone, Brent-Kung and Han-Carlson adder.

    1. Kogge-Stone Adder

      The Kogge-Stone adder generates carry signals in O (log n) time, and is considered to be the fastest adder. The parallel prefix graph of Kogge-Stone adder is shown in Fig. 5. The high speed of Kogge-Stone adder is because of its minimum logic depth and lower fan-out [7]. The main disadvantage of Kogge- Stone adder is that it occupies large area and has high wiring congestion

      Fig. 5. Kogge-Stone adder.

    2. Brent-Kung Adder

      The Brent-Kung adder is one of the most advanced adder designs. Its performance is lower compared to Kogge-Stone adder, but it takes less area to implement and has less wiring congestion. The parallel prefix graph of Brent-Kung adder is shown in Fig. 6.

      Fig. 6. Brent-Kung adder.

    3. Han-Carlson Adder

    The Han-Carlson adder is a blend of the Brent-Kung and Kogge-Stone adders. It uses one Brent-Kung stage at the beginning followed by Kogge-Stone stages, terminating with another Brent-Kung stage to compute the odd numbered prefixes [8]. It provides better performance compared to Kogge-Stone for smaller adders. The parallel prefix graph of Han-Carlson adder is shown in Fig. 7.

    Fig. 7. Han-Carlson adder.

  6. SIMULATION AND RESULTS

    Simulation and synthesis is done using Xlinx ISE8.2i, selecting device Spartan-3E FPGA (XC3S500E-4FG320C). The adder abbreviations used in the following discussions are: RCA for the ripple carry adder, KSA for the Kogge-Stone adder, and HCA for the Han-Carlson adder. Table.1 shows the synthesis results of different adders.

    TABLE 1. COMPARISON BETWEEN VARIOUS MULTIPLIERS

    No. of Bits

    /td>

    Adder

    Delay (ns)

    Slices

    LUTs

    6-bit

    RCA

    15.527

    7

    12

    KSA

    15.407

    7

    12

    HCA

    14.052

    8

    14

    12-bit

    RCA

    24.963

    14

    24

    KSA

    18.497

    25

    43

    HCA

    17.070

    22

    39

    24-bit

    RCA

    44.355

    28

    48

    KSA

    27.921

    79

    139

    HCA

    20.196

    59

    104

    Simulation result for 24-bit Vedic multiplier is shown in Fig. 8.

    Fig. 8. Simulation result for 24-bit Vedic multiplier.

    Comparison of Vedic multiplier using different adder is give in Table 2. The results clearly shows that the performance of Vedic multiplier using Han-Carlson adder is higher, in terms of both delay and area, compared to multiplier using Kogge- Stone adder.

    TABLE 2. COMPARISON BETWEEN VEDIC MULTIPLIERS USING DIFFERENT ADDER

    Multiplier

    Delay (ns)

    Slices

    LUTs

    IOBs

    RCA

    84.889

    1038

    1844

    96

    KSA

    72.330

    1370

    2395

    96

    HCA

    64.116

    1283

    2269

    96

  7. CONCLUSION

Higher speed multipliers are required in many digital signal processing and image processing applications. In this paper, high performance Vedic multiplier using Han-Carlson adder is proposed. The benefit of using Han-Carlson adder is its high operational speed. Synthesis results shows that the performance parameters such as area and delay are reduced compared to multiplier using Kogge-Stone adder with lower number of bits, which makes it more power efficient. Due to its regular and

parallel structure the proposed design can be realized on silicon as well. The proposed multiplier is very useful for the microprocessors and DSP processors whose performance is dependent upon the efficiency of multiplier.

REFERENCES

  1. R. Pushpangadan, V. Sukumaran, R. Innocent, D. Sasikumar, and V. Sundar, High Speed Vedic Multiplier for Digital Signal Processors, IETE journal of research, vol. 55, issue 6, pp. 282-286, 2010.

  2. M.E Paramasivam, and R.S Sabeenian, An efficient bit reduction binary multiplication algorithm using Vedic methods, IEEE 2nd International Advance Computing Conference, Patiala, India, pp. 25, 19- 20 Feb. 2010.

  3. L. Sriraman, and T. N. Prabakar, Design and Implementation of Two Variable Multiplier Using KCM and Vedic Mathematics, IEEE, 2012.

  4. Kunchigi.V, Kulkarni.L, and Kulkarni.S, High speed and area efficient Vedic multiplier, Devices, Circuits and Systems (ICDCS), 2012 International Conference on, pp.360-364, 15-16 March 2012.

  5. Nurdiani Zamhari, Peter Voon, Kuryati Kipli, Kho Lee Chin, and Maimun Huja Husin, Comparison of Parallel Prefix Adder (PPA), Proceedings of The World Congress on Engineering 2012, pp816-818, July 4-6, 2012.

  6. Konstantinos Vitoroulis, and Asim J. Al-Khalili, Performance of Parallel Prefix Adders implemented with FPGA technology, Circuits and Systems, 2007. NEWCAS 2007. IEEE Northeast Workshop on, pp.498 501, 5-8 Aug. 2007.

  7. K.Babulu, and Y.Gowthami, Implementation and Performance Evaluation of Prefix Adders using FPGAs, IOSR Journal of VLSI and Signal Processing (IOSR-JVSP), Volume 1, Issue 1, pp.51-57, Sep-Oct. 2012.

  8. Sreenivaas Muthyala Sudhakar, Kumar P. Chidambaram, and Earl E. Swartzlander, Hybrid Han-Carlson adder, Circuits and Systems (MWSCAS), 2012 IEEE 55th International Midwest Symposium on, pp.818 821, 5-8 Aug. 2012.

One thought on “High Performance Vedic Multiplier Using Han-Carlson Adder

Leave a Reply

Your email address will not be published. Required fields are marked *