International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 1

ISSN 2229-5518

Design of High Speed Vedic Square by using Vedic Multiplication Techniques

G.Ganesh Kumar*, C. Venkata Sudhakar**, M.Naresh Babu***

Department of Electronics & Communication Engineering, SVEC, Tirupati, Andhra Pradesh-517102 India.

Email_Id : ggkumar1988@gmail.com*, sudhakar.chowdam@gmail.com**,manchunareshbabu@gmail.com ***

Abstract— Digital signal processors (DSPs) are very important in various engineering disciplines. Faster additions and multiplications are of extreme importance in DSP for convolution, discrete Fourier transforms, digital filters,etc. As in all the arithmetic operations, it is the squaring which is most important in finding the transforms or the inverse transforms in signal processing. The squaring operation occupies most of the computing time, therefore it is necessary to concentrate on the improvement of speed with which. Urdhava Triyakbhyam algorithm of ancient Indian Vedic Mathematics is utilized to improve its efficiency. This is a highly modular design in which smaller blocks can be used to build higher blocks. Vedic square is designed by using Verilog HDL coding and compared the performance with the modified Wallace tree in terms of time delay and area occupied on the Xilinx Spartan xc3s500e-5fg320.

Index Terms— Delay, Karatsuba – Ofman algorithm, Urdhva Triyakbhyam Sutra, Vedic Mathematics, Vedic Square, Wallace tree, Xilinx Spartan.

1 INTRODUCTION

he demand for high speed processing has been increasing as a result of expanding computer and digital signal processing applications. Higher throughput arithmetic operations are important to achieve the desired performance in many real-time signal and image processing applications. The key arithmetic operations in such applications are multiplication and squaring. Since multiplication and squaring dominates the execution time of most DSP algorithms, so there is a need of high speed multiplier and a squaring of a number. Minimizing power consumption for digital systems involves optimization at all levels of the design. This optimization includes the technology used to implement the digital circuits, the circuit style and topology, the architecture for implementing the circuits and at the highest level the
algorithms that are being implemented.

2 VEDIC MATHEMATICS

Vedic mathematics is part of four Vedas (books of wisdom). It is part of Sthapatya- Veda (book on civil engineering and architecture), which is an upa-veda (supplement) of Atharva Veda. It gives explanation of several mathematical terms including arithmetic, geometry (plane, co- ordinate), trigonometry, quadratic equations, factorization and even calculus.
His Holiness Jagadguru Shankaracharya Bharati Krishna Teerthaji Maharaja (1884- 1960) comprised all this work together and gave its mathematical explanation while discussing it for
various applications. Vedic maths deals with several basic as well as complex mathematical operations. Especially, methods of basic arithmetic are extremely simple and powerful [2, 3].
The word “Vedic” is derived from the word “Veda” which means the store-house of all knowledge. Vedic mathematics is mainly based on
16 Sutras (or aphorisms) dealing with various branches of mathematics like arithmetic, algebra, geometry etc. These Sutras along with their brief meanings are enlisted below alphabetically.
1) (Anurupye) Shunyamanyat – If one is in ratio, the other is zero.
2) Chalana-Kalanabyham – Differences and
Similarities.
3) Ekadhikina Purvena – By one more than the
previous One.
4) Ekanyunena Purvena – By one less than the
previous one.
5) Gunakasamuchyah – The factors of the sum is
equal to the sum of the factors.
6) Gunitasamuchyah – The product of the sum is
equal to the sum of the product.
7) Nikhilam Navatashcaramam Dashatah – All
from 9 and last from 10.
8) Paraavartya Yojayet – Transpose and adjust.
9) Puranapuranabyham – By the completion or
noncompletion.
10) Sankalana- vyavakalanabhyam – By addition
and by subtraction.
11) Shesanyankena Charamena – The remainders
by the last digit.
12) Shunyam Saamyasamuccaye – When the sum
is the same that sum is zero.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 2

ISSN 2229-5518

13) Sopaantyadvayamantyam – The ultimate and twice the penultimate.
14) Urdhva-tiryagbhyam – Vertically and crosswise.
15) Vyashtisamanstih – Part and Whole.
16) Yaavadunam – Whatever the extent of its
deficiency.
These methods and ideas can be directly applied to trigonometry, plain and spherical geometry, conics, calculus (both differential and integral), and applied mathematics of various kinds. [ 1,4].

.

3 Design of Vedic Square

Urdhva – Triyagbhyam(Vertically and Crosswise): Urdhva tiryakbhyam Sutra is a general multiplication formula applicable to all cases of multiplication. It literally means “Vertically and Crosswise

An alternative method of multiplication using Urdhva tiryakbhyam Sutra is shown in Fig.

1. The numbers to be multiplied are written on two consecutive sides of the square as shown in the figure. The square is divided into rows and columns where each row/column corresponds to one of the digit of either a multiplier or a multiplicand. These small boxes are partitioned into two halves by the crosswise lines. Each digit of the multiplier is then independently multiplied with every digit of the multiplicand and the two- digit product is written in the common box. All the digits lying on a crosswise dotted line are added to the previous carry. The least significant digit of the obtained number acts as the result digit and the rest as the carry for the next step. Carry for the first step (i.e., the dotted line on the extreme right side) is taken to be zero.

Fig. 1. Alternative way of multiplication by Urdhva tiryakbhyam Sutra.

The design starts first with Multiplier design, that is 2x2 bit square multiplier as shown in figure

2. Here, “Urdhva Tiryakbhyam Sutra” or “Vertically and Crosswise Algorithm”[4] for multiplication has been effectively used to develop digital multiplier architecture. This algorithm is quite different from the traditional method of multiplication, that is to add and shift the partial products.

Fig. 2. Hardware Realization of 2x2 block square multiplier

To scale the multiplier further, Karatsuba – Ofman algorithm can be employed[6]. Karatsuba- Ofman algorithm is considered as one of the fastest ways to multiply long integers. It is based on the divide and conquer strategy[6]. A multiplication of
2n digit integer is reduced to two n digit multiplications, one (n+1) digit multiplication, two n digit subtractions, two left shift operations, two n digit additions and two 2n digit additions.

The algorithm can be explained as follows: Let X and Y are the binary representation of two long integers:
We wish to compute the product XY. Using the divide and conquer strategy, the operands X and Y can be decomposed into equal size parts XH and XL, YH and YL, where subscripts H and L represent high and low order bits of X and Y respectively.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 3

ISSN 2229-5518

The product XY can be computed as follows:

Fig. 4(c). 32 Bit Vedic Square

For 32 bit vedic square, first the basic blocks, that are the 2x2 bit multipliers have been made and then, using these blocks, 4x4 block has been made by adding the partial products using carry save adders and then using this 4x4 block, 8x8 bit block,
16x16 bit block and then finally 32 x 32 bit Vedic
Square as shown in figure 3 has been made.

Fig. 3. 32X32 Bits Vedic Square

4 IMPLEMENTATION OF VEDIC SQUARE

The proposed Vedic Square implemented using two different coding techniques viz., conventional shift & add and Vedic technique for 8, 16, and 32 bit vedic squares. It is evident that there is a considerable increase in speed of the Vedic architecture. The simulation results for 8, 16, and
32 bit vedic squares are shown in the figures 4.(a), (b), (c) respectively.

Simulation Results:

Fig. 4(a). 8 Bit Vedic Square

Fig. 4(b). 16 Bit Vedic Square

Synthesis Results:

Selected Device: 3s500efg320-5

Table 1.Comparison of Delays
The worst case propagation delay in the Vedic Square case was found to be 31.526ns. To compare it with other implementations the design was synthesized on XILINX: SPARTAN: xc3s500e-
5fg320[13]. Table 1 shows the synthesis result for various implementations. The result obtained from proposed Vedic Square is faster than Wallace Tree.

.

5 CONCLUSION

The designs of 32x32 bits Vedic Square have been implemented on Spartan XC3S500-5-FG320. The design is based on Vedic method of multiplication [3]. The worst case propagation delay in the Vedic Square case is 31.526ns. It is therefore seen that the Vedic Square are much more faster than the Wallace Tree. This gives us method for hierarchical square design. So the design complexity gets reduced for inputs of large no of bits and modularity gets increased. Urdhva tiryakbhyam algorithm which can reduce the delay, power and hardware requirements for square of numbers. FPGA implementation of this multiplier shows that hardware realization of the Vedic mathematics algorithms is easily possible. The high speed square algorithm exhibits improved efficiency in terms of speed.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 4

ISSN 2229-5518

REFERENCES

[1] 1964Booth, A.D., “A signed binary multiplication technique,” Quarterly Journal of Mechanics and Applied Mathematics, vol. 4, pt. 2, pp. 236– 240, 1951.

[2] Wallace, C.S., “A suggestion for a fast multiplier,” IEEE Trans.

Elec. Comput., vol. EC-13, no. 1, pp. 14–17, Feb.

[3] A.P. Nicholas, K.R Williams, J. Pickles, “Application of Urdhava

Sutra”, Spiritual Study Group, Roorkee (India),1984. [4] Jagadguru Swami Sri Bharath, Krsna Tirathji, “Vedic

Mathematics or Sixteen Simple Sutras From The Vedas”, Motilal

Banarsidas, Varanasi(India),1986.

[5] Neil H.E Weste, David Harris, Ayan anerjee,”CMOS VLSI Design, A Circuits and Systems Perspective”,Third Edition, Published by Person Education, PP-327-328]

[6] D. Zuras, On squaring and multiplying large integers, In Proceedings of International Symposium on Computer Arithmetic, IEEE Computer Society Press, pp. 260-271, 1993.

[7] S.G. Dani, Vedic Maths’: facts and myths, One India One

People, Vol 4/6,January 2001, pp. 20-21; (available on www.math.tifr.res.in/ dani).

[8] Thapliyal H. and Srinivas M.B. “High Speed Efficient N x N Bit

Parallel Hierarchical Overlay Multiplier Architecture Based on Ancient Indian Vedic Mathematics”, Transactions on Engineering, Computing and Technology, 2004, Vol.2.

[9] 2008Shripad Kulkarni, “Discrete Fourier Transform (DFT) by using Vedic Mathematics”Papers on implementation of DSP algorithms/VLSI structures using Vedic Mathematics, 2006, www.edaindia.com, IC Design portal.

[10] Mrs. M. Ramalatha, Prof. D. Sridharan, “VLSI Based High Speed

Karatsuba Multiplier for Cryptographic Applications Using Vedic

Mathematics”, IJSCI, 2007.

[11] “Lifting Scheme Discrete Wavelet Transform Using Vertical and

Crosswise Multipliers” Anthony O’Brien and Richard Conway, ISSC, 2008,Galway, June 18-19.

[12] “A Reduced-Bit Multiplication Algorithm For Digital Arithmetic”

Harpreet Singh Dhilon And Abhijit Mitra, International Journal of Computational and Mathematical Sciences, Waset, Spring.

[13] www.xilinx.com

IJSER © 2013 http://www.ijser.org