High Performance Vedic Multiplier Using Han-Carlson Adder

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.