International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 756

ISSN 2229-5518

Design of Multiply and Accumulate Unit using

Vedic Multiplication Techniques

V.K.Karthik, Y.Govardhan, V.Karunakara Reddy, K.Praveena (Guide/Assistant Professor)

Abstract— This paper proposed the design of Multiply and Accumulate (MAC) Unit using the techniques of Ancient Indian Vedic Mathematics that have been modified to improve performance. The speed of MAC depends greatly on the multiplier. Vedic Mathematics is the ancient system of mathematics which has a unique technique of calculations based on 16 Sutras. The work has proved the efficiency of Urdhva Triyagbhyam– Vedic method for multi- plication which strikes a difference in the actual process of multiplication itself. It enables parallel generation of intermediate products, eliminates un- wanted multiplication steps with zeros and scaled to higher bit levels using Karatsuba algorithm with the compatibility to different data types. Multiply- Accumulate is an extensible block using the Vedic multiplier module plays an important role in computing, especially digital signal processing. The cod- ing is done in Verilog HDL and the FPGA synthesis is done using Xilinx Spartan library. The results show that design of MAC unit using Vedic multiplica- tion is efficient in terms of area/speed compared to conventional multiplication.

Index Terms— FPGA Synthesis, Karatsuba - Ofman algorithm, Urdhva Triyakbhyam Sutra, Vedic Mathematics, Verilog HDL, Vedic Multiplier, Wallac e

Tree.

1 INTRODUCTION

——————————  ——————————
HE Multipliers have an important effect in designing arithmetic, signal and image processors. Many manda- tory functions in such processors make use of multipli-

ers (for example, the basic building blocks in Fast Fourier transforms (FFTs) and multiply accumulate (MAC) are multipliers). The advanced digital processors now have fast bit-parallel multipliers embedded in them.

Various methods exist for the reduction in the compu- tation time involved by the multiplier with other factors as trade-offs. High-speed, bit-parallel multiplication can be classified into three types (a) shift-and-add multipliers that generate partial products sequentially and accumulate. This requires more hardware and is the slowest multiplier. This is basically the array multiplier making use of the clas- sical multiplying technique which consumes more time to perform two subtasks, addition and shifting of the bits and hence consumes 2 to 8 cycles of clock period. (b) generating all the partial product bits in parallel and accumulate them using a multi-operand adder. This is also called as parallel multiplier by using the techniques of Wallace tree [1] and Booth algorithm[2], (c) using arrays of almost identical cells for generation of bit products and accumulation.

The uses of Vedic Mathematics shows its application in fast calculations (multiplication, division, squaring, cubing, square root, cube root), trigonometry, three dimensional coordinate geometry, solution of plane and spherical trian- gles, linear and non-linear differential equations, matrices and determinants, log and exponential[15]. The most inter- esting point is to note that the Vedic Mathematics provides unique solutions in several instances where trial and error method is available at present.

————————————————

• V.K.Karthik is currently pursuing bhachelor degree program in Electronics

& control systems engineering inSree Vidyanikethan engineering college,

Tirupathi, A.P, India. PH-9963564573. E-mail:karthikvkk@gmail.com.

• Y.Govardhan and V.Karunakara Reddy is also currently pursuing

bhachelor degree program in Electronics & control systems engineering in

Sree Vidyanikethan engineering college, Tirupathi, A.P, India. E-mail:

govardhan2012@gmail.com, karunakarreddy7777@gmail.com.

Vedic Mathematics offers a fresh and highly efficient approach to mathematics covering a wide range - starts with elementary multiplication and concludes with a rela- tively advanced topic, the solution of non-linear partial differential equations. But the Vedic scheme is not simply a collection of rapid methods; it is a system, a unified ap- proach.

This paper proposes a multiplier providing the solu- tion of the aforesaid problems adopting the sutra of Vedic Mathematics called Urdhva Tiryakbhyam (Vertically and Cross wise)[3,4,5]. It can be shown that the design MAC unit is highly efficient in terms silicon area/speed.

2 VEDIC MATHEMATICS

Vedic mathematics is part of four Vedas (books of wisdom). It is part of Sthapatya- Veda (book on civil engineer- ing 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 cal- culus.
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. Swamiji constructed 16 sutras (formulae) and 16 Upa sutras (sub formulae) after ex- tensive research in Atharva Veda. Obviously these formulae are not to be found in present text of Atharva Veda because these formulae were constructed by Swamiji himself. Vedic mathematics is not only a mathematical wonder but also it is logical. That’s why it has such a degree of eminence which cannot be disapproved. Due these phenomenal characteristics, Vedic maths has already crossed the boundaries of India and has become an interesting topic of research abroad. Vedic maths deals with several basic as well as complex mathemati- cal operations. Especially, methods of basic arithmetic are ex- tremely simple and powerful [2, 3].
The word “Vedic” is derived from the word “Veda”

International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 757

ISSN 2229-5518

which means the store-house of all knowledge. Vedic mathe- matics 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 noncomple-
tion.
10) Sankalana- vyavakalanabhyam – By addition and by sub-
traction.
11) Shesanyankena Charamena – The remainders by the last
digit.
12) Shunyam Saamyasamuccaye – When the sum is the same that sum is zero.
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 trigonom- etry, plain and spherical geometry, conics, calculus (both dif- ferential and integral), and applied mathematics of various kinds. As mentioned earlier, all these Sutras were reconstruct- ed from ancient Vedic texts early in the last century. Many Sub-sutras were also discovered at the same time, which are not discussed here. The beauty of Vedic mathematics lies in the fact that it reduces the otherwise cumbersome-looking calculations in conventional mathematics to a very simple one. This is so because the Vedic formulae are claimed to be based on the natural principles on which the human mind works. This is a very interesting field and presents some effective al- gorithms which can be applied to various branches of engi- neering such as computing and digital signal processing [ 1,4].
The multiplier architecture can be generally classified into three categories. First is the serial multiplier which em- phasizes on hardware and minimum amount of chip area. Second is parallel multiplier (array and tree) which carries out high speed mathematical operations. But the drawback is the relatively larger chip area consumption. Third is serial- paral- lel multiplier which serves as a good trade-off between the times consuming serial multiplier and the area consuming parallel multipliers.

3 DESIGN OF PROPOSED MAC UNIT

3.1 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”. To illustrate this multipli- cation scheme, let us consider the multiplication of two deci- mal numbers (5498 × 2314). The conventional methods already know to us will require 16 multiplications and 15 additions.
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. Thus, each digit of the multiplier has a small box common to a digit of the 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 multi- plicand 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 tiryak- bhyam Sutra.
The design starts first with Multiplier design, that is
2x2 bit multiplier as shown in figure 2. Here, “Urdhva Tiryak-
bhyam 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.

International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 758

ISSN 2229-5518

Fig.2 : Hardware Realization of 2x2 block
To scale the multiplier further, Karatsuba – Ofman al- gorithm 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[11]. A multipli- cation of 2n digit integer is reduced to two n digit multiplica- tions, one (n+1) digit multiplication, two n digit subtractions, two left shift operations, two n digit additions and two 2n dig- it 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 di- vide 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.

For Multiplier, first the basic blocks, that are the

2x2 bit multipliers have been made and then, using these

blocks, 4x4 block has been made and then using this 4x4

block, 8x8 bit block, 16x16 bit block and then finally 32 x 32

bit Multiplier as shown in figure 3has been made[7].

Fig.3: Block diagram of 32x32 Multiply block

3.2 MAC

The MAC unit is built with Vedic multiplier. Hence the advantages of Vedic multiplier like increase in speed, decrease in delay, decrease in power consumption, de- crease in area occupied will enhance the MAC unit also. The DSP applications like Convolution (summation of mul- tiplied terms), Correlation, Discrete Fourier Transform, Fast Fourier Transform etc employ the MAC unit, which assists in efficient computing in terms of speed, delay and com- plexity.

zero

Let k= 2n. If k is odd, it can be right padded with a

The product XY can be computed as follows:

Fig.4 : Multiply and Accumulate Unit

International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 759

ISSN 2229-5518

4 PERFORMANEC EVALUVATION AND COMPARISON

The proposed MAC unit is implemented using two differ- ent coding techniques viz., Wallace tree and Vedic tech- nique for 32 bit multiplier. It is evident that there is a con- siderable increase in speed of the Vedic architecture. The simulation results for 32 bit multiply and accumulate unit is shown in the figure 5

Fig 5: Simulation result of MAC Unit

TABLE 1

DELAY COMPARISION FOR DIFFERENT MAC UNITS

Performance		MAC unit us- ing Wallace Tree	MAC unit us- ing Vedic Mul- tiplier

Minimum Period (ns)	64.624ns	37.799ns

Area (No. of LUTs)	3172	2714

The worst case propagation delay in the Optimized

MAC unit using Vedic multiplier case was found to be

37.799ns. To compare it with other implementations the

design was synthesized on XILINX: SPARTAN: xc3s500e-

5fg320[18]. Table 1 shows the synthesis result for various

implementations. The result obtained from proposed MAC

unit using Vedic multiplier is faster than MAC unit using

Wallace Tree.

5 CONCLUSION

In this paper, a new method of 32-bit MAC unit is presented based on Vedic method of multiplication [9]. This gives us method for hierarchical multiplier design. So the design complexity gets reduced for inputs of large no of bits and modularity gets increased.. The Multiply and Ac- cumulate Unit designed with Vedic overlay high speed multiplier algorithm exhibits improved efficiency in terms of speed and area.

REFERENCES

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

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

[2] Booth, A.D., “A signed binary multiplication technique,” Quarterly

Journal of Mechanics and Applied Mathematics, vol. 4, pt. 2, pp. 236–

240, 1951.

[3] Jagadguru Swami Sri Bharath, Krsna Tirathji, “Vedic Mathematics or Sixteen Simple Sutras From The Vedas”, Motilal Banarsidas, Varana- si(India),1986.

[4] A.P. Nicholas, K.R Williams, J. Pickles, “Application of Urdhava Sutra”, Spiritual Study Group, Roorkee (India),1984.

[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] Mrs. M. Ramalatha, Prof. D. Sridharan, “VLSI Based High Speed Kar- atsuba Multiplier for Cryptographic Applications Using Vedic Mathemat- ics”, IJSCI, 2007

[7] Thapliyal H. and Srinivas M.B. “High Speed Efficient N x N Bit Parallel Hierarchical Overlay Multiplier Architecture Based on Ancient Indian Ve- dic Mathematics”, Transactions on Engineering, Computing and Technology, 2004, Vol.2.

[8] Jagadguru Swami Sri Bharati Krsna Tirthji Maharaja,” Vedic Mathe- matics”, Motilal Banarsidas, Varanasi, India, 1986.

[9] “A Reduced-Bit Multiplication Algorithm For Digital Arithmetic” Har- preet Singh Dhilon And Abhijit Mitra, International Journal of Com- putational and Mathematical Sciences, Waset, Spring, 2008.

[10] “Lifting Scheme Discrete Wavelet Transform Using Vertical and Crosswise

Multipliers” Anthony O’Brien and Richard Conway, ISSC,

2008,Galway, June 18-19.

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

[12] Shripad 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.

[13] 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).

[14] M.C. Hanumantharaju, H. Jayalaxmi, R.K. Renuka, M. Ravishankar, "A High Speed Block Convolution Using Ancient Indian Vedic Mathemat- ics," ICCIMA, vol. 2, pp.169-173, International Conference on Com- putational Intelligence and Multimedia Applications, 2007.

[15] Himanshu Thapliyal, “Vedic Mathematics for Faster Mental Calcu- lations and High Speed VLSI Arithmetic”, Invited talk at IEEE Com- puter Society Student Chapter, University of South Florida, Tampa, FL, Nov 14 2008.

[16] Jeganathan Sriskandarajah, “Secrets of Ancient Maths: Vedic Math- ematics”, Journal of Indic Studies Foundation, California, pages 15 and 16.

[17] S. Kumaravel, Ramalatha Marimuthu, "VLSI Implementation of High Performance RSA Algorithm Using Vedic Mathematics," IC- CIMA, vol. 4, pp.126-128, International Conference on Computation- al Intelligence and Multimedia Applications (ICCIMA 2007), 2007.

[18] www.xilinx.com.

AUTHORS DETAILS:

International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 760

ISSN 2229-5518

• V.K.Karthik, Y.Govardhan, V.Karunakara Reddy is currently pursuing III EConE degree program in Electronics & Control engineering in Sree Vidhyanikethan Engineering college, Tirupati, A.P, India.

E-mail: Karthikvkk@gmail.com, Govardhan2012@gmail.com, Karunakarreddy7777@gmail.com

• K.Praveena is currently working as Asst.Professor in Electronics &

Control engineering in Sree Vidhyanikethan Engineering College, Tirupati, A.P, India.

E-mail: Naidu.kmd@gmail.com