Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-06-24
2002-07-02
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S523000
Reexamination Certificate
active
06415311
ABSTRACT:
BACKGROUND OF THE INVENTION
According to a first conventional method, a product of an unsigned multiplication A[
5
:−
2
]×B[
5
:−
2
] (e.g., 0,000 00.01
2
×1,01010.10
2
or 0.25
10
×42.5
10
) is obtained and added to an accumulator value T[
15
:
0
] (e.g., 0,00000,00010,00000.
2
=64.
10
) as follows.
The two values A[
5
:−
2
] and B[
5
:−
2
] are received by an 8×8 carry save multiplier that produces a 16-bit sum value S[
11
:−
4
] and a 16-bit carry value C[
11
:−
4
]. The sum and carry bits S[−
1
:−
4
] and C[−
1
:−
4
] that are less significant than the bits of the accumulator value T[
15
:
0
] are discarded. The sum and carry values S[
11
:
0
] and C[
11
:
0
] are extended with zero's to form values S[
15
:
0
] and C[
15
:
0
] to match the bit weights of the register value T[
15
:
0
]. Subsequently, the values S[
15
:
0
] and C[
15
:
0
] are added to register value T[
15
:
0
].
A problem with this first conventional method is that an unwanted carry out often occurs when adding sum and carry values generated by some methods such as booth recoding. Accordingly, a second conventional method of multiplying A[
5
:−
2
]×B[
5
:−
2
] which eliminates the unwanted carry out has been developed.
Specifically, the two values A[
5
:−
2
] and B[
5
:−
2
] are received by an 8×8 booth recoded carry save multiplier that produces a 16-bit sum value S[
11
:−
4
] (e.g., 00,00000,10011.0010
2
=19.125
10
) and a 16-bit carry value C[
11
:−
4
] (e.g., 11,11111,10111.1000
2
=4087.5
10
unsigned=−8.5
10
signed). The two values S[
11
:−
4
] and C[
11
:−
4
] are added in a
2
:
1
adder in a first stage to form a product P[
11
:−
4
] (e.g., 00,00000,01010.1010
2
=10.625
10
). The unwanted carry out is eliminated during this
2
:
1
addition by discarding the most significant carry bit.
Bits P[−
1
:−
4
] are also discarded and bits P[
15
:
12
] are assigned values of 0 to form product P[
15
:
0
] (e.g., 0,00000,00000,01010
2
=10
10
) thereby matching the bit weights of accumulator value T[
15
:
0
]. The product value P[
15
:
0
] is added to the accumulator value T[
15
:
0
] in a
2
:
1
adder in a second stage to form a result value T′[
15
:
0
] (e.g., 0,00000,00010,01010
2
=74
10
)
This two stage addition requires a booth recoded carry save multiplication followed by two additions in series using relatively slow
2
:
1
adders. Therefore, what is desired is a faster circuit and method for performing a booth multiplication (and adding the product to a third (e.g., accumulator) value.
SUMMARY OF THE INVENTION
A carry save multiplier receives two input values having respective bit lengths A and B and provides sum and carry values, each having bit lengths A+B+1. A carry prediction circuit receives the most significant bit of the sum and carry values and provides an extension bit to be merged with less significant bits of the sum and carry values. A carry save adder receives the altered sum and carry values, as well as a third input value to provide second sum and carry values.
In one embodiment, the second sum and carry values are added in a carry propagate adder to form a resulting value. In one embodiment, the carry prediction circuit is an XOR gate that receives the most significant bit of the first sum and carry values. In another embodiment, the circuit is an OR gate that receives the most significant bits and outputs the extension bit to be merged with the less significant bits of at least one of the first sum and first carry bits.
The present invention provides a faster circuit and method for performing a multiplication and adding the product to a third (e.g., accumulator) value.
REFERENCES:
patent: 5751619 (1998-05-01), Agarwal et al.
patent: 6073156 (2000-06-01), Purcell et al.
patent: 6081823 (2000-06-01), Purcell et al.
Patwa Nital P.
Purcell Stephen C.
ATI International Srl
Mai Tan V.
Vedder Price Kaufman & Kammholz
LandOfFree
Sign extension circuit and method for unsigned... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sign extension circuit and method for unsigned..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sign extension circuit and method for unsigned... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2857704