Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reissue Patent
2001-08-17
2004-01-13
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S626000
Reissue Patent
active
RE038387
ABSTRACT:
CROSS-
REFERENCE TO RELATED APPLICATION
This application claims foreign priority from European Patent No.
94830581
.
8
, filed Dec.
22
,
1994
.
TECHNICAL FIELD
This invention relates to multiplier circuits for accomplishing operations with binary numbers, and in particular, to a monolithically integratable multiplier circuit which can be used in integrated circuit microprocessors or microcontrollers.
BACKGROUND OF THE INVENTION
Among the circuits for carrying out arithmetical operations of multiplication, multipliers having a typical, iterative structure or architecture known as a “cellular array” have been found to be especially advantageous.
Assuming that two integers expressed in natural binary form with 4 parallel-supplied bits are to be multiplied together,
A=a
3
*2
3
+a
2
*2
2
+a
1
*2+a
0
B=b
3
*2
3
+b
2
*2
2
+b
1
*2+b
0
then the product is,
A*B=b
0
(a
3
*2
3
+a
2
*2
2
+a
1
*2+a
0
)+2b
1
(a
3
*2
3
+a
2
*2
2
+a
1
*2+a
0
)+4b
2
(a
3
*2
3
+a
2
*2
2
+a
1
*2+a
0
)+8b
3
(a
3
*2
3
+a
2
*2
2
+a
1
*2+a
0
)
Therefore, the product of A by B is obtained by adding together the partial products wherein the terms making up the following matrix appear:
a
3
b
0
a
2
b
0
a
1
b
0
a
0
b
0
a
3
b
1
a
2
b
1
a
1
b
1
a
0
b
1
a
3
b
2
a
2
b
2
a
1
b
2
a
0
b
2
a
3
b
3
a
2
b
3
a
1
b
3
a
0
b
3
There are several different types of algorithms whereby the sum of the partial products thus computed can be reckoned. Iterative array multipliers consist of a combinatorial network which performs this addition with a delay which is only dependent on the time required to go through the various logic circuits.
The computation of the matrix of partial products is accomplished using a combinatorial network of logic AND gating circuits whereby all the matrix bits are obtained simultaneously with just the delay of a simple logic product. If the size of the operands is of n bits, then n*n AND gates will be required.
There are several circuit architectures that can provide the sum of the individual logic products making up the partial product matrix. Of considerable import is Dadda's algorithm, described in an article entitled “Some Schemes for Parallel Multipliers”, Alta Frequenza, Vol. XXXIV, No. 5, May 1965, which yields the sum of the individual partial products by compressing the matrix columns, that is progressively reducing the number of the rows which make up the partial product matrix by adding together the bits in one column until two rows only are obtained whose sum, representing the result of the multiplication, is obtained using a fast adder. Thus, the multiplier is composed of three parts: the matrix structure of AND gates which is to compute the partial products, the circuit for compressing the columns, and the final adder.
For effecting the column compression portion of the procedure, parallel counters may be used, that is components which will count the number of bits equal to 1 present at their inputs; where two inputs only are provided, these would be so-called Half-Adders (“HA”), whereas with three inputs provided, these would be so-called Full Adders (“FA”). However, they may also be defined for any number of inputs greater than three.
Dadda uses both FAs and HAs in his multiplier, and shows that the best method (i.e., that requiring the smallest number of cells) consists of compressing the columns such that the number of rows which make up the partial product matrix decreases in accordance with the following recursive formula:
d(0)=2
d(k+1)=3/2d(k)
where, d(i) is the number of rows in the i-th stage, and k is the number of stages required for the reduction.
Thus, the following series is generated:
k
0
1
2
3
4
5
6
7
8
9
d(k)
2
3
4
6
9
13
19
28
42
63
For example, in the 8×8 case, the initial number (8) of the rows must be reduced to 6, 4, 3, and ultimately 2; accordingly, 4 stages are required.
The algorithm provides for the use of FAs and HAs arranged in a structure which ensures that no more than d(k) rows exist in the k-th stage.
Also described in the article is Wallace's block diagram, and reflections are offered on the parallel adders used in binary number multipliers.
In another, more recently published article by L. Dadda, entitled “On Parallel Digital Multiplier”, Alta Frequenza, Vol. XLV, No. 10, October 1976, the parallel implementation of the adders is dealt with, using “fast” storage elements to provide high-speed digital multipliers.
The technique employed for multiplying natural binary numbers may also be used for relative numbers, expressed in binary form, by representing the negative value numbers in the two's complement binary form. The necessary add operation is carried out by two's complementing the negative terms. This allows the complexity of the arithmetic circuits of a processor to be greatly reduced and, accordingly, the speed of operation increased.
Known are natural number multipliers, two's complement binary number multipliers, and multipliers which either enable two natural binary numbers or two's complement binary numbers to be multiplied together.
However, there is an unmet need in the art for a multiplier circuit for accomplishing multiplication operations with two binary operands, each operand either in the natural or two's complement form, as desired.
SUMMARY OF THE INVENTION
The present invention provides a multiplier circuit that performs multiplication operations with two binary operands, either of which may be in natural or twos complement form. This is achieved without prejudice for the high-speed and design simplicity features of conventional multiplier circuits, in particular Dadda's circuits.
A multiplier circuit multiplies together both natural and two's complement binary numbers, which it receives in the form of electric signals having predetermined logic values, that are applied to input terminals of logic gating circuits. The logic gating circuits provide partial products of the bits of the two binary factors, and a combinatorial network provides the final sum of such partial products. The partial multiplications that include at least one of the more significant bits of the operands are performed by logic gating circuits which can be enabled to also carry out a two's complement partial multiplication. The multiplier circuit further includes additional logic gating circuits which supply the combinatorial network with additive constants with predetermined logic values unrelated to the factors.
REFERENCES:
patent: 4153938 (1979-05-01), Ghest et al.
patent: 5121352 (1992-06-01), Hesson
patent: WO 91/19249 (1991-12-01), None
Montuschi, Paolo et al., “n×n Carry-Save Multipliers without Final Addition,” inProc. 11thSymposium on Computer Arithmetic, IEEE Computer Society IEEE Technical Committee on VLSI, Windsor, Ontario, Canada, Jun. 29-Jul. 2, 1993, pp. 54-61.
Roth, Jr., “Fundamentals of Logic Design,”Second Edition, 1979, Chapters 8.4-8.6, p. 164-170.
Costa Raffaele
Faldarini Anna
Formenti Laura
Mai Tan V.
STMicroelectronics S.r.l.
Tarleton E. Russell
LandOfFree
Multiplier circuit for multiplication operation between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiplier circuit for multiplication operation between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplier circuit for multiplication operation between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3252764