Performance Analysis of Vedic Mathematics Algorithms

Contributed by:
Harshdeep Singh
This PDF contains :
Abstract,
Keywords,
1. Introduction,
2. Conventional multiplier and divider,
2.1 Four-bit Array multiplier,
2.2 Eight-bit Array multiplier,
2.3 Binary divider,
3. Vedic mathematics algorithms,
3.1 Urdhva Tiryagbhyam Sutra for multiplication,
3.2 Nikhilam Sutra for multiplication,
3.3 Nikhilam Sutra for division,
3.4 Dhwajank Sutra for division,
3.5 An application of digital signal processor,
4. Implementation and comparisons,
5. Conclusion
1. Sådhanå (2021)46:83 Ó Indian Academy of Sciences
Sadhana(0123456789().,-volV)FT3](012345
6789().,-volV)
Performance analysis of Vedic mathematics algorithms
on re-configurable hardware platform
RHEA BIJI and VIJAY SAVANI*
Department of Electronics and Communication Engineering, Institute of Technology, Nirma University,
Ahmedabad, India
e-mail: 19mecv15@nirmauni.ac.in; vijay.savani@nirmauni.ac.in
MS received 26 November 2020; revised 18 January 2021; accepted 10 February 2021
Abstract. For the overall performance of systems like microprocessors and digital signal processors (DSPs)
platforms, arithmetic units, all must be efficient in terms of speed, power, and area. Multipliers and dividers are
inevitable hardware employed in such systems. This paper focuses on Vedic mathematics algorithms for
multiplication and division for power-efficient, faster, and area-efficient design. For four- and eight-bit Vedic
multiplication algorithms, Urdhva Tiryagbhyam and Nikhilam Sutras are employed in this paper. For eight-bit
Vedic division algorithms, Nikhilam and Dhwajank Sutras are used. The Vedic mathematics algorithms are also
compared to conventional methods of multiplication (like Array multiplier) and division (using Booth multi-
plication algorithm). As an application of DSP, the linear convolution operation is implemented using both
conventional and Vedic algorithms. It has been observed that the Vedic algorithms operate faster, consume less
power, and occupy less area on a targeted hardware platform. The implementations were carried out using the
Verilog HDL language and Xilinx’s Vivado EDA tool. To measure various performance parameters, Cadence
simvision (using 180-nm GPDK CMOS Technology) and Xilinx’s ISE tool were also used.
Keywords. Digital signal processing; Vedic mathematics algorithms; Urdhva Tiryagbhyam; Nikhilam Sutra;
Verilog.
1. Introduction are discussed. The logic is much better on the count of
power consumption, hardware requirements, execution
Vedic mathematics has been the source of inspiration in the time, and space management. Key advantages from all the
field of computation for many centuries [1]. It is an ancient sutras have been taken and a novel architecture is devel-
system of mathematics based on 16 sutras [2]. Out of these, oped for the fast and efficient division [7].
Urdhva Tiryagbhyam and Nikhilam Sutras for multiplica- In [8], the authors have proposed a multiplier architec-
tion and Nikhilam Sutra and Dhwajank Sutra for division ture for signed multiplication. Signed multiplier architec-
are used in this paper. Multipliers and dividers, both are an ture is based on two’s complement and for unsigned data,
important computational unit in a processor and controllers. Urdhva Triyakbhyam Vedic multiplier is utilized. A carry
It affects the overall performance of the system also [3]. select adder is used in this method while calculating the
Hence, the optimization of area, speed, and power of these partial product. The major advantage obtained is less
units is very important [4, 5]. Thus Vedic mathematics combinational path delay compared with the existing
concepts and their algorithms are used in this paper to methods [9].
achieve a reduction in major performance parameters, i.e. In [6], the convolution operation is implemented. It
area, power, and speed (delay), as compared with conven- includes multiplication and additions in it. To improve the
tional multiplier and division architectures. Using Vedic overall speed of the convolution operation, Vedic (Urdhva
multiplication, a convolution operation is implemented. Triyakbhyam) multiplier is used.
This is a time-efficient way of implementing the operation The paper is organized as follows. In section 2, a con-
[6]. ventional Array multiplier and a conventional Binary
In [1] the authors have presented and compared the divider are discussed. In section 3, Vedic algorithms for
performance of different division sutras, namely Nikhilam, multiplication and division are discussed. Section 4 pre-
Paravartya, and Dhwajank. Principles in developing a sents the performance analysis of the algorithms. Imple-
completely new division logic for the base 2 number system mentation and its comparison of conventional and Vedic
algorithms are highlighted and presented in tabular form.
*For correspondence Finally, the concluding remarks are drawn in section 5.
2. 83 Page 2 of 5 Sådhanå (2021)46:83
2. Conventional multiplier and divider
In this section, the conventional methods of multiplication
and division are explained. Four- and eight-bit Array
multipliers and eight-bit Binary dividers are described.
2.1 Four-bit Array multiplier
The whole process requires multiplication and addition
operations. In binary, two bits can be multiplied using the
AND operation. The final result is obtained by adding the
partial products and the carry generated from the previous
additions [10, 11]. Here the full adders are being used for
this purpose. Four full adders have the third input as a fixed
value ‘‘0’’. Hence, they are equivalent to half adders. For a
4  4 Array multiplier, 16 AND gates, 4 half adders, and 8
full adders (totally 12 adders) are required.
Figure 1. Line diagram for 4  4 multiplication [13, 14].
2.2 Eight-bit Array multiplier
The structure of the eight-bit Array multiplier can be
realized by extending the four-bit Array multiplier struc- The line diagram in figure 1 shows the steps involved in
ture. In general x  y multiplier needs x  y AND gates, y 4  4 Vedic multiplication. The same procedure can be
half adders, and ðx  2Þ  y full adders (totally ðx  1Þ  y extended to build higher-order multipliers [13].
adders). Thus eight-bit Array multiplication needs 64 AND A four-bit Vedic multiplier is made using 4 two-bit
gates, 8 half adders, and 48 full adders (totally 56 adders). Vedic multipliers and 3 adders; 1 four-bit adder and 2
eight-bit adders are required for the same. An eight-bit
Vedic multiplier is made with the help of 4 four-bit Vedic
2.3 Binary divider multipliers and 3 adders. Totally, One 8-bit adder and two
In division operation, dividend and divisor are the inputs 12-bit adders are needed for this implementation.
and the outputs are in the form of quotient and remainder.
Mainly, a counter is present and some decisions need to be
taken. Also, shifting left operation is used. Booth’s division 3.2 Nikhilam Sutra for multiplication
algorithm is implemented for an 8-bit division operation. In this method, the complement of the larger number from
According to the steps, a program is written using Verilog its nearby base is calculated (see figure 2) before multi-
HDL and simulated to verify the functionality. plication [13].
3. Vedic mathematics algorithms 3.3 Nikhilam Sutra for division
In this section, Vedic mathematics algorithms for multi- The basics of division using Nikhilam Sutra for the division
plication and division are presented and explained. Two is shown in figure 3. Complement of divisor, multiplica-
algorithms for multiplication (i.e. Urdhva Tiryagbhyam tion, addition, incrementing of the counter, and comparison
Sutra and Nikhilam Sutra) and two algorithms for division, are the steps involved in this sutra [1].
(i.e. Nikhilam Sutra and Dhwajank Sutra, are discussed).
3.4 Dhwajank Sutra for division
3.1 Urdhva Tiryagbhyam Sutra for multiplication Mainly addition and multiplication of cross-products are
This sutra is known as Vertical and Cross-wise multipli- involved in the Dhwajank Sutra operation. MSBs of the
cation. It is generic for any of the n-bit multiplication [12]. divisor are kept aside. Later, the MSB of the dividend is
The multiplication and the addition operations are done in divided with the MSB of the divisor. Cross-product of
parallel [13]. quotient and rest of the bits is taken and addition is done.
3. Sådhanå (2021)46:83 Page 3 of 5 83
multipliers: Array multiplier and Vedic multiplier. The
delays obtained are compared in the Implementation and
comparisons section. It has been observed that the opera-
tions performed using the Vedic multiplier are faster as
compared with the conventional method.
4. Implementation and comparisons
In this section, the whole gist of the work is summarized in
terms of implementation results and comparison. Results
obtained are compared to see the significance of the Vedic
Figure 2. Example of Nikhilam (base) Sutra [13].
algorithms in the arithmetic unit. The implementation and
results for power are obtained using the Cadence EDA tool
with 180-nm GPDK CMOS Technology. The Xilinx
Vivado tool is used to figure out the area and delay (speed)
of the respective algorithms.
A conventional 4  4 Array multiplier is compared with
2 4-bit Vedic multipliers for performance parameters area,
delay, and power. The results of these performance
parameters are enumerated in table 1. There is a significant
decrease in the delay due to the efficient Vedic algorithm.
The other two parameters, which are area and power, do not
significantly decrease as compared to the conventional
method/algorithms. Also, the performance parameters of
the Vedic multiplier are compared to the results presented
[2, 8].
Figure 3. Example of Nikhilam (base) Sutra [15]. Percentage reduction in area, delay, and power as com-
pared with conventional method are listed in table 2. Per-
centage reduction is calculated as [(value in the
Sum is subtracted from a combination of the previous conventional algorithm – value in Vedic algorithm)/value
remainder and the next digit of the dividend. in conventional algorithm] 100. Significant improvement
The final remainder is obtained by subtraction of the in the delay is observed. The other two parameters have
right part of dividend prefixed by the last remainder and comparable reduction as shown in table 2.
cross-multiplication of quotient and divisor [16]. A conventional 8  8 Array multiplier is compared with
two 8-bit Vedic multipliers for performance parameters and
their results are presented in table 3. A significant decrease
3.5 An application of digital signal processor in delay, area, and power is observed using both the Vedic
algorithms. Also, performance parameters of Vedic multi-
(DSP): linear convolution
plier from literature are mentioned in it.
Linear convolution helps to estimate the output of the Percentage reduction in terms of area, delay, and power
system when an arbitrary input and the impulse response is as compared with the conventional method are listed in
available [17]. Basically, in linear convolution, multipliers table 4. Significant improvement in the area, power, and
and adders are element components for this operation. The delay is observed. Thus Vedic multiplication is faster and
convolution operation is done using two types of the resources required to store the intermediate values are
Table 1. Performance comparison of 4-bit conventional and Vedic multipliers (NR: not reported in corresponding reference).
Array multiplier Vedic_Crisscross multiplier Vedic_Nikhilam multiplier Multiplier Multiplier
Parameters (4  4) (4  4) (4  4) [2] [8]
Cells (area) 39 37 58 24 39
Power 48475.89 46363.21 46005.71 NR 125.06
Delay (ns) 5.85 3.75 3.29 10.43 14.62
4. 83 Page 4 of 5 Sådhanå (2021)46:83
Table 2. Percentage reduction in area, power, and delay for 4-bit Table 4. Percentage reduction in area, power, and delay (8-bit
multipliers. multipliers).
Percentage reduction as Percentage reduction as
compared with Vedic_Nikhilam compared with Vedic_Nikhilam
conventional multiplier Vedic_Crisscross multiplier conventional multiplier Vedic_Crisscross multiplier
(%) multiplier (4  4) (4  4) (%) multiplier (8  8) (8  8)
Cells (area) 5 No reduction Cells (area) 26.3 20.53
Power (nW) 4.35 5.10 Power (nW) 19.0 5.4
Delay (ns) 35.9 43.8 Delay (ns) 70.00 68.25
decreased. Finally, the reduction in delay and area helps in
the reduction of the overall power of the system.
In table 5 and table 6, a conventional divider is com- Table 5. Performance comparison of 8-bit conventional and
pared with two Vedic dividers (i.e. Nikhilam and Dhwa- Vedic dividers.
jank) for performance evaluation. Dividers have a higher
area than the multipliers. Hence, improvement using Vedic Binary Vedic_Nikhilam Vedic_Dhwajank
dividers is very useful to reduce the overall area, power, Parameters divider divider divider
and delay of the system. Cells 238 41 30
(area)
As seen from table 7, Vedic algorithms have advantages Power 3,71,982.66 3,01,062.29 3,51,893.61
in terms of delay when applied to a convolution operation (nW)
in DSP-related applications. The Vedic multiplier used here Delay (ns) 22.59 2.27 17.08
is the Urdhva Tiryagbhyam multiplier. Percentage reduc-
tion in terms of delay obtained in this paper and a reference
paper is also mentioned in the table.
As seen from table 8, 22.64% reduction in the delay is
Table 6. Percentage reduction in area, power, and delay for 8-bit
observed when Vedic multiplier is used in the convolution
dividers.
operation as compared with a conventional Array multi-
plier. Percentage reduction as per [17] is 28%. Hence, it can Percentage reduction as
be concluded that convolution operation can be performed compared with Vedic_Nikhilam Vedic_Dhwajank
significantly faster when the Vedic multipliers are used. conventional divider (%) divider divider
Cells (area) 82.77 87.39
Power (nW) 19.06 5.4
5. Conclusion Delay (ns) 89.0 24.4
Vedic algorithms have advantages in terms of power, area,
and delay. Thus they are used in systems like DSPs and
microprocessors so that the overall system becomes effi-
cient. In this paper two arithmetic units, i.e. multipliers and Table 7. Convolution using Array and Vedic multipliers.
dividers, are implemented using Vedic algorithms. For 4-bit
Urdhva multiplier, 5%, 35.9%, and 4.35% reductions in Convolution using Array Convolution using Vedic
area, delay, and power, respectively, are obtained as com- Parameters multiplier multiplier
pared with the conventional 4-bit Array multiplier; for the Delay (ns) 7.89 6.11
4-bit Vedic multiplier (Nikhilam), 5.1% and 43.8%
Table 3. Comparison of 8-bit conventional and Vedic multipliers (NR: not reported in corresponding reference).
Array multiplier Vedic_Crisscross multiplier Vedic_Nikhilam multiplier Multiplier Multiplier
Parameters (8  8) (8  8) (8  8) [2] [8]
Cells (area) 190 140 151 125 159
Power 1376457.98 31896.31 73683.43 NR 138.45
Delay (ns) 22.42 6.69 7.12 18.46 23.67
5. Sådhanå (2021)46:83 Page 5 of 5 83
Table 8. Percentage reduction in delay (convolution using Vedic [6] Batham N and Anjum S 2016 Algorithm for convolution
multiplier). operation in DFT using vedic multiplication. International
Journal of Engineering Innovations and Research 5(5):
Convolution using Vedic 288–291
Parameters multiplier [7] Toro S, Patil A, Chavan Y V, Patil S C, Bormane D S, and
Wadar S 2016 Division operation based on vedic mathe-
Reduction in delay [this 22.64% matics. In: Proceedings of the 2016 IEEE International
work] Conference on Advances in Electronics, Communication and
Reduction in delay [17] 28.00% Computer Technology (ICAECCT), IEEE, pp. 450–454
[8] Pichhode K, Patil M D, Shah D and Rohit B C 2015 FPGA
implementation of efficient vedic multiplier. In: Proceedings
of the 2015 International Conference on Information Pro-
reduction in power and delay are observed. Implementation cessing (ICIP), IEEE, pp. 565–570
[9] Sapkal K J and Shrawankar U 2017 Complexity analysis of
of 8-bit Urdhva multiplier results in 26.3%, 70%, and 19%
vedic mathematics algorithms for multicore environment.
reduction in terms of area, delay, and power, respectively,
International Journal of Rough Sets and Data Analysis 4:
compared with the conventional 8-bit Array multiplier; for 31–47
the 8-bit Nikhilam multiplier, 20.53%, 68.25%, and 5.4% [10] Kumar A 2017 Comparative analysis of vedic and array
reductions in area, delay, and power are obtained; nearly multiplier. International Journal of Electronics and Com-
80% reduction in terms of area and power is observed for munication Engineering and Technology 8(3): 17–27
8-bit Nikhilam and Dhwajank dividers as compared with [11] Sriraman L and Prabakar T N 2012 Design and implemen-
the conventional divider whereas reduction in the delay is tation of two variable multiplier using KCM and vedic
89% and 24.4%. Convolution using Vedic operations has a mathematics. In: Proceedings of the 2012 1st International
reduction in delay of 22.64% over conventional methods. Conference on Recent Advances in Information Technology
Implementations can be extended to 16-, 32-, 64-bit mul- (RAIT), IEEE, pp. 782–787
[12] Sudeep M C, Bimba M S, and Vucha M 2014 Design and
tipliers and dividers.
FPGA implementation of high speed vedic multiplier.
International Journal of Computer Applications 90(16):
10.5120/15802-4641
[13] Prasada G S V, Seshikala G, and Sampathila N 2018
References Performance analysis of 6464 bit multiplier designed using
urdhva tiryakbyham and nikhilam navatashcaramam dasha-
[1] Tadas A and Rotake D 2015 64 bit divider using vedic tah sutras. In: Proceedings of the 2018 IEEE Distributed
mathematics. In: Proceedings of the 2015 International Computing, VLSI, Electrical Circuits and Robotics (DIS-
Conference on Smart Technologies and Management for COVER), IEEE, pp. 28–31
Computing, Communication, Controls, Energy and Materials [14] Prasada G S V, Seshikala G, and Niranjana S 2019 Design
(ICSTM), IEEE, pp. 317–320 of high speed 32-bit floating point multiplier using urdhva
[2] Akhter S and Chaturvedi S 2019 Modified binary multiplier triyagbhyam sutra of vedic mathematics. International
circuit based on vedic mathematics. In: Proceedings of the Journal of Recent Technology and Engineering 8(2 special
2019 6th International Conference on Signal Processing and issue 3): 1064–1067
Integrated Networks (SPIN), IEEE, pp. 234–237 [15] Rajani M and Sridevi N 2015 Survey on implementation of
[3] Kishor D R and Bhaaskaran V K 2014 Low power divider IEEE754 floating point number division using vedic tech-
using vedic mathematics. In: Proceedings of the 2014 niques. International Journal of Engineering Development
International Conference on Advances in Computing, Com- and Research 3(3)
munications and Informatics (ICACCI), IEEE, pp. 575–580 [16] Ugra Mohan Kumar S K, Singh M P, and Yadav A K 2017
[4] Thakur K and Sharma T 2019 Area efficient high speed Fast and efficient division technique using vedic mathemat-
vedic multiplier. International Journal of Innovative Tech- ics in Verilog code. International Journal of Scientific and
nology and Exploring Engineering 8(9S): 302–306 Engineering Research 8(10): 99–103
[5] Akhter S, Saini V and Saini J 2017 Analysis of vedic [17] Punwantwar N R and Chatur P N 2015 Convolution and
multiplier using various adder topologies. In: Proceedings of deconvolution using vedic mathematics. International Jour-
the 2017 4th International Conference on Signal Processing nal of Advanced Research in Electrical, Electronics, and
and Integrated Networks (SPIN), IEEE, pp. 173–176 Instrumentation Engineering 4(6): 5216–5223