FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention: NOVEL METHOD AND DEVICE WITH REDUCED BIT REQUIREMENT FOR MULTIPLICATION
Applicant
KPIT Cummins InfoSystems Ltd.,
35 and 36, Rajiv Gandhi Infotech Park,
Phase 1, MIDC, Hinjawadi, Pune-411 057, India
The following specification particularly describes the invention and the manner in which it is to be performed.

Field of the invention
The invention relates to methods and Devices related to multipliers used in computing. More particularly, this invention relates to methods and Devices for enabling the multiplication of numbers with up to N bits using (N-l) bit multiplier.
Background of the invention
Multipliers are employed for carrying out operations involving multiplications like in digital signal processing. The commonly employed methods for enabling the multiplications are Booth's algorithm, Shift and add multiplier, array multiplier and Sequential multiplication.
Existing multiplication methods utilize N-bit multiplier to carry out N-bit multiplication. Consequently, the multiplication of higher bit number using these multipliers is not usually possible. Efforts have been directed to address the problem of carrying out N-bit multiplications using N-l bit multipliers. The Japanese Patent D0cument number JP63208940 discloses a multiplication Device which is fitted with an internal multiplier without m bit error and an input selector Device installed on the input side of the said internal multiplier, and an output selector Device installed on the output side of the said internal multiplier. This input selector Device determines the size of the absolute value of the input data. If the input data is greater than the m bit, the input selector ignores the least significant digits, and if the input data is smaller than the m bit, it assigns the said input data to the said internal multiplier so as to make the entire input bit valid. The output selector Device converts the output digit numbers of the said internal multiplier to the digit numbers of the multiplication result of the said input data. The invention suffers from the disadvantage of not being accurate over a wide range of multiplicands because of ignoring lower bits in some cases. Nikhilam Navatas' Caramam Dasata Sutra is a Vedic multiplication method used for the multiplication of two numbers that are close to a certain base. The Vedic method in a fashion applicable to N-bit multiplier can be described in the following manner:


N l -Multiplicand
N2 - Multiplier
B-Base= ION
Dl - Devlation of Nl from B
D2 - Devlation of N2 from B
1. D1=(N1-10N)
2. D2 = (N2-10N)
3. Ml=Dl x D2
4. Devl = N1 +D2 or Nl - D2 based on the sign of D2
5. if any carry is generated from Ml add it to Devl, MultMSB = carry of Ml + Devl, MultLSB = Ml without carry
6. Result = MultMSB | MultLSB
However, the Sutra cannot be used conveniently in its current form for multipliers used in computing technology since current computing technology is based on hexadecimal number system and the Sutra is specifically meant for Decimal number systems. The current inventors have developed methods and Devices whereby the problem of N-bit multiplication by N-l bit multiplier can be addressed. The methods and Devices of the current invention overcome the mentioned drawbacks of the prior art mentioned. The methods and Devices of the current invention enable the multiplication of numbers with up to N bits by using a (N-l) bit multiplier.
Object of the invention
It is an object of this invention to provide for methods to enable multiplication of numbers having up to N bits using (N-l) bit multiplier. Another object of the invention is to provide for Devices for enabling the multiplication of numbers having up to N bits by using (N-l) bit multiplier.
Summary of the invention
The present invention relates to methods and hardware architecture for enabling the multiplication of numbers with up to N bits using (N-l) bit multiplier.


The present invention provides for methods to enable multiplication of numbers with up to N bits by using a (N-1) bit multiplier comprising the steps of subtracting the base (2(N-1)) from the numbers, multiplying the differences using the (N-1) bit multiplier to obtain a first product, adding the first number and the difference of the second number and the base to obtain a first sum, adding the first sum to the (N-1) bits carry of the first product to obtain a second sum and concatenating the second sum and the (N-1) least significant bits of the first product to obtain the final result of the multiplication of the numbers. In case the numbers have unequal bits, the method comprises of the steps of subtracting the base (2(N"1)) from the numbers, multiplying the differences using the (N-1) bit multiplier to obtain a first product, adding the first number and the difference of the second number and the base to obtain a first sum, adding first sum and (N-1) bits carry of the first product to obtain second sum, converting the (N-1) bits LSB of the first product to 2's complement by subtracting with base to obtain the LSB of the final product, subtracting (N-1) bits MSB of the first product from the first sum to obtain the third difference and subtracting the third difference to obtain the MSB of the final product.
The present invention provides for Devices to enable the multiplication of numbers with up to N bits using (N-1) bit multiplier. The Device comprises subtractors to subtract the base from the numbers, (N-1) bit multiplier to multiply the differences, first adder to add the first number and the second difference, second adder to add the output of the first adder and the (N-1) bit carry of the output of the (N-1) bit multiplier, concatenating means to concatenate the output of the second adder and the (N-1) least significant bits of the output of the (N-1) bit multiplier to obtain the final result wherein the output of the first adder forms the MSB and the (N-1) least significant bits of the output of the (N-1) bit multiplier forms the LSB of the final result. The present invention also provides for Devices to enable the multiplication of numbers with up to N bits and having unequal number of bits using (N-1) bit multiplier. The Device comprises subtractors to subtract the base from the numbers, (N-1) bit multiplier to multiply the differences, first adder to add the


first number and the second difference, second adder to add the output of the first adder and the (N-1) bits carry of the output of the (N-1) bit multiplier, third subtractor to subtract the (N-1) bits LSB of the output of the multiplier from the base (2(N-1)), first multiplexer to selectively output from among the output of the third subtractor and the (N-1) bits LSB of the output of the (N-1) bit multiplier. Optionally XOR and AND gates to operate logically on the output of second adder, fourth subtractor to subtract -1 from the output of the second adder, a second multiplexer to selectively output from among the output of the second adder, the fourth subtractor and the AND and XOR gates. A concatenating means to concatenate the second sum or the output of the second multiplexer and the (N-1) bits LSB of the first product or the output of the first multiplexer to obtain the final result, wherein the final result, the second sum or the output of the second multiplexer forms the most significant bits and the (N-1) bits LSB of the first product or the output of the first multiplexer forms the least significant bits.
Description of the drawings
Figure 1 outlines the process for enabling multiplication of numbers with up to N bits by a (N-1) bit multiplier using the method of this invention. Nl and N2 represent the multiplicands having up to N bits that are to be subject to the multiplication. B represents the base and is taken as 2(N-1). 1 represents the (N-1) bit multiplier, 2 and 3 represent subtractors. Nl-B represents the output of the subtractor, 2. N2-B represents the output of the subtractor, 3. 4 represents an adder, and 6 represents the register storing the result from the adder, 4. 7 represents the Bits [(N-2):0] of register 5 (N-1 Least Significant Bits (LSB) of register 5). 8 represents the carry of 5 - bits ([2*(N-1): N-1] of register, 5 (N-1 Most Significant Bits (MSB) of register, 5). 9 represents an adder, 10 represents the register containing result of addition of 8 and 6. 11 represents register containing same value as 7 in same order bitwise. 12 represents the register containing the final result concatenated 10 and 11 where 10 is Most Significant Bits (N bit MSB) and 11 is Least Significant Bits (N bit LSB).


Figure 2 represents the Device for multiplication of numbers with up to N bits by (N-l) bit multiplier where the numbers are both either positive or negative. MO represents (N-l) bit multiplier, U0 and Ul represent subtractors, U2 and U3 represents adders. B represents the base (2(N_1)), Nl and N2 represents numbers with up to N bits. D0 represents the output of MO, Dl represents the LSB of D0 (D0 [N-2:0]) and D2 represents the MSB of D0 DO ([2*(N-1): N-l]). PO represents the final product.
Figure 3 represents the Device for multiplication of numbers with up to N bits by (N-l) bit multiplier where one of the numbers has N bits and the other has less than N bits. MO represents (N-l) bit multiplier, U0 and Ul represent subtractors, U2 and U3 represents adders. B represents the base (2(N-1)), Nl is an N bit number and N2 is a number with lesser than N bits. Ml and M2 represents multiplexers, XOR represents an XOR gate and AND represents an AND gate. U4 represents a subtractor. Dl represents the LSB of D0 (D0 [N-2:0]) and D2 represents the MSB of D0 DO ([2*(N-1): N-l]). PO represents the final product. Cl represents the most significant bits of result of Ul, CO represents Most significant bits of the result of U0, C2 represents most significant bits of result of U2. XOR gate derives the multiplexers to select from two different paths based on c0 and cl. AND gate generates the most significant one bits (leftmost bits) of the final product. U5 represents subtractor to subtract 1 from the output of U3.
Detailed Description of the invention
The present invention addresses the problem of enabling the multiplication of
numbers with up to N bits using (N-l) bit multipliers. The invention provides for
methods and Devices for enabling the multiplication of numbers with up to N
bits using (N-l) bit multiplier.
By using the methods and Devices of this invention, existing (N-l) bit multiplier
can be scaled up by one bit or successive bits without affecting the hardware
requirements and the speed much.
The method of this invention for the multiplication of numbers of up to N-bits by
the (N-l) bit multiplier comprises of the steps of: selecting a base for the


operation. The base selected is 2(N-1). The differences of the first and second numbers from the base are determined. The first and second differences are then subject to multiplication using the (N-l) multiplier to obtain a first product. The first number is added to the second difference to obtain the first sum. The first sum is added to the (N-l) bits carry of the first product to obtain the second sum. The second sum and the (N-l) bits wide portion of the first product are concatenated to obtain the result where the second sum forms the most significant bits and the (N-l) bits wide portion of the first product forms the least significant bits.
In one preferred embodiment of the invention, the method for enabling the multiplication of numbers with up to N bits using (N-l) bit multiplier where the numbers possess equal number of bits comprises the steps of:
- selecting the base as 2(N"1);
subtracting the base from the first number to obtain the first difference and the base from the second number to obtain the second difference;
- multiplying the first difference and the second difference in the (N-l) bit
multiplier to obtain the first product;
adding the first number and the second difference to obtain a first sum;
adding the first sum and the (N-l) bits carry of the first product to obtain
a second sum;
concatenating the second sum and the (N-l) least significant bits of the
first product to obtain the result where the second sum forms the most
significant bits and the (N-l) bits LSB of the first product forms the least
significant bits. In another preferred embodiment of this invention, the method for enabling the multiplication of numbers with up to N bits using (N-l) bit multiplier where the numbers possess unequal number of bits comprises of the steps of:
selecting the base as 2(N"1);
subtracting the base from the first number to obtain the first difference
and the base from the second number to obtain the second difference;


- multiplying the first difference and the second difference in the (N-l) bit
multiplier to obtain the first product;
adding the first number and the second difference to obtain a first sum; adding the first sum and the (N-l) bits carry of the first product to obtain a second sum;
- converting the (N-l) bits LSB of the first product to 2's complement by subtracting with base to obtain the LSB of the final product; subtracting the (N-l) bits MSB of the first product from the first sum to obtain the third difference;
- subtracting 1 from the third difference to obtain the MSB of the final product.
The methods of this invention can be used fro computing in the hexadecimal system.
Figure 1 illustrates the method of this invention. The figure is for the purpose of illustrating the invention and does not limit the scope of the invention. Nl represents the first number with up to N-bits and N2 represents the second number with up to N-bits. B represents the base and is 2(N"1) is selected as the base. The difference between Nl and B is determined using the adder/subtractor, 2. The result thus obtained is Nl-B. The difference between N2 and B is determined using the adder/subtractor, 3. The result thus obtained is N2-B. The first number, Nl and the second difference, N2-B are then subjected to addition using the adder, 4 to obtain the result 6. The differences, Nl-B and N2-B are subjected to multiplication using the (N-l) bit multiplier, 1 to obtain the product, 5. The product, 5 is represented in the portions, 7 and 8 where 7 represents the (N-l)-bits portion and 8 represents the carry of 5 over 7. The sum, 6 is added to the carry of 5, 8 using the adder, 9 to obtain the result 10. 12 represents the final product and is the concatenation of 10 and 11 (11 is same as 7), where 10 forms the most significant bits and 11 form the least significant bits. The Device of this invention comprises subtractors, adders and optionally multiplexers and AND and XOR gates in addition to the (N-l) bit multiplier.


In one preferred embodiment of this invention, the Device for enabling the multiplication of number with up to N bits using (N-1) bit multiplier comprises of:
- first subtracter means for subtracting the first number from the base, 2(N"
!) to obtain the first difference;
second subtractor means for subtracting the second number from the base to obtain the second difference;
- (N-1) bit multiplier means for multiplying the first difference and the
second difference to obtain the first product;
first adder means for adding the first number and the second difference to obtain the first sum;
second adder means for adding the first sum and (N-1) bits carry of the first product to obtain the second sum;
- concatenation means for concatenating the second sum and the (N-1) bits
LSB of the first product to obtain the final result, wherein the final result,
the second sum forms the most significant bits and the (N-1) bits LSB of
the first product forms the least significant bits.
Figure 2 represents a Device of this invention. The figure is for the purpose of illustration only and Does not limit the scope of the invention. In figure 2, U0 and Ul represent subtractors that subtract the base (2(N"1)) from the numbers, Nl and N2. U0 and Ul provide the outputs Nl-B and N2-B respectively. The (N-1) bit multiplier, Ml is used to calculate the product of Nl-B and N2-B. The adder, U2 adds the first number, Nl and the second difference, N2-B to provide the first sum. The adder, U3 adds the first sum and the (N-1) bits carry of the first product to provide the second sum. A concatenation means provides the final result by concatenation of the second sum and the (N-1) bits LSB of the first product where the second sum forms the MSB of the final product and the (N-1) bits LSB of the first product forms the LSB of the final product.
The above Device can enable the multiplication of numbers with up to N bits using (N-1) bit multiplier where the numbers are having equal number of bits.


In another preferred embodiment of this invention, a Device for the multiplication of numbers with up to N bits and having unequal number of bits is provided. The Device comprises:
first subtractor means for subtracting the first number from the base, 2^"
l) to obtain the first difference;
- second subtractor means for subtracting the second number from the base to obtain the second difference;
- (N-l) bit multiplier means for multiplying the first difference and the second difference to obtain the first product;
- first adder means for adding the first number and the second difference to obtain the first sum;
optionally, third subtractor means for subtracting (N-l) bits LSB of the first product from the base to obtain the third difference;
- second adder means for adding the first sum and (N-l) bits carry of the first product to obtain the second sum;
- optionally, first multiplexer to selectively output from among the third difference and the (N-l) bits LSB of the first product to obtain the LSB of the final product;
- optionally, AND gate and XOR gate to provide a logic output for the second sum and the most significant one bit of the final product; optionally, fourth subtractor means for subtracting 1 from the second sum to obtain the fourth difference;
optionally, second multiplexer means to selectively output from among the second sum, fourth difference and the output from the AND and XOR gates to obtain the MSB of the final product;
- concatenation means for concatenating the second sum or the output of
the second multiplexer and the (N-l) bits LSB of the first product or the
output of the first multiplexer to obtain the final result, wherein the final
result, the second sum or the output of the second multiplexer forms the
most significant bits and the (N-l) bits LSB of the first product or the
output of the first multiplexer forms the least significant bits.


Hardware description languages (HDL) can be used for the purposes of this invention. A preferred HDL for this invention is the Verilog HDL. Funtional simulation can be done using NC-Verilog tool (Cadence). DC-Ultra (Synopsys) tool can be used for the synthesis of the Verilog code to generate netlist. Figure 3 represents a Device of this invention as mentioned above. The figure is for the purpose of illustration only and Does not limit the scope of the invention. In Figure 3, U0 and Ul represent subtracters that subtract the base (2(N"1)) from the numbers, Nl and N2. U0 and Ul provide the outputs Nl-B and N2-B respectively. The (N-l) bit multiplier, Ml is used to calculate the product of Nl-B and N2-B. The adder, U2 adds the first number, Nl and the second difference, N2-B to provide the first sum. The adder, U3 adds the first sum and the (N-l) bits carry of the first product to provide the second sum. The subtractor, U4 subtracts the (N-l) bits LSB of the output of the (N-l) bit multiplier. The multiplexer, Ml selectively outputs from among the (N-l) bits LSB and the output of U4. AND and XOR are logic operators to operate on the second sum. The subtractor, U5 subtracts -1 from the output of the second adder, U3. The XOR and AND gates provide logic operation for output of U3. The multiplexer, M2 selectively outputs from among the output of the second adder, the XOR and AND gates and the U5. A concatenation means concatenates the output of the first multiplexer, Ml or the (N-l) bits LSB of the first product and the second multiplexer, M2 or the second sum to obtain the final result wherein the second sum or the output of the second multiplexer forms the most significant bits and the (N-l) bits LSB of the first product or the output of the first multiplexer forms the least significant bits.
The following examples further illustrate the invention. The examples are for illustration only and D0 not limit the scope of the invention.
Example 1:
Multiplication of 235 and 211 using a 7-bit multiplier where both the numbers are greater than the base:
Nl=235
N2 = 211


Nl and N2 are 8-bit numbers,
B = 128 i.e, 2(N-1)
Binary representations:
Nl=11101011
N2 = 11010011
B= 10000000
Nl-B = 1101011
N2-B = 1010011
(Nl-B) * (N2-B) = 10001010110001 (This multiplication is carried out in the
(N-l) bit multiplier)
N3 = (N-l) bits wide portion of the above product = 0110001
N4 is the carry of the above = 1000101
N5=N1+(N2-B)= 100111110
N6 = N5+N4= 110000011
The final result of the process, N7 = concatenation of N6 and N3, where N6
forms the MSB and N3 forms the LSB = 1100000110110001
The final result, N7 in decimal form = 49585
Example 2:
Multiplication of 76 and 105 using a 7-bit multiplier where both the numbers are
lesser than the base:
Nl=76
N2= 105
Nl and N2 are both 7-bit numbers
B = 128 i.e, 2(N"1)
Binary representations:
Nl = 1001100
N2 = 1101001
B= 10000000
Nl-B = -110100
N2-B = -10111


(Nl-B) * (N2-B) = 10010101100 (This multiplication is carried out in the (N-1)
bit multiplier)
N3 = (N-1) bits wide portion of the above product = 0101100
N4 is the carry of the above =1001
N5=N1+(N2-B) = 110101
N6 = N5+N4 = 111110
The final result of the process, N7 = concatenation of N6 and N3, where N6
forms the MSB and N3 forms the LSB = 1111100101100
The final result, N7 in decimal form = 7980
Example 3:
Multiplication of 194 and 98 using a 7 bit multiplier when one number is less
than the base and other is greater than the base
Nl= 194
N2 = 98
Nl is 8 bit number and N2 is 7 bit number
B = 128 i.e. 2(N"1)
Binary representations
Nl = 11000010
N2= 1100010
B =10000000
Nl-B =1000010
N2-B = -11110
(Nl-B) * (N2-B) = -1111 0111100 (This multiplication is carried out in the (N-
1) bit multiplier)
N3 = 2's complement of the (N-1) bits wide portion of the above product as this
is negative number = 1000100
N4 = carry of the above product = -1111
N5 = Nl + (N2-B) = 10100100
N6 = N5 + N4 - 1 (One is subtracted because the product of N-1 bit multiplier
output is negative and 2's complement of N3 has been taken) = 10010100


The final result of the process, N7 = concatenation of N6 and N3 where N6 forms the MSB and N3 forms the LSB = 100101001000100 The final result, N7 in decimal form = 19012


We claim,
1. A method for enabling multiplication of a first number and a second
number each having up to N bits using (N-l) bit multiplier where both
the numbers have equal number of bits comprising the steps of:
selecting 2(N_1) as the base;
subtracting the base from the first number to obtain the first difference;
subtracting the base from the second number to obtain the second
difference;
multiplying the first difference and the second difference using the (N-l)
bit multiplier to obtain the first product;
adding the second difference to the first number to obtain the first sum;
adding the first sum to the (N-l) bits carry of the first product to obtain
the second sum;
concatenating the second sum and the (N-l) bits LSB of the first product
to obtain the result, wherein the result, the second sum forms the most
significant bits and the (N-l) bits LSB of the first product forms the least
significant bits.
2. A method according to claim 1, wherein the process is carried out in hexadecimal system.
3. A method for enabling multiplication of a first number and a second number each having up to N bits using (N-l) bit multiplier where both the numbers have equal number of bits comprising the steps of: selecting 2(N-1) as the base;
subtracting the base from the first number to obtain the first difference;
subtracting the base from the second number to obtain the second
difference;
multiplying the first difference and the second difference using the (N-l)
bit multiplier to obtain the first product;
adding the second difference to the first number to obtain the first sum;


converting the (N-1) bits LSB of the first product to 2's complement by
subtracting with base to obtain the LSB of the final product;
subtracting the (N-1) bits MSB of the first product from the first sum to
obtain the third difference;
subtracting 1 from the third difference to obtain the MSB of the final
product.
4. A method according to claim 3, wherein the process is carried out in hexadecimal system.
5. A Device for enabling multiplication of numbers with up to N bits using (N-1) bit multiplier comprising:
first subtractor means for subtracting the first number from the base,
2(N"1) to obtain the first difference;
second subtractor means for subtracting the second number from the base
to obtain the second difference;
(N-1) bit multiplier means for multiplying the first difference and the
second difference to obtain the first product;
first adder means for adding the first number and the second difference to
obtain the first sum;
second adder means for adding the first sum and (N-1) bits carry of the
first product to obtain the second sum;
concatenation means for concatenating the second sum and the (N-1) bits
LSB of the first product to obtain the final result, wherein the final result,
the second sum forms the most significant bits and the (N-1) bits LSB of
the first product forms the least significant bits.
6. A Device for enabling multiplication of numbers with up to N bits and
having unequal number of bits using (N-1) bit multiplier comprising:
first subtractor means for subtracting the first number from the base,
2(N"1) to obtain the first difference;
second subtractor means for subtracting the second number from the base to obtain the second difference;


(N-1) bit multiplier means for multiplying the first difference and the
second difference to obtain the first product;
first adder means for adding the first number and the second difference to
obtain the first sum;
third subtractor means for subtracting the (N-1) LSB of the first product
from the base to obtain the third difference;
second adder means for adding the first sum and (N-1) bits carry of the
first product to obtain the second sum;
optionally, first multiplexer to selectively output from among the third
difference and the (N-1) bits LSB of the first product to obtain the LSB
of the final product;
optionally, AND gate and XOR gate to provide a logic output for the
second sum and the most significant one bit of the final product;
optionally, fourth subtractor means for subtracting 1 from the second
sum to obtain the fourth difference;
optionally, second multiplexer means to selectively output from among
the second sum, fourth difference and the output from the AND and XOR
gates to obtain the MSB of the final product;
concatenation means for concatenating the second sum or the output of
the second multiplexer and the (N-1) bits LSB of the first product or the
output of the first multiplexer to obtain the final result, wherein the final
result, the second sum or the output of the second multiplexer forms the
most significant bits and the (N-1) bits LSB of the first product or the
output of the first multiplexer forms the least significant bits.




Abstract
Novel method and Device with reduced bit requirement for multiplication. Methods and Devices for enabling the multiplication of numbers with up to N bits using (N-1) bit multiplier. The methods employs the selection of a base, 2(N-1)and subtracting the numbers from the base. The differences are multiplied in the (N-1) bit multiplier. The (N-1) carry of (N-1) bit multiplier product is added to the sum of the first number and the second difference to obtain the MSB of the final product with the (N-1) bits portion forming the LSB of the product. The Device includes adders, subtractors and optionally, multiplexers in addition to the (N-1) bit multiplier to enable the multiplication of numbers with up to N bits.