Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-01-20
2003-02-18
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S620000, C708S625000
Reexamination Certificate
active
06523055
ABSTRACT:
CROSS REFERENCE TO MICROFICHE APPENDICES
Appendices A and B, which are part of the present disclosure, are included in a microfiche appendix consisting of three (3) sheets of microfiche having a total of one hundred eighty-nine (189) frames, and the microfiche appendix is incorporated herein by reference in its entirety. Appendices A and B are listings of computer programs including source code in the language VERILOG for a structural embodiment and a behavioral embodiment respectively of a multiplication accumulation circuit (also called “MAC”) in accordance with the invention as described more completely below.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
This invention relates to a multiplication accumulation circuit (also referred to as “MAC”) that can perform two multiplications and accumulations simultaneously, or alternatively a single multiplication and accumulation of double words.
BACKGROUND
Multiplication of two operands (typically called “multiplicand” and “multiplier”) to generate a product is well known. In a paper and pencil method taught in grammar school, the digits of the multiplier are taken one at a time from the right to the left, each digit is multiplied by the multiplicand, and the resulting product (also called “intermediate product”) is placed at an appropriate place, e.g. shifted left depending on the position of the multiplier's digit being used. After all digits of the multiplier are multiplied, all the intermediate products are added to generate the product. The following example (in binary) illustrates the paper and pencil method:
0010
two
multiplicand
×
0110
two
multiplier
+
0000
(0 in multiplier)
+
0010
(1 in multiplier)
+
0010
(1 in multiplier)
+
0000
(0 in multiplier)
0001100
two
Computers use another method, known as “Booth's algorithm” that uses just addition, subtraction and shift operations based on examining a pair of adjacent bits in the multiplier, as illustrated by the following table:
a
i
a
i−1
Operation
0
0
Do nothing; shift the
product right
0
1
Add b to product; shift the
product right
1
0
Subtract b from product,
shift the product right
1
1
Do nothing; shift the
product right
wherein &agr;
i
refers to bit i in multiplier &agr;, b is the multiplicand, and 1≦i≦4; &agr;
0
being assumed to be 0.
Booth's algorithm has been used in a multiplier that “can perform one series of multiplication of (one word) X (one word) or can simultaneously execute two series of multiplications of (half word) X (half word) under the control of a division control signal . . . ” (col. 2, lines 47-52 in U.S. Pat. No. 4,825,401 granted to Ikumi). See also U.S. Pat. No. 5,586,070 granted to Purcell for another circuit “which performs selectable multiplication operations on a first word having an upper byte and a lower byte and a second word having an upper byte and a lower byte” (abstract).
SUMMARY
A multiplication accumulation circuit (also called “MAC”) in accordance with the invention has at least two modes and depending on the mode performs at least one of the following multiplication operations in a single cycle, (1) multiplication of two pairs of single words (in a “dual mode”) or (2) multiplication of one pair of double words, (in a “double mode”). The MAC normally operates in the double mode (also called “default mode”) and goes into the dual mode when a control signal (also called “dual mode signal” is active. The dual mode signal, when active, enables a circuit (hereinafter “shifting circuit”) that is included in the MAC and that is used to shift bits of an intermediate product, as described below.
Moreover, in the same cycle the MAC also optionally adds to the resulting product (or products) another operand (e.g. value of a previous accumulation) if another control signal (also called “accumulate signal”) is active.
In one embodiment, the MAC has five input buses that carry signals for operands A, B, C, D and E, a control bus that carries signals for controlling the operations performed on the just-described operands, and an output bus that carries a signal generated by the MAC.
Operands A and B can be, respectively, the upper and lower halves of a first double word [A,B] to be used as a multiplicand. Similarly, operands C and D can be the upper and lower halves of a second double word [C,D] to be used as a multiplier. In this case, the four operands A, B, C and D are to be used as follows by the MAC: (1) to perform a single multiplication of the first double word with the second double word (in an operation called “double multiply”), and (2) to perform an addition of the product of the double multiply operation, and the fifth operand E, e.g. to generate on the output bus a signal of value [A,B]*[C,D]+E (in an operation called “double word MAC operation”).
When the accumulate signal is inactive, the MAC does not add the fifth operand, thereby providing the result of the double word multiply operation. In the double word multiply operation, the two double words [A,B] and [C,D] can be written as 2
n
*A+B and 2
n
*C+D, where n is the number of bits in an operand, so that the product has the value 2
2n
*A*C+2
n
*(A*D+B*C)+B*D.
When the dual mode signal goes active, the MAC (1) uses operands A and C to perform a first multiplication and (2) uses operand's B and D to perform a second multiplication simultaneous with the first multiplication and also (3), performs an addition of the products of the two multiplications (in an operation called “dual multiply”). Optionally (if the accumulate signal is active) the MAC adds to the two products the fifth operand E, e.g. to generate on the output bus a signal of value A*C+B*D+E (in an operation called “dual MAC operation”). If the accumulate signal is inactive, the MAC disregards the fifth operand E, and therefore generates on the output bus a signal of value A*C+B*D (in the operation called “dual multiply”).
In one embodiment, the MAC has a hardware circuit (in the form of, for example, complimentary metal oxide semiconductor (CMOS) logic gates) that performs the double word MAC operation, and the MAC uses the same hardware circuit with the shifting circuit to perform the dual MAC operation. Prior to addition of two intermediate products in the MAC, the shifting circuit right shifts the bits in one of the two products so that the shifted bits are appropriately aligned with bits in the other of the two products. In an alternative embodiment, certain hardware in the MAC performs the dual MAC operation, and the MAC uses the same hardware with the shifting circuit to perform the double word MAC operation. In the alternative embodiment, the shifting circuit left shifts the bits in one of the two products prior to addition.
Use of a shifting circuit to implement a double word MAC operation (or alternatively a dual MAC operation) as described herein requires fewer number of gates than in the prior art, because one of two separate adders otherwise required in the prior art to add the two intermediate products in the two different ways is eliminated. Moreover, the MAC can perform two multiplications and two additions of single word operands in a single cycle, as compared to two or more cycles otherwise required in the prior art (e.g. for adding the two intermediate products). Therefore, use of a shifting circuit as described herein allows the MAC to perform the double word MAC and dual MAC operations faster while using minimal hardware, as compared to a prior art device.
In one embodiment, the MAC is implemented by two multiplier units, each of which uses operands A and B as a double word multiplicand, or alternatively
Padmanabhan Satish
Shah Shailesh I.
Srivatsa Chakra R.
Yu Robert K.
Hitt Gaines & Boisbrun PC
LSI Logic Corporation
Mai Tan V.
LandOfFree
Circuit and method for multiplying and accumulating the sum... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit and method for multiplying and accumulating the sum..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit and method for multiplying and accumulating the sum... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3141822