Implementation Of High Speed Pipelined Vedic Multiplier

Implementation Of High Speed Pipelined Vedic Multiplier

Prakash Pawar1, Varun. R2, Suma M. S3.

1,2 M.Tech in VLSI Design and Embedded System, 3Assistant Professor Department of ECE, R .V College of Engineering, Bangalore, India.

ABSTRACT

This paper deals with the pipelined architecture of Vedic multiplier, where Vedic mathematics[1] is an ancient technique with unique approach and it has got different sutras. Here, in this paper Urdhva-Tiryakbhyam(U-T) Sutra is been discussed , which is efficient in area and speed of the multiplier. To raise the speed of the multiplier we have implemented pipelined architecture where registers are introduced in between the stages. Finally, the delay comparison of Vedic U-T is done with pipelined Vedic U-T and improvement in the speed of the multiplier is observed. The model is simulated using Xilinx ISE 13.1Version tool and synthesized using cadence RTL compiler.

Keywords

Vedic mathematics, U-T Sutra, pipeline architecture.

1. INTRODUCTION

   Multiplier plays an important role in Digital signal processing (DSP) applications such as ALU, MAC [5] and Image processing systems, higher throughput of Arithmetic operation are important for real time applications and thus it is necessary to move towards optimization technique and raise the speed of the multiplier. Vedic mathematics [1] is an ancient technique which was used in the time of Vedas. It has got as many as 12 Sutras that can be used for different Arithmetic calculation. Since The ever growing technology and increased complexity in the design demands for the optimized area and delay. Researchers are constantly working on towards the designing of optimized multiplier architecture. Critical path delay is the key factor in determining the speed of the multiplier, In simpler form multiplication can be developed using successive addition, subtraction and shifting operation as in literature. Different algorithms are implemented for the multiplier and each technique has got its own advantage and trade off in terms speed, area, and power consumption.

   Multipliers are the core component of any DSP applications and hence speed of the processor largely depends on multiplier architecture. A multiplier of size n bits has n2 gates. For multiplication algorithms performed in DSP applications latency and throughput are the two major concerns.

   In this paper Urdhva-Tiryakbhyam(U-T) Sutra is applied to binary number system and can be used to design efficient digital multiplier architecture. Furthermore, pipelining concept [6] can be applied to multiplier architecture to raise the speed. Depending on the number of adders used in partial products addition, registers can be used for the blocks of combinational logic and care should be taken that minimum number of registers should be used to avoid area overhead.

2. URDHVA-TIRYAKBHYAM Sutra

   Fig.1 Line Diagram for Urdhva- Tiryakbhyam Sutra.

   To illustrate an example for the above sutra we will consider the vertical and crosswise multiplication of two binary numbers a3a2a1a0 as a multiplicand and b3b2b1b0 as a multiplier, multiplication of two n-bit numbers would result in product of 2n-bit ,each stage of

   operation can be shown by a line diagram representation Fig.1, in every steps LSB bit of sum is stored in product and higher bits considered to be carry bits for next stage operation these operation are shown by the expression P0,P1,P7 final result is obtained by concatenating the bits of all steps. From convention multiplier all partial products are calculated in parallel and shifting of partial product is eliminated in case of Urdhva-Tiryakbhyam sutra and hence it is more efficient.

   The above line diagram representation of Vedic Multiplier Fig.1 is implemented using equations shown below with operands X and Y.

   X=a3a2a1a0 Y=b3b2b1b0.

   P0 = a0.b0.

   P1= a1.b0 +a0.b1.

   P2 = a2.b0+a1.b1+a0.b2+P1[1].

   P3 = a3.b0+a2.b1+a1.b2+a0.b3+P2[2:1]. P4 = a3.b1+a2.b2+a1.b3+P3[2:1].

   P5 = a3.b2+a2.b3+P4[2:1]. P6 = a3.b3+P5[2:1].

   P7 = p6[2:1].

   P= P[0]&P[1]&P[2]&P[3]&P[4]&P[5]& P[6] & P[7].

   Further 8-bit multiplier can be implemented using 4-bit multiplier blocks, In general 2n-bit multiplier can be implemented using n-bit blocks [8].

3. Proposed Pipelined Architecture

   The Urdhva-Tiryakbhyam Sutra discussed above is implemented using pipelined architecture to raise the speed of the multiplier.

   Fig.2 Block Diagram of Pipelined Architecture

   Register

   a3 b3 a3 b3 a2 b3 a3 b1 a2 b2 a1 b3 a3 b0 a2 b1 a1 b2 a0 b3 a2 b0 a1 b1 a0 b2 a1 b0 a0 b1 a0 b0

   FA 4-bit adder 4-bit adder 5-bit adder 4-bit adder HA

   2

   2

   2

   2 2

   P7, P6 P5 P4 P3 P2 P1 P0

   Fig.3 Hardware architecture of Pipelined Vedic multiplier.

   From Fig.1 the number of adders in each step is known and depending on number of adders 4-stages of pipeline operation is done to reduce the critical path delay, more number of stages used may increase the speed further but leads to area overhead, hence minimum number of registers are preferred. The partition of four different stages are shown in Fig.2 with a block diagram .

   In Fig.3 use of registers is shown with the following stages as discussed. In this proposed model 4-stage pipelining architecture is used at the first cycle of the clock, input of the 1st stage are processed and obtained result is kept in 1st level register , simultaneously other stage inputs are fed to1st level registers. At the second cycle of the clock 2nd stage inputs are processed, and the obtained results are placed in 2nd level registers and simultaneously next stage inputs are fed to 2nd level registers At the 3rd clock cycle, 3rd stage inputs are processed and obtained results are placed in 3rd level registers and simultaneously next stage inputs are fed into 3rd level registers. At the 4th clock cycle, 4th stage inputs are processed and obtained results are placed in 4th level registers.

   Finally, the output results are obtained after 4th clock cycle. In the same way 2nd data operand are processed with one stage lagging and hence after 5th clock cycle, output of 2nd data operands are obtained.

4. Implementation and Simulation Results

   The Vedic multiplier using Urdhva-Tiryakbhyam and proposed pipelined Vedic multiplier is designed and implemented using Verilog code. These models are Simulated using Xilinx 13.1 ISE simulator and Synthesized using Cadence RTL Encounter 180nm tool.

   The Simulation [A],[B],[C],[D] shows the output results for a 4-bit Vedic multiplier, 32-bit Vedic multiplier ,4- bit pipelined Vedic multiplier and 32-bit pipelined Vedic multiplier respectively.

   For 4-bit Pipelined Vedic multiplier it is observed that output of 1st data input is obtained after 4th clock cycle, after 5th clock cycle output of next data inputs and so on. For a 32-bit Pipelined Vedic multiplier, output is obtained after 7th clock cycle since 7-stages of pipelining is used for 32-bit multiplier.

   1. 4-bit Vedic Multiplier.

   2. 32-bit Vedic Multiplier.

   3. 4-bit Pipelined Vedic Multiplier.

   4. 32-bit Pipelined Vedic Multiplier.

   Delay Comparison

   Table.1 shows the delay comparisons between different Vedic multiplirs viz, the Shift and Add multiplier, Vedic multiplier and proposed Pipelined Vedic multiplier models.

   Table.1

   Delay(ns) Comparison Table
   	4-bit	8-bit	16-bit	32-bit
   Shift & Add Multiplier	4.638	12.580	27.034	53.098
   Vedic Multiplier	3.010	8.822	21.025	45.419
   Proposed Pipelined Vedic Multiplier	1.953	5.745	9.543	13.343

   The results shown in Table.1 are obtained using Cadence RTL compiler tool. Fig.4 and Fig.5 shows the critical path delay of Vedic Multiplier and proposed model. From the Table.1 above, it can be clearly inferred that proposed Pipelined Vedic Multiplier proves to be more efficient in terms of speed compared to Vedic Multiplier. Hence, the proposed model works as a high Speed multiplier. Fig.6 shows delay comparison chart between different multipliers.

   Fig.4 Critical path Delay of 4-bit Vedic Multiplier.

   Fig.5 Critical Path Delay of 4-bit Pipelined Vedic Multiplier.

   Delay

   (ns) 60

   50

   Shift & Add Multiplier

   Vedic Multplier

   Pipelined Vedic Multiplier

   Delay

   (ns) 60

   50

   Shift & Add Multiplier

   Vedic Multplier

   Pipelined Vedic Multiplier

   40

   30

   20

   10

   0

   40

   30

   20

   10

   0

   4-bit 8-bit 16-bit 32-bit

   4-bit 8-bit 16-bit 32-bit

   Fig.6 Delay Comparison Chart.

5. CONCLUSION

   In the paper proposed, a 32-bit Pipelined Vedic multiplier Architecture is designed and it proved to be more efficient in terms of speed compared to conventional Vedic Multiplier using Urdhva- Tiryakbhyam sutra . This approach is well suited for applications, where high speed multipliers are required. Hence proposed design can be efficiently used in MAC units and DSP operations to raise the performance of the system in terms of speed.

6. REFERENCES

1. Jagadguru Swami Sri Bharati Krisna Tirthaji Maharaja, Vedic Mathematics: Sixteen Simple Mathematical Formulae from the Veda, Delhi (1965).

2. H.C. Chow and I.C. Wey, A 3.3V 1GHz high speed pipe-lined Booth multiplier, Proc. of IEEE ISCAS, vol. 1, pp. 457-460, May. 2002.

3. Himanshu Thapliyal, Vedic Mathematics for Faster Mental Calculations and High Speed VLSI Arithmetic, Invited talk at IEEE Computer Society Student Chapter, University of South Florida, Tampa, FL, Nov 14 2008.

4. P. Ramanathan, P.T. Vanathi, and S. Agarwal, High Speed Multiplier Design Using Decomposition Logic, Serbian Journal of Electrical Engineering, vol. 6, no. 1,pp. 33-42, May 2009.

5. Devika, K. Sethi and R.Panda, Vedic Mathematics Based Multiply Accumulate Unit, 2011 International Conference on Computational Intelligence and Communication Systems, CICN 2011, pp.754-757, Nov. 2011.

6. Q. LI, G. LIANG, and A. BERMAK, A High-speed 32-bit Signed/Unsigned Pipelined Multiplier, IEEE 5th Int. Sym-posium Electronic Design, Test and Application, pp.207- 211, Jan. 2010.

7. S.S.Kerur, Prakash.Narchi,Jayashree.C.N,Harish.M. Kittur and Girish.V.A, Implementation of Vedic Multiplier for Digital Signal Processing International Conference on VLSI, Communication & Instrumentation (ICVCI) 2011, Proceedings published by International Journal of Computer Applications® (IJCA).

8. Abhishek GuptaImplementation of Vedic Multiplier for Digital Signa Processing International Journal of Engineering and Innovative Technology (IJEIT) Volume 1, Issue 5, May 2012. ISSN: 2277-3754.