Design And Analysis of Area Efficient Wallace Tree Multiplier using Approximate 4:2 Compressor and Kogge Stone Adder

Design And Analysis of Area Efficient Wallace Tree Multiplier using Approximate 4:2 Compressor and Kogge Stone Adder

Hafsa

M.Tech VLSI Design, Dept. of ECE IES College of Engineering Thrissur, Kerala

Aksa David

Asst. Professor, Dept of ECE IES College of Engineering Thrissur, kerala

Abstract Over the years, the complexity of VLSI design circuits has increased dramatically. With this improvement, there comes the need for low area and high speed VLSI circuits. The common known fact is that multiplier circuit plays an important role in the digital processor design. Nowadays, low area and high speed multiplier designs are in high demand. Compared to other multipliers, Wallace tree multipliers are considered to be fast rather than other multipliers. It is found out that it reduces the area compared to normal Wallace Tree Multiplier Design. Here, another method for Approximate Wallace multiplier using 4:2 compressors is proposed to keep the area overhead minimal. Also in order to improve the speed of Wallace tree multiplier without degrading its area parameter, a new structure of Wallace tree multiplier is proposed in this paper. In the proposed structure, the final addition stage of partial products is performed by parallel prefix adders (PPAs). In this paper, five Wallace tree multiplier structures are proposed using Kogge stone adder, Sklansky adder, Brent Kung adder, Ladner Fischer adder and Han carlson adder. All the multiplier structures are designed using Verilog HDL in Xilinix

1. design suite. The proposed structures are simulated using ISIM simulator and synthesized using XST synthesizer. The proposed designs are analyzed with respect to traditional multiplier design in terms of area (No. of LUTs) and delay (ns).

   Keywords Wallace tree multiplier, Parallel Prefix adders(PPAs), Kogge Stone adder, Sklansky adder, Brent-Kung adder, Ladner Fischer adder, Han Carlson adder and 4:2 compressors

   1. INTRODUCTION

      At present, the technology is advancing very rapidly in very short duration of time. The circuits being design have some billions of components with low area, high speed and low power consumption. Hence area, speed and power plays crucial role in the design of any circuit. In order to satisfy the current trend demand a circuit must be designed with low area and less delay constraints. Arithmetic units are major blocks in any processing units which perform various arithmetic operations. Multiplication operation is important among all arithmetic operations. Several multiplication algorithms are present such as Binary multiplier, array multiplier, Booths multiplier, Dadda multiplier, Wallace tree multiplier. Wallace tree multiplier is advantageous in different types of multipliers.

      A Wallace multiplier is a hardware implementation of binary multiplier, a digital circuit that multiplies two integers. It uses a selection of full adders and half adders to sum partial

      products in stages until two numbers are left. Wallace multipliers reduce as much as possible on each layer, whereas Dadda multipliers try to minimize the required number of gates by postponing the reduction to the upper layers. Operation of WTM is same as the first stage of multiplication and it generates the partial product. In traditional modal half adders and full adders are used for the reduction of partial products. It adds the first three rows of partial product. Then generated sum and carry is added with next row of partial products. This process continues until the final stage which have only two rows of sum and carry. Final stage is also reduced by adders like carry look ahead adder, carry select adder parallel prefix etc. thus adders plays a important role in the generation of final product terms. The speed of addition is going to effect the operation of the multiplication.

      In order to increase the performance of multiplication operation, the adders structure used in WTM has a major role. In this paper, a new structure of WTM is designed using 4:2 compressors for the reduction of partial products and PPAs are used to add the final row of partial products with the previous stage of generated sum and carry which gives final product terms. The PPAs are originated from carry look ahead adder concept of generating and propagating carry bits.

      In PPAs, a carry generation tree is present which generates carry for all preceding stages which improves the speed of operation. The carry generation tree mainly consists of two components-black cell and grey cell. The black cell and grey cell are interconnected to from carry tree network. Carry generation tree block is also called as parallel carry generation block as it generates carry bits for all stages at a time parallel. There are different types of PPAs whose classification mainly depends on two factors-

      1. Number of black and grey cells in carry generation tree.

      2. Interconnection of black and grey cells in carry generation tree.

      Kogge stone adder, Sklansky adder, Brent-Kung adder, Ladner-Fischer adder and Han Carlson adder are some of the PPAs used in the design of proposed Wallace tree multiplier in this paper.

   2. EXISTING TECHNOLOGY

1. WALLACE TREE MULTIPLIER

   Multipliers plays a important role in processing unit. There are many multiplication algorithms are being used for the design of multiplier. This multiplier should satisfy some parameter like area, speed and power consumption. WTM are most extensively used multiplier design in many processor and memory units. A Wallace multiplier is a hardware implementation of binary multiplier, a digital circuit that multiplies two integers. It uses a selection of full adders and half adders to sum partial products in stages until two numbers are left. Wallace multipliers reduce as much as possible on each layer, whereas Dadda multipliers try to minimize the required number of gates by postponing the reduction to the upper layers. Operation of WTM is same as the first stage of multiplication and it generates the partial product. In traditional modal half adders and full adders are used for the reduction of partial products. It adds the first three rows of partial product. Then generated sum and carry is added with next row of partial products. This process continues until the final stage which have only two rows of sum and carry. Final stage is also reduced by adders like carry look ahead adder, carry select adder parallel prefix etc. thus adders plays a important role in the generation of final product terms. The speed of addition is going to effect the operation of the multiplication.

   Figure 1: WTM Block Diagram

   Figure 1: shows the basic block diagram for WTM, 16 bit integer perform AND and generates partial products which reduced and final round performed by PPAs. In detailed multiplication process of Wallace tree multiplier is explained through Figure 2: for input size of 4-bits.

   Figure 2: 4 bit multiplication in WTM

   Above figure shows the multiplication in WTM for 4 bit number A0-A3 and B0-B3 are the multiplicant. After AND operation we get partial products. This partial products are reduced by half adders and full adders. During phase 1, first three rows are added and we get the sum and carry, which added with last row until it become two rows with first row sum and second row carry. Here PS is partial product sum and PC is the partial product carry. Finally the last two rows can be reduced to get final product

   In entire process of multiplication, addition process holds major role. To perform fast addition, carry must be propagated quicly. A Wallace tree multiplier using Carry select adder designed. But, carry propagation delay is more in this existing methodology which is the major drawback. To prevail over this drawback, Parallel prefix adders are used in place of half and full adders in final stage of addition in phase 2 of this multiplier. The main motivation of this proposed design is to achieve Wallace tree multiplier architecture with high speed than the existing designs.

   Figure 3: Dot representation of 8 bit multiplication in WTM

   Figure 3: shows the dot representation of 8 bit multiplication in Wallace tree multiplier. Here there 4 stages for partial product reduction. Final stage is added using PPAs. As bit increases the number of stages also increases

2. PARALLEL PREFIX ADDER

   parallel prefix adders (PPA) are considered effective combinational circuits for performing the binary addition of two multi-bit numbers. These adders are widely used in arithmetic-logic units, which are parts of modern processors, such as microprocessors, digital signal processors,etc. To avoid the higher delay problem of existing carry adders the PPA is used which is simply the modified design form of CLA. The Prefix adders can be designed in many different ways based on the different requirements and the production of carries. Recently, use the tree structure form of adders to raise the speed of addition function in any kind of processors. PPA are fastest adders with tree structure based and used for high performance arithmetic processes in successive industries and DSP laboratories. The PPAs are also called as logarithmic delay adders because the delay value is established using logarithmic functions. Addition in PPA can be processed using three main actions as shown in figure 4: Pre-computation (P and G signal generation). Signals are generated by

   Pi = A XOR B [1]

   Gi = A AND B [2]

   Where A and B are input bits. Prefix computation (carry signals group generation), generates carry bits for all inputs with the help of black cell and grey cell which uses some logical operations for the generation. Post-computation (Sum signal generation), is sum generation block used to generate sum by performing XOR operation of propagate signal and carry signal generated from the block 2 i.e,

   Si = Pi XOR Ci-1 [3]

   Figure 4:PPA block diagram

   There are different types of PPAs whose classification mainly depends on two factors-

   1. Number of black and grey cells in carry generation tree

   2. Interconnection of black and grey cells in carry generation tree.

      • Types of PPAs

      Name of PPA	Delay (ns)	Area	No: of black cell	No: of grey cell
      Kogge stone adder	less	Large	34	15
      Sklansky adder	More than KSA	less	17	15
      Brent Kung adder	More than than KSA and BKA	Less	12	15
      Ladner Fischer adder	Less than BKA	Less	12	15
      Han Carlson adder	More than SA	Slightly less than KSA	17	15

      Table 1: Types of PPAs and their specification

      	WTM using KSA	WTM using SA	WTM using BKA	WTM using LF	WTM using HCA
      Slice LUTs	151	141	140	139	141
      Occupied Slices	50	50	52	52	62
      IOBs	32	32	32	32	32
      Delay (ns)	20.896	23.177	21.051	22.125	21.955
      Power (mW)	14	14	14	14	14

      Table 2: Comparison of 8 bit WTM using PPAs

      Table 1 specification of Wallace tree multiplier using five parallel prefix adder such as KSA, SA, BKA, LF and HCA. Table 2 shows the comparison of 8 bit WTM using the PPAs. The delay of parallel prefix adder is directly proportional to the number of level in the carry propagation stage. The synthesis report consists of delay in terms of nano seconds.and area details in terms of number of LUTs occupied. From table 1, it can be seen that Wallace tree multiplier using Kogge stone adder is having least delay but it has more number of LUTs occupied when compared to other structures.

   3. PROPOSED TECHNOLOGY

      In traditional Wallace tree multiplier full adders and half adders are used for the reduction of partial products. For a 16 bit WTM use more number of full adders and half adders which consumes large area. In proposed modal a new method is implemented to reduce the area by using 4:2 compressors for the reduction of partial products. Compressors have been considered as the most efficient building blocks of a high speed multiplier. It provides an advantage of accumulation of partial products at an expense of least possible power dissipation. From the analysis made at the previous section shows that Kogge stone adder has better delay. Hence we Kogge stone adder in final stage to get the final product.

      There are two types of compressors, exact compressor and approximate compressor. For exact compressor there are many error, so we mainly use approximate compressor.

      Figure 5 shows a 4:2 compressor

      Figure 5: 4:2 compressor

      There are several design for the the implementation of compressor. But by using some of the design there we get some error during computation. Hence we use a design which gives less error comparing with other design. In this out of 16 outcomes, 2 of them gives error. So while we use it for higher application it can be neglected. Figure 6 shows the internal circuit diagram for 4:2 compressor

      Figure 6: Implementation of 4:2 compressor

      K

      Figure 7: Block diagram of proemposed system

   4. SIMULATED RESULT

      Fig.8 shows the final simulation result of a Wallace tree multiplier using 4:2 compressor and Kogge Stone Adder is used for final partial product reduction

      Fig.8: Simulated result for WTM using 4:2 compressor and Kogge Stone Adder

   5. CONCLUSION

      Verified five parallel prefix adders in terms of area and delay. Area details in terms of number of LUTs occupied and delay in terms of nano seconds. From table 2, it can be seen that Wallace tree multiplier using Kogge stone adder is having least delay but it has more number of LUTs occupied when compared to other structures, Ladner Fischer has least area. For the application where speed is main concern we can use Kogge Stone adder. In the proposed system Wallace tree multiplier using 4:2 compressors and Kogge stone adder is implemented

   6. REFERENCES

[1] R. Bala Sai Kesava, K. Bala Sindhuri, B. Lingeswara rao, N. Udaya Kumar, Low Power And Area Efficient Wallace Tree Multiplier Using Carry Select Adder With Binary To Excess-1 Converter

[2] Rakesh S, K. S. Vijula Gracea, A comprehensive review on the VLSI design performance of different Parallel Prefix Adders

[3] Jasmine Saini and Somya Agarwal, Aditi Kansal, Performance, Analysis and Comparison of Digital Adders

[4] Kokila Bharti Jaiswal, Nithish Kumar V, Pavithra Seshadri and Lakshminarayanan G, Low Power Wallace Tree Multiplier Using Modified Full Adder

[5] Dhaval R Gandhi, Nehal N Shah, Comparative Analysis For Hardware Circuit Architecture Of Wallace Tree Mltiplier

[6] T. Arunachalam and S. Kirubaveni, Analysis of High Speed Multipliers

[7] Mr. Deepak Raj, Mrs.Sahana K Adyanthaya, Prof. Praveen J, Prof. Raghavengra Rao R, Design and Implementation of different types of efficient parallel prefix adders

[8] Priyanka Mishra, Seema Nayak, A Study on Wallace Tree Multiplier

[9] Shilpa K. C, Shwetha M, Geetha B. C, Lohitha D. M, Navya, Pramod

N. V, Performance Analysis Of Parallel Prefix Adder For Datapath VLSI Design

[10] S. Sowmiya, K. Stella, and V.M.Senthilkumar, Design and analysis of 4:2 compressor for arithmetic application

[11] Sri Laxmi.P, B. Kumar Sanjiv, Vandana Khare, Design and Comparison of Different 4:2 Compressors Based on 180nm Technology

[12] Chandrakala, A. Sreeramulu L. Srinivas, Design and Implementation of 4-2 Compressor Design with New Xor-Xnor

[13] Antonio Giuseppe Maria Strollo, Ettore Napoli, Davide De Caro, Nicola Petra and Gennaro Di Meo, Comparison and Extension of Approximate 4-2 Compressor for Low-Power Approximate Multipliers

[14] A.Sundhar, S.Deva tharshini, G.Priyanka, S.Ragul and C.Saranya, Performance Analysis of Wallace Tree Multiplier with Kogge Stone Adder using 15-4Compressor