25-08-2017, 09:32 PM
A Reduced-Bit Multiplication Algorithm for Digital Arithmetic
A Reduced-Bit Multiplication.pdf (Size: 378.38 KB / Downloads: 31)
Abstract
A reduced-bit multiplication algorithm based on the
ancient Vedic multiplication formulae is proposed in this paper.
Both the Vedic multiplication formulae, Urdhva tiryakbhyam and
Nikhilam, are first discussed in detail. Urdhva tiryakbhyam, being
a general multiplication formula, is equally applicable to all cases of
multiplication. It is applied to the digital arithmetic and is shown to
yield a multiplier architecture which is very similar to the popular
array multiplier. Due to its structure, it leads to a high carry propagation
delay in case of multiplication of large numbers. Nikhilam
Sutra, on the other hand, is more efficient in the multiplication of large
numbers as it reduces the multiplication of two large numbers to that
of two smaller numbers. The framework of the proposed algorithm
is taken from this Sutra and is further optimized by use of some
general arithmetic operations such as expansion and bit-shifting to
take advantage of bit-reduction in multiplication. We illustrate the
proposed algorithm by reducing a general 4£4-bit multiplication to
a single 2 £ 2-bit multiplication operation.
INTRODUCTION
DIGITAL multipliers [1], [2] are the core components of
all the digital signal processors (DSPs) and the speed
of the DSP is largely determined by the speed of its multipliers
[3]. They are indispensable in the implementation of
computation systems realizing many important functions such
as fast Fourier transforms (FFTs) and multiply accumulate
(MAC). Two most common multiplication algorithms followed
in the digital hardware are array multiplication algorithm and
Booth multiplication algorithm [4]. The computation time
taken by the array multiplier is comparatively less because
the partial products are calculated independently in parallel.
The delay associated with the array multiplier is the time
taken by the signals to propagate through the gates that
form the multiplication array. Booth multiplication is another
important multiplication algorithm [5]. Large booth arrays
are required for high speed multiplication and exponential
operations which in turn require large partial sum and partial
carry registers. Multiplication of two n-bit operands using
a radix-4 booth recording multiplier requires approximately
n=(2m) clock cycles to generate the least significant half of
the final product, where m is the number of Booth recoder
adder stages.
VEDIC MATHEMATICS
Vedic mathematics is the name given to the ancient Indian
system of mathematics that was rediscovered in the early
twentieth century from ancient Indian sculptures (Vedas) by
Sri B. K. Tirtha (1884-1960) [10]. It mainly deals with
Vedic mathematical formulae and their application to various
branches of mathematics. The algorithms based on conventional
mathematics can be simplified and even optimized
by the use of Vedic Sutras. 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. [10]. These Sutras along
with their brief meanings are enlisted below alphabetically.
THE PROPOSED VEDIC MULTIPLIER
The proposed Vedic multiplier is based on the Vedic multiplication
formulae (Sutra). These Sutra have been traditionally
used for the multiplication of two numbers in the decimal
number system. In this paper, we apply the same ideas to
the binary number system to make the proposed algorithm
compatible with the digital hardware. Let us first discuss both
these Sutras in detail.
Urdhva Tiryakbhyam Sutra
Urdhva tiryakbhyam Sutra is a general multiplication formula
applicable to all cases of multiplication. It literally means
“Vertically and Crosswise”. To illustrate this multiplication
scheme, let us consider the multiplication of two decimal
numbers (325 £ 728). Line diagram for the multiplication
is shown in Fig. 1. The digits on the two ends of the line
are multiplied and the result is added with the previous carry.
When there are more lines in one step, all the results are added
to the previous carry. The least significant digit of the number
thus obtained acts as one of the result digits and the rest act
as the carry for the next step. Initially the carry is taken to be
zero.
CONCLUSION
A new reduced-bit multiplication algorithm based on a formula
of ancient Indian Vedic mathematics has been proposed.
Both the Vedic multiplication formulae, Urdhva tiryakbhyam
and Nikhilam, have been investigated in detail. Urdhva
tiryakbhyam, being general mathematical formula, is equally
applicable to all cases of multiplication.