Source: http://www.google.com/patents/US5289399?dq=inassignee:Temic
Timestamp: 2015-04-02 03:26:26
Document Index: 591703646

Matched Legal Cases: ['arts 1', 'art 1', 'art 1', 'art 2', 'art 2', 'arts 1']

Patent US5289399 - Multiplier for processing multi-valued data - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA multiplier, which is capable of processing a multiplication of multi-valued data, includes a register transforming circuit (RC) for shifting data stored and outputting a plurality of data, a multiplying circuit connected to the register transforming circuit (RC) for multiplying the outputs from the...http://www.google.com/patents/US5289399?utm_source=gb-gplus-sharePatent US5289399 - Multiplier for processing multi-valued dataAdvanced Patent SearchPublication numberUS5289399 APublication typeGrantApplication numberUS 07/984,695Publication dateFeb 22, 1994Filing dateDec 2, 1992Priority dateDec 6, 1991Fee statusPaidPublication number07984695, 984695, US 5289399 A, US 5289399A, US-A-5289399, US5289399 A, US5289399AInventorsYukihiro YoshidaOriginal AssigneeSharp Kabushiki KaishaExport CitationBiBTeX, EndNote, RefManPatent Citations (5), Referenced by (7), Classifications (12), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetMultiplier for processing multi-valued data
US 5289399 AAbstract
A multiplier, which is capable of processing a multiplication of multi-valued data, includes a register transforming circuit (RC) for shifting data stored and outputting a plurality of data, a multiplying circuit connected to the register transforming circuit (RC) for multiplying the outputs from the register transforming circuit (RC) and an adding circuit connected to the multiplying circuit for adding the multiplied results according to a predetermined arithmetic rule based on logic to be used. The multiplier further includes an AND circuit element connected to the adding circuit for shifting and sending out the outputs from the adding circuit. A W register is connected to the adding circuit for storing the shifted outputs from the adding circuit according to the AND circuit element, and a further AND circuit element is connected to the W register for shifting and sending out the outputs from the W register. Another AND circuit element is connected to the further AND circuit element for further shifting the outputs from the further AND circuit element. Finally, a W register is connected to the further AND circuit element for storing the shifted output from the W register.
1. An apparatus for processing a multiplication of multi-valued data, comprising:register means for shifting data stored therein and outputting said shifted data therefrom; multiplying means connected to said register means for multiplying said shifted data output from said register means to produce multiplied results; adding means connected to said multiplying means for adding said multiplied results according to a predetermined arithmetic rule based on logic to be used; and means for shifting said added results output from said adding means and for outputting said shifted results. 2. An apparatus according to claim 1, wherein said shifting means includes a first shifting means connected to said adding means for shifting said added results output from said adding means and for outputting said shifted results.
11. A multiplier which is capable of processing a multiplication of multi-valued data, comprising:register means for shifting data stored and outputting a plurality of data; multiplying means connected to said register means for multiplying said outputs from said register means to produce multiplied results; adding means connected to said multiplying means for adding said multiplied results according to a predetermined arithmetic rule based on logic to be used; first shifting means connected to said adding means for shifting and sending out said outputs from said adding means; first register connected to said adding means for storing said shifted outputs from said adding means according to said first shifting means; second shifting means connected to said first register for shifting and sending out said outputs from said first register; third shifting means connected to said second shifting means for further shifting said outputs from said second shifting means; and second register connected to said second shifting means for storing said shifted output from said first register. 12. An apparatus according to claim 11, wherein said stored data is a binary signal.
15. A multiplier which is suitable to process multi-valued data comprising:register means for shifting data stored therein and for outputting said shifted data; a plurality of first data output means for outputting first data based on a predetermined arithmetic rule based on logic to be used; a plurality of multiplication means connected to said register means and said first data output means for multiplying an output from said register means and an output from said first data output means; a plurality of second data output means for outputting second data based on a predetermined arithmetic ruled based on logic to be used; and a plurality of addition means connected to said multiplication means for adding an output from said multiplication means, an output from said second data output means and a specific input altogether, and for outputting said added result to another second data output means located adjacent to said second data output means. 16. A multiplier according to claim 15, wherein an addition means located at an end of said plurality of addition means is capable of adding an output of said multiplication means and said specific input, and outputting said added result to said second data output means located adjacent to said adding means.
It is therefore an object of the present invention to provide a multiplier which can apply to multi-valued signals such as a binary signal and a quadruple signal, and which can perform stably a high-speed multiplication.
FIG. 1 is a block diagram showing a 2-bit parallel and serial type multiplier according to a first embodiment of the invention;
Referring to the accompanying drawings, an embodiment of a multiplier according to the present invention will be described in detail.
In the arrangement shown in FIG. 1, a multiplication and an addition are performed in a 2-bit parallel manner at each time t2i-1 (i=1, 2, 3, . . . , n). Thereby, a time margin φ is yielded at a time t2i. This means that the multiplication and the addition are required to be performed only once at each 2φ.
Then, the serial outputs X1 and X2 of the XO register 28 and the XE register 29 and the serial outputs Y1 and Y2 of the YO register 37 and the YE register 38 are input to the multiplying circuit 39.
As shown in FIG. 3, the multiplier is arranged to have a register circuit RC, an X1 -bit circuit X1 to an X2n -bit circuit X2n, multiplying circuits M1 to Mn, a W1 -bit circuit W1 to a W2n -bit circuit W2n, and adding circuits A1 to An.
Likewise, the YE register 52 is connected to the OR circuit element 50. The X1 -bit circuit X1 to X2n -bit circuit X2n operate to output the first data X1 to X2n based on the predetermined method.
The multiplying circuits M1 to Mn are connected to the register circuit RC and the X1 -bit circuit X1 to the X2n -bit circuit X2n so that those multiplying circuits M1 to Mn perform a multiplication of the output of the register circuit RC and each output of the X1 -bit circuit X1 to the X2n -bit circuit X2n. The W1 -bit circuit W1 to W2n -bit circuit W2n operate to output the second data W1 to W2n based on the predetermined method.
The adding circuits A1 to An are connected to the multiplying circuits M1 to Mn so that each adding circuit performs an addition of each output of the multiplying circuits M1 to Mn, each output of the W3 -bit circuit W3 to the W2n -bit circuit W2n and each particular input C'1 to C'n-1 and then outputs the added result to the W1 -bit circuit W1 to the W2n -bit circuit W2n located adjacently to the adding circuits A1 to An, respectively.
At a first multiplying stage, the multiplying circuit M1 is connected to the X1 -bit circuit X1, the X2 -bit circuit X2, the YO register 51 and the YE register 52.
At a second multiplying stage, the multiplying circuit M2 is connected to the X3 -bit circuit X3, the X4 -bit circuit X4, the YO register 51, the YE register 52 and the multiplying circuit M1.
At a third multiplying stage, the multiplying circuit M3 is connected to the X5 -bit circuit X5, the X6 -bit circuit X6, the YO register 51, the YE register 52, and the multiplying circuit M2.
At an i-th multiplying stage, the multiplying circuit Mi is connected to the X2i-1 -bit circuit X2i-1, the X2i -bit circuit X2i, the YO register 51, the YE register 52 and the multiplying circuit Mi-1.
At an (n-1)th multiplying stage, the multiplying circuit Mn-1 is connected to the X2n-3 -bit circuit X2n-3, the X2n-2 -bit circuit X2n-2, the YO register 51, the YE register 52, and the multiplying circuit Mn-2.
At an n-th multiplying stage, the multiplying circuit Mn is connected to the X2n-1 -bit circuit X2n-1, the X2n -bit circuit X2n, the YO register 51, the YE register 52, and the multiplying circuit Mn-1.
Turning to the adding stages, at a first adding stage, the adding circuit A1 is connected to the W1 -bit circuit W1, the W2 -bit circuit W2, the W3 -bit circuit W3, the W4 -bit circuit W4 and the multiplying circuit M1.
At a second adding stage, the adding circuit A2 is connected to the W3 -bit circuit W3, the W4 -bit circuit W4, the W5 -bit circuit W5, the W6 -bit circuit W6 and the multiplying circuit M2.
At a third adding stage, the adding circuit A3 is connected to the W5 -bit circuit W5, the W6 -bit circuit W6, the W7 -bit circuit W7, the W8 -bit circuit W8, and the multiplying circuit M3.
At an i-th adding stage, the adding circuit Ai is connected to the W2i -bit circuit W2i, the W2i-1 -bit circuit W2i-1, the W2i+2 -bit circuit W2i+2, the W2i+1 -bit circuit W2i+1 and the multiplying circuit Mi.
At an (n-1)th adding stage, the adding circuit An-1 is connected to the W2n-2 -bit circuit W2n-2, the W2n-3 -bit circuit W2n-3, the W2n -bit circuit W2n, the W2n-1 -bit circuit W2n-1 and the multiplying circuit Mn-1.
At an n-th adding stage, the adding circuit An is connected to the W2n -bit circuit W2n, the W2n-1 -bit circuit W2n-1 and the multiplying circuit Mn.
When performing a multiplication of n-bits�n-bits, the known full-bit binary parallel multiplier needs an operating time for processing 2n bits, because the length of one word is n bits and the multiplied result is 2n bits. On the other hand, the multiplier shown in FIG. 3 needs an operating time of only n bits even if the multiplication of two n-bit words is performed. That is, the multiplying speed is half as long as that of the known multiplier. It means that the operating speed is kept constant if the physical clock frequency is reduced to a half.
Consider an expansion of the method used in the multiplier shown in FIG. 3. In performing a parallel multiplication on a 4-bit unit=24 (16 values), when multiplying two n-bit words, the expanded multiplication needs a multiplying time of (n/4) bit-time and an adding time of (n/4) bit-time. Hence, the overall time is an (n/2) bit-time. That is, the overall multiplying speed of the expanded method is made four times as fast as that of known multiplier.
In performing the parallel multiplication on the 3-bit unit=23 (8 values), the expanded multiplication needs a multiplying time of (n/3) bits and an adding time of (n/3) bits, though a redundant bit may take place. Hence, the overall time is an (2 n/3) bit-time. That is, the overall multiplying time of the expanded method is made three times as fast as that of known multiplier.
In FIG. 7, Λ denotes an AND circuit and V denotes an OR circuit.
In the logic circuit of the multiplier, X0, X1/3, X2/3, X1, Y0, Y1/3, Y2/3, Y1, C0, C1/3, and C2/3 denote equivalent circuits. That is, when an X input is 0, 1/3, 2/3 or 1, the output becomes 1. This holds true to Y. For C, when an input is 0, 1/3 or 2/3, the output becomes 1.
If the binary logic is used, in FIG. 8, X0, X1/3, X2/3, X1, Y0, Y1/3, Y2/3, Y1, C0, C1/3, and C2/3 denote the logically same but physically different circuit from those used in the logic circuit of the multiplier.
The equivalent logic (X≡0), (X≡1/3), (X≡2/3) and (X≡1) are represented by X0, X1/3, X2/3 and X1. Likewise, the equivalent logic (Y≡0), (Y≡1/3), (Y≡2/3) and (Y≡1) are represented by Y0, Y1/3, Y2/3 and Y1. The equivalent logic (C≡0), (C≡1/3) and (C≡2/3) are represented by C0, C1/3 and C2/3.
The outputs Z2 and Z1 of the multiplier and the carrier outputs C2 and C1 are indicated in the charts 1 and 2.
______________________________________chart 1C0       C1/3     C2/3X0  X1/3        X2/3              X1                   X0                       X1/3                            X2/3                                X1                                     X0                                         X1/3                                              X2/3                                                  X1______________________________________Y0                   1   1    1   1    2   2    2                        2                        Y1/3  1 2 3 1 2 3  2 3  1                        Y2/3  2  2 1 3 1 3 2  2                        Y1  3 2 1 1  3 2 2 1  3______________________________________
The chart 1 also represents the logic expression of the output <Z> of the multiplier. To correspond to 0. 1, 2 and 3 of <Z>, (Z2, Z1) indicates (0, 0), (0, 1) (1, 0) or (1, 1). The blanks in the chart indicate 0
______________________________________chart 2C0       C1/3     C2/3X0  X1/3        X2/3              X1                   X0                       X1/3                            X2/3                                X1                                     X0                                         X1/3                                              X2/3                                                  X1______________________________________Y0                        Y1/3        1   1 1                        Y2/3   1 1   1 1  1 1 2                        Y1   1 2  1 1 2  1 2 2______________________________________
The chart 2 also represents the logic expression of the carry output <C>. To correspond to 0, 1, and 2 of <C>, (C2, C1) indicates (0, 0), (0, 1) and (1, 0). The blanks in the chart indicate 0.
If the multiplier is configured of the output <Z> and the carry output <C>, the resulting multiplier is the circuit shown in FIG. 10.
The multiplier shown in FIG. 10 performs a multiplication in a 2-bit parallel manner at each time t2i-1 (i=1, 2, 3, . . . , n). The multiplying output <Z> indicated in the charts 1 and 2, that is, the logic expression of (Z2, Z1) is logically multiplied by a time t2i-1.
Likewise, the carry output <C>, that is, (C2, C1) is logically multiplied by a time t2i-1. This operation is used for the logic converting circuit shown in FIG. 7 or the binary input circuit shown in FIG. 8. The carry output <C> takes place at the time t2i and is added to the multiplied output at the next t2i-1. C2 t2i and C1 t2i are ORed into the OR circuit element.
(Z2, Z1) of the multiplying output <Z> is input to the logic converting circuit shown in FIG. 11 or the binary input circuit shown in FIG. 12 and is used in the adding circuit shown in FIG. 9.
The multiplier according to this invention can commonly apply to the quadruple logic and the binary logic. In actuality, it employs either one. However, the combination of both logic can be used. In addition, considering that the carry output (C2, C1) may take place at the 2n-th bit (final bit), C2 t2n+1 and C1 t2n+1 are ORed with the output (Z2, Z1).
In the foregoing full 2-bit parallel and serial multiplier, each of the XO register 28, the XE register 29, the YO register 37, and the YE register 38 has the bit-shifting arrangement as shown in FIG. 13. Herein, XO denotes Xodd, XE denotes XEven, YO denotes Yodd and YE denotes YEven.
In the multiplying circuit shown in FIG. 14, a carry takes place at the time ti and is added to the multiplied output about the next bit, so that the carry output <C>, that is, (C2, C1) is made to have the arrangement shown in FIG. 14. Further, since the carry is output at the time tn+1 (i=1, 2, 3, . . . , n), C2 tn+1 and C1 tn+1 are ORed with the output (Z2, Z1).
In the adding circuit shown in FIG. 16, the carry takes place at the time ti and is added to the added output about the next bit. Hence, the carry output C" appears as shown in FIG. 16. Considering that the carry is output at the time tn+1, C"tn+1 is ORed with W'.
In the adding circuit shown in FIG. 22, considering that a carry may take place at the most significant bit, C'n is ORed with W2i-1.
Since the adding circuit shown in FIG. 22 performs the parallel operation, C'i-1 denotes a carry output from the previous stage and C'i denotes a carry input to the next stage. In the multiplying circuit shown in FIG. 20, C2i-2 and C2i-3 shown in FIGS. 21 and 24 are carry outputs from the previous stage. C2i and C2i-1 are carry inputs to the next stage. The carry outputs C2n, C2n-1 at the final stages 2n and 2n-1 are ORed with the output <Z>, that is, (Z2i, Z2i-1).
X�Y=W�4x+y                          (2)
Assuming that a sign bit of X is Xs, a sign bit of Y is Ys, indicating code bits of x, y as xs, ys, respectively, then a code Ws of the mantissa can be represented by the following expression.
Ws =Xs &#8853;Ys                              (3)
The exponents are listed in the following table 2, wherein x≧0 and y≧0:
TABLE 2______________________________________xsys      P         Ps______________________________________0    0      x + y    --    0    --    0    --    00    1      x - y    x &gt; y 0    x = y 0    x &lt; y 11    0     -(x - y)  x &gt; y 1    x = y 0    x &lt; y 01    1     -(x + y)  --    1    --    1    --    1______________________________________
wherein p denotes an exponent of a mantissa W of the multiplied result and ps denotes a sign bit of p.
The foregoing operation may be represented by the flowchart shown in FIG. 27. In the flowchart, p+1→ p is executed, because the carry may take place from the most significant digit by multiplying the mantissa X by the mantissa Y. This flowchart (steps S1 to S13) and the circuit arrangement for implementing the operation illustrated in the flowchart are allowed to be implemented by the known means. Hence, the description about them is left out.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3617723 *Feb 25, 1970Nov 2, 1971Collins Radio CoDigitalized multiplierUS3805043 *Oct 11, 1972Apr 16, 1974Bell Telephone Labor IncSerial-parallel binary multiplication using pairwise additionUS4796219 *Jun 1, 1987Jan 3, 1989Motorola, Inc.Serial two's complement multiplierUS5021987 *Aug 31, 1989Jun 4, 1991General Electric CompanyChain-serial matrix multipliersJPS5938849A * Title not available* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5438533 *Sep 13, 1993Aug 1, 1995Sharp Kabushiki KaishaMultivalued multiplier for binary and multivalued logic dataUS5463573 *Nov 16, 1993Oct 31, 1995Sharp Kabushiki KaishaMultivalued subtracter having capability of sharing plural multivalued signalsUS5524088 *Apr 6, 1994Jun 4, 1996Sharp Kabushiki KaishaMulti-functional operating circuit providing capability of freely combining operating functionsUS5740344 *Feb 8, 1996Apr 14, 1998Itri-Industrial Technology Research InstituteTexture filter apparatus for computer graphics systemUS7562106Dec 20, 2004Jul 14, 2009Ternarylogic LlcMulti-value digital calculating circuits, including multipliersUS8209370May 27, 2009Jun 26, 2012Ternarylogic LlcMulti-value digital calculating circuits, including multipliersWO2001011538A2 *Aug 7, 2000Feb 15, 2001Patil Preeth KumarDiscrete computer system* Cited by examinerClassifications U.S. Classification708/493, 708/627International ClassificationG06F7/506, G06F7/523, G06F7/49, G06F7/52, G06F7/483, G06F7/527Cooperative ClassificationG06F7/49, G06F7/533European ClassificationG06F7/533, G06F7/49Legal EventsDateCodeEventDescriptionJul 27, 2005FPAYFee paymentYear of fee payment: 12Aug 2, 2001FPAYFee paymentYear of fee payment: 8Aug 11, 1997FPAYFee paymentYear of fee payment: 4Feb 2, 1993ASAssignmentOwner name: SHARP KABUSHIKI KAISHA, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNOR:YOSHIDA, YUKIHIRO;REEL/FRAME:006446/0885Effective date: 19921212RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services