A High Speed and Device Efficient, FPGA
Based Squaring Circuit

SHUBHAM MISHRA; SHAILENDRA KUMAR DHAKAD

A High Speed and Device Efficient, FPGA Based Squaring Circuit

SHUBHAM MISHRA¹ and SHAILENDRA KUMAR DHAKAD²

B.E(HONS), Dept. of EI ,BITS PILANI UNIVERSITY ,GOA,INDIA
LECTURER, Dept. of EEE &I, BITS PILANI UNIVERSITY, GOA ,INDIA

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Abstract

In this paper a high speed squaring circuit for binary numbers is proposed. The methodology used is inspired from ancient Egyptian method of multiplication. Implementation of this method to binary squaring can increase speed and would improve the device utilization .It was found that the architecture targeted for Xilinx Virtex-4 FPGA( xc4vlx80- 12) used 52 , 4-input LUTS with a combinational delay of 14.972 ns for 32 bit squaring.

Keywords

Squaring Algorithm, FPGA(field-programmable gate array), VHDL,VLSI Design, Peasant multiplication .

INTRODUCTION

Since squaring is one of the fundamental operations widely used in digital signal processing algorithms, a high-speed and highly efficient squaring methodology is proposed. We present a simple way of squaring which is inspired from Peasants method (old Egyptian technique for multiplication)[6]. the main motivation behind this work is to investigate the VLSI Design and Implementation of Squaring Circuit architecture with reduced delay and improved device utilisation .

In mathematics, ancient Egyptian multiplication(also known as Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or peasant multiplication)[6], one of two multiplication methods used by scribes, was a systematic method for multiplying two numbers that does not require the multiplication table, only the ability to multiply and divide by 2, and to add. It decomposes one of the multiplicands (generally the larger) into a sum of powers of two and creates a table of doubling of the second multiplicand. This method may be called mediation and duplation, where mediation means halving one number and duplation means doubling the other number. It is still used in some areas.

THE MULTIPLIER ARCHITECTURE

In this section, we propose an efficient algorithm[6] which can be implemented for fast squaring calculations of binary numbers.

The algorithm used is peasants multiplication method , which is explained below

Take two numbers say A and B , to compute A*B through peasants method

(Rounding the numbers on left and right sections of the table)

MODIFICATION IN METHOD

The method can be modified in order to make it more efficient and hardware implementable .

In order to delete the row with even Left entry ,we can use the following method:-

1)Multiply each bit on the right in a particular row by the last bit (l.s.b) of the number of the same row.

2)Multiplying this bit will automatically cancel rather make all the elements of that row on the right as '0' if the number on left is even and otherwise would leave it as it is.

Example: let us take the same example 1101 * 11101110

HARDWARE IMPLEMENTATION

This method could be extended to square n bit numbers at a high-speed at high efficiency using logic gates.

A) Squaring a two bit number :

Let us take a two bit number msb( a(1) a(0) )lsb .Squaring this number by the above method can be described as:

D) General algorithm for a ' n ' bit number

The algorithm can be extended to an 'n' bit number . Where 0 is the lsb and n is its lsb.

To apply the generalised algorithm we need to understand following terms

• n denotes number of bits in the number which is to be squared.

• j = 2*n – 1

• S denotes the square of the input 'a' .

• S(k) denotes the k th term in S.

• 0 is assigned as the msb(most significant bit) of S.

• round off all the division values : if k= 7 , k/2=3

The terms in its square can be found by using just four generator terms

RESULTS

The modified high speed squaring algorithm design was simulated in Modelsim 6.6c [2]and synthesised using Xilinx ISE 12.2i [2] through VHDL[1] which was mapped on to Virtex-4 (xc4vlx80 -12) FPGA.

The results for device utilisation are placed in table 2. Table3 reflects the comparison between the proposed algorithm and the existing methodologies .

From the point of view of combinational delay the table 4 provides a comparison between the proposed algorithm and the existing architecture’s .

CONCLUSION

The modified high speed squaring algorithm was targeted on a Xilinx xc4vlx80-12-ff1148 FPGA.. The design achieved a high device utilisation with only 52 LUTS(4 input) for 32bit squaring . The implemented design is also efficient in terms of device utilisation and fast .The implementation verified that there was a delay of 14.972ns for 32 bit squaring which is far better than the existing vedic[7] squaring and booth squaring[4]. The idea proposed here may set path for future research in this direction. Future scope of research this is to reduce area requirements and can be extended to various fields of DSP.

Tables at a glance


Table 1	Table 2	Table 3	Table 4

References

V.A. Pedroni, “Circuit Design with VHDL,” 2008.

Xilinx(12.1) ISE User Manual’, Xilinx Inc, USA,April 19, 2010. ,

Prabha S., Kasliwal, B.P. Patil and D.K. Gautam, “Performance Evaluation of Squaring Operation by Vedic Mathematics”, IETE Journal of Research, vol.57, Issue 1, Jan-Feb 2011

B. Parhami, “Computer Arithmetic Algorithms and Hardware Architectures,” 2nd ed, Oxford University Press, New York, 2010.

Kai Hwang, “Computer Arithmetic: Principles, Architecture and Design,” New York: John Wiley & Sons, 1979.

http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication

“An Improved Squaring Circuit for Binary Numbers”(IJACSA) International Journal of Advanced Computer Science and Applications,Vol. 3, No.2, 2012

B. Jeevan,“A High Speed Binary Floating Point Multiplier Using Dadda Algorithm” ,pg. 1944 – 1947, vol.3 IEEE International Symposium on Circuits and Systems, 1997. ISCAS '97.