Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-03-02
2002-02-12
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S628000
Reexamination Certificate
active
06347326
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of computing devices, and in particular to the field of binary multiplication.
2. Description of Related Art
The representation of negative numbers in a binary number system can take a variety of forms. Two common representations are sign-magnitude (SM), and twos complement (2's). In the sign-magnitude representation, a sign-bit is used to represent the algebraic sign of the number, and an independent set of bits are used to represent the magnitude of the number. In the twos complement representation, negative numbers are represented as the result of a subtraction of the magnitude of the number from zero. That is, in a four bit system, for example, a negative 2 is represented as the result of 0000 minus 0010, which is 1110 (the borrow, or carry, produced by the subtraction is ignored). The twos complement representation has the advantageous characteristic that additions and subtractions of twos complement numbers can be effected without regard for whether the numbers being added or subtracted are positive or negative. That is, the addition of 5 (0101) to a negative 2 (1110) is 3 (0011) (the borrow, or carry, produced by the addition is ignored). The sign-magnitude representation requires a specific consideration of the sign bit of each number to determine whether, for example, an “addition” is actually a subtraction of magnitudes depending upon the sign of each number being added. That is, the addition of 5 (+0101) to a negative 2 (−0010) is effected by subtracting 2 (0010) from 5 (0101) to produce a magnitude of 3 (0011). The sign of the result also requires a comparison of the magnitudes of each number as well.
The sign-magnitude representation, on the other hand, is well suited for multiplication, while the twos complement representation cannot be used directly to perform multiplication. FIG.
1
illustrates the problem. Shown in
FIG. 1
is the binary multiplication of the binary numbers 1010 and 0111 to produce the binary product 01000110. As is common in the art, the multiplication of two numbers is often performed as a sequence of sub-multiple multiplications, so as to allow the use of a smaller, less costly, multiplier. In general, an N×M bit multiplication is effected by a sequence of N/j×M/k bit multiplications, where N, M, j, k, N/j, and M/k are integers. That is, for example, the multiplication of two 32 bit numbers can be preformed as a sequence of repeated 16 bit multiplications (N/2×M/2), or a sequence of 16 bit by 8 bit multiplications (N/2×M/4), and so on. The results of each sub-multiplication are accumulated, appropriately shifted dependent upon the place of the submultiples, to form the product.
FIG. 1
illustrates the multiplication of the two four-bit numbers (4×4 bit multiplication) as a sequence of two-bit submultiple multiplications (4/2×4/2 bit multiplications). The submultiples of the two number N
1
, N
2
being multiplied are identified as H
1
, L
1
, and H
2
, L
2
respectively. The H and L notations are used to signify high-order and low-order submultiples, respectively. In binary form, the value of the binary submultiple L
1
is 11, and the value of the binary submultiple L
2
is 10. The product of L
1
and L
2
is identified as L
1
*L
2
in
FIG. 1
, and has the value 0110. In decimal magnitude form, the value of L
1
(11) is 3, the value of L
2
(10) is 2, and the product of L
1
and L
2
(0110) is 6. In like manner, the product of submultiples L
1
(11) and H
2
(10) is identified as L
1
*H
2
in
FIG. 1
, and has the value of (0110) shifted left two places (011000), corresponding to the place of H
2
being two places to the left.
The product of submultiples H
1
(01) and L
2
(10) is identified as H
1
*L
2
in
FIG. 1
, and has the value of (0010) shifted left two places (001000), corresponding to the place of H
1
being two places to the left. The product of submultiples H
1
(01) and H
2
(10) is identified as H
1
*H
2
in
FIG. 1
, and has the value of (0010) shifted left four places (00100000), corresponding to the place of H
1
and H
2
each being two places to the left.
In decimal magnitude form, the value of subproducts L
1
*L
2
(0110), L
1
*H
2
(011000), H
1
*L
2
(001000), and H
1
*H
2
(00100000) are 6, 24, 8, and 32, respectively. The sum of these binary subproducts is 01000110, which in decimal form is 70, the product of the numbers N
1
(7) and N2 (10). That is, if the binary numbers 0111 and 1010 represent decimal magnitudes 7 and 10, the sum of the products of their submultiples accurately represents their product as a decimal magnitude, 70.
In twos complement form, however, the binary numbers 0111 and 1010 represent decimal values 7 and −6, respectively. The binary product of these two binary numbers, 01000110, does not, however, accurately represent their product, −42.
Conventionally, the multiplication of twos complement numbers is effected by first converting the twos complement numbers into sign-magnitude form, and multiplying the magnitudes. If the signs of the multiplicands differ, the product of the magnitudes is converted to a negative number in twos complement form.
FIG. 2
illustrates this process, using the same multiplicands as in FIG.
1
. The twos complement representation (1010) of −6 is converted to a negative sign S
1
, and a magnitude of 6 (0110 ). The twos complement representation (0111) of 7 is converted to a positive sign S
2
, and a magnitude of 7 (0111). The binary product of 0111 (7) and 0110 (6) is 01000110 (42). Because the sign S
1
, S
2
of the multiplicands differ, the product 01000110 (42) is converted to the negative of 01000110 in twos complement form 11010110, thereby producing the proper result, −42 in twos complement form.
Note that the twos complement conversion is applied to the original four-bit wide number, and thereafter the multiplication is effected on the narrower two-bit wide submultiples. As noted above, narrower operations consume less area of circuitry, and therefore are less costly, than wider operations (the terms wide and narrow are used herein to describe the number of bits comprising a number, independent of the magnitude of the number, a wide number having more bits than a narrow number). The conversions of a wide number between twos complement form and sign-magnitude form is time consuming, and the circuitry required to effect the conversions is area consuming. Therefore, a need exists for a device or process that allows for the multiplication of twos complement numbers that does not require a wide twos complement conversion.
BRIEF SUMMARY OF THE INVENTION
It is an object of this invention to provide a process and device that allows for the multiplication of twos complement numbers without a wide conversion to and from twos complement form. This object and others are achieved by partitioning the operands of an N×M bit multiplication into N/j+1 bit and M/k+1 bit submultiples, respectively. The most significant submultiple is assigned the sign of the operand, while each of the less significant submultiple is assigned a positive sign. The product of each submultiple pair is sign extended to the width of the product (N+M), and the accumulation of these sign extended submultiple products provides the product of the original twos complement operands, in twos complement form.
REFERENCES:
patent: 4722068 (1988-01-01), Kuroda et al.
patent: 4761756 (1988-08-01), Lee et al.
patent: 4860240 (1989-08-01), Hartly et al.
patent: 5153850 (1992-10-01), Williams
patent: 5181184 (1993-01-01), Shim et al.
patent: 5467296 (1995-11-01), Suzuki
patent: 6014684 (2000-01-01), Hoffman
Bouwmeester Hans Adrianus
Currie Kenneth David
Jensen Rune Hartung
Spanjaart Hans Albert
Malzahn David H.
Philips Electronics North America Corporation
LandOfFree
N bit by M bit multiplication of twos complement numbers... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with N bit by M bit multiplication of twos complement numbers..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and N bit by M bit multiplication of twos complement numbers... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2977824