Patent US5128891A successfully refreshed from Google Patents.
US5128891A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High speed divider with square root capability
Assignee: Advanced Micro Devices Inc
•
Filing: 1990-04-02
•
Granted: 1992-07-07
•
Expires: 2010-04-02
Abstract
Abstract An apparatus for performing the division of a first operand by a second operand by iteratively producing a series of partial remainders and predicted quotient bits utilizing the generation of multiples of the second operand and the selection of one of the generated multiples. The second operand is first selected as a first partial remainder. A first quotient bit is predicted from the first and second operands and a next quotient bit is predicted from the partial remainder and the second operand. One of the generated multiples is selected for producing a next partial remainder based upon the next quotient prediction. A next partial remainder is then produced from the produced partial remainder and the selected multiple of the second operand.
Inventors
- 👤 Thomas W. Lynch
- 👤 Stephen D. McIntyre
- 👤 Ken Tseng
- 👤 Salim A. Shah
- 👤 Tony Hurson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 23:30
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/52; G06F7/535; G06F7/537; G06F7/5375; G06F7/544; G06F7/552; G06F7/5525; G06F2207/00; G06F2207/552; G06F2207/5526; G06F2207/5528
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
224 words
Apparatus for performing a division of a first operand by a second operand to produce a result comprised of a series of quotient bits, comprising: means for iteratively producing a series of partial remainders, said means for iteratively producing a series of partial remainders selecting said first operand as a first partial remainder; means for iteratively predicting a series of quotient bits, said quotient prediction means predicting a first quotient bit based upon said first operand and said second operand, and a next quotient bit based upon one of said series of partial remainders and said second operand; a first quotient register connected to said quotient prediction logic to receive and store said next quotient bit determined by said quotient prediction logic; a second quotient register connected to said quotient prediction logic to receive said next quotient bit and store said next quotient bit minus one; means for generating multiples of said second operand; said means for iteratively producing a series of partial remainders determining a next partial remainder based upon one of said series of produced partial remainders and one of said multiples of said second operand; said means for iteratively producing a series of partial remainders further including means for selecting, based upon said next quotient bit, one of said generated multiples of said second operand for producing said next partial remainder.
Claim 2
Dependent Claim
224 words
Apparatus for performing a division of a first operand by a second operand to produce a result comprised of a series of quotient bits, comprising: means for iteratively producing a series of partial remainders, said means for iteratively producing a series of partial remainders selecting said first operand as a first partial remainder; means for iteratively predicting a series of quotient bits, said quotient prediction means predicting a first quotient bit based upon said first operand and said second operand, and a next quotient bit based upon one of said series of partial remainders and said second operand; a first quotient register connected to said quotient prediction logic to receive and store said next quotient bit determined by said quotient prediction logic; a second quotient register connected to said quotient prediction logic to receive said next quotient bit and store said next quotient bit minus one; means for generating multiples of said second operand; said means for iteratively producing a series of partial remainders determining a next partial remainder based upon one of said series of produced partial remainders and one of said multiples of said second operand; said means for iteratively producing a series of partial remainders further including means for selecting, based upon said next quotient bit, one of said generated multiples of said second operand for producing said next partial remainder.
Claim 3
Dependent Claim
59 words
An apparatus according to claim 1 wherein said means for iteratively producing a series of partial remainders of said first operand determines said next partial remainder in accordance with the following equation: P.sub.J+1 =4P.sub.J +q.sub.j D where: P J+1 =said next partial remainder; P J =said prior partial remainder; q j =said prior quotient prediction; and D=said second operand.
Claim 4
Dependent Claim
30 words
An apparatus according to claim 2 wherein said means for generating multiples of said second operand further comprises means for generating ±0, ±1, ±2, and ±3 times said second operand.
Claim 5
Dependent Claim
61 words
An apparatus according to claim 3 wherein said means for iteratively producing a series of partial remainders of said first operand further comprises multiplexing means for selecting one of said generated multiples of said second operand for producing said next partial remainder, said selected multiple of said operand being equivalent to the product of said second operand and said quotient prediction.
Claim 6
Dependent Claim
52 words
An apparatus according to claim 4 wherein said means for generating multiples of said second operand further comprises: means for shifting said operand to produce two times said second operand; and an adder for adding said second operand and said produced two times said second operand to produce three times said operand.
Claim 7
Dependent Claim
36 words
An apparatus according to claim 1 wherein said means for iteratively producing a series of partial remainders of said first operand produces each of said series of partial remainders as a plurality of sums and carries.
Claim 8
Dependent Claim
17 words
An apparatus according to claim 6 further comprising means for determining that said result has been produced.
Claim 9
Dependent Claim
42 words
An apparatus according to claim 7 wherein said: means for determining that said result has been produced further comprises: means for determining the sign of said partial remainder; and means for adjusting said result based on the sign of said partial remainder.
Claim 10
Dependent Claim
56 words
An apparatus according to claim 8 wherein said means for iteratively producing a series of partial remainders of said first operand determines said next partial remainder in accordance with the following equation: P.sub.J+1 =4P.sub.J +QD where: P J+1 =said next partial remainder; P J =said prior partial remainder; Q=said prior quotient prediction; and D=said second operand.
Claim 11
Dependent Claim
30 words
An apparatus according to claim 9 wherein said means for generating multiples of said second operand further comprises means for generating +0, +1, +2, and +3 times said second operand.
Claim 12
Dependent Claim
57 words
An apparatus according to claim 10 wherein said means for iteratively producing a series of partial remainders further comprises multiplexing means for selecting one of said generated multiples of said second operand for producing said next partial remainder, said selected multiple of said operand being equivalent to the product of said second operand and said quotient prediction.
Claim 13
Dependent Claim
53 words
An apparatus according to claim 11 wherein said means for generating multiples of said second operand further comprises: means for shifting said operand to produce two times said second operand; and an adder for adding said second operand and said produced two times said second operand to produce three times said second operand.
Claim 14
Dependent Claim
98 words
An apparatus according to claim 12 wherein said means for iteratively predicting a series of quotient bits based upon a corresponding one of said series of partial remainders of said first operand and said second operand further comprises: a first quotient prediction circuit connected to receive said first and second operands, said first quotient prediction circuit predicting a first quotient bit; and a second quotient prediction circuit connected to receive said first predicted quotient bit, said divisor and series of partial remainders, said second quotient prediction circuit iteratively predicting the remaining bits of said series of quotient bits.
Claim 15
Independent Claim
199 words
An apparatus for dividing a dividend by a divisor to produce a result, comprising: a partial remainder register connected to receive and store said dividend as a partial remainder; a divisor register connected to receive and store said divisor; quotient prediction logic connected to receive said divisor from said divisor register and said partial remainder from said partial remainder register, said quotient prediction logic determining a quotient bit based upon said received divisor and partial remainder; a first quotient register connected to receive and store said quotient bit determined by said quotient prediction logic; means, connected to said divisor register, for generating multiples of said divisor; and a carry save adder connected to receive said multiples of said divisor from said means for generating multiples of said divisor and said predicted quotient bit from said quotient prediction logic, said carry save adder determining a next partial remainder by selecting one of said multiples of said divisor and adding it to said partial remainder, said partial remainder register connected to receive and store said next partial remainder in place of said partial remainder, said quotient prediction logic connected to receive said next partial remainder to determine a next quotient bit.
Claim 16
Independent Claim
199 words
An apparatus for dividing a dividend by a divisor to produce a result, comprising: a partial remainder register connected to receive and store said dividend as a partial remainder; a divisor register connected to receive and store said divisor; quotient prediction logic connected to receive said divisor from said divisor register and said partial remainder from said partial remainder register, said quotient prediction logic determining a quotient bit based upon said received divisor and partial remainder; a first quotient register connected to receive and store said quotient bit determined by said quotient prediction logic; means, connected to said divisor register, for generating multiples of said divisor; and a carry save adder connected to receive said multiples of said divisor from said means for generating multiples of said divisor and said predicted quotient bit from said quotient prediction logic, said carry save adder determining a next partial remainder by selecting one of said multiples of said divisor and adding it to said partial remainder, said partial remainder register connected to receive and store said next partial remainder in place of said partial remainder, said quotient prediction logic connected to receive said next partial remainder to determine a next quotient bit.
Claim 17
Dependent Claim
56 words
An apparatus according to claim 14 wherein said carry save adder produces said partial remainder as a plurality of sums and carries and said apparatus further comprises a first adder connected to receive said partial remainder from said partial remainder register, said adder adding said sums and carries to determine whether said result has been produced.
Claim 18
Dependent Claim
33 words
An apparatus according to claim 15 further comprising a second adder connected to receive said partial remainder from said partial remainder register, said second adder determining the sign of said sums and carries.
Claim 19
Dependent Claim
47 words
An apparatus according to claim 16 wherein said quotient prediction logic further determines, for every quotient bit determined, the quotient bit minus one, said apparatus further comprising a second quotient register connected to receive and store said quotient bit minus one determined by said quotient prediction logic.
Claim 20
Dependent Claim
48 words
An apparatus according to claim 17 further comprising: means for determining whether said quotient bit stored in said first quotient register is off by one; and means for replacing said quotient stored in said first quotient register by said quotient minus one stored in said second quotient register.
Claim 21
Dependent Claim
21 words
An apparatus according to claim 18 further comprising an output latch connected to receive said quotient from said first quotient register.
Claim 22
Dependent Claim
91 words
An apparatus according to claim 19 wherein said dividend, said divisor and said result are each comprised of a mantissa portion and an exponent portion, said quotient being produced by dividing the mantissas of said dividend and said divisor and said apparatus further comprising exponent calculation means connected to receive the exponents of said dividend and said divisor, said exponent calculation means subtracting said divisor exponent from said divident exponent to determine said result exponent, said output latch being further connected to receive said result exponent from said exponent calculation means.
Claim 23
Dependent Claim
57 words
An apparatus according to claim 16 further comprising: first shifting means connected to receive said divisor for producing two times said divisor; a third adder connected to receive two times said divisor from said first shifter and said divisor; and a second divisor register connected to receive and store three times said divisor from said second adder.
Claim 24
Dependent Claim
46 words
An apparatus according to claim 21 further comprising a first multiplexer connected to receive said divisor from said divisor register and three times said divisor from said second divisor register and to output +0, +1, +2, and +3 times said divisor to said carry save adder.
Claim 25
Dependent Claim
49 words
An apparatus according to claim 22 wherein said carry save adder determines a next partial remainder in accordance with the following equation: P.sub.J+1 =4P.sub.J +q.sub.j D where: P J+1 =said next partial remainder; P J =said prior partial remainder; q j =said prior quotient prediction; and D=said second operand.
Claim 26
Dependent Claim
45 words
An apparatus according to claim 23 wherein said carry save adder further comprises: second shifting means for shifting said partial remainder twice to produce four times said partial remainder; and means for selecting one of said inputs from said multiplexer based upon said quotient prediction.
Claim 27
Dependent Claim
45 words
An apparatus according to claim 24 wherein said carry save adder produces said next partial remainder by adding said partial remainder shifted twice to produce four times said partial remainder and said multiplexer input equal to the product of said divisor and said quotient prediction.
Claim 28
Dependent Claim
48 words
An apparatus according to claim 14 further comprising: a first multiplexer connected to receive said divisor, said multiplexer including shifter means for producing two times said divisor from said divisor; and a first adder connected to receive two times said divisor from said multiplexer means and said divisor.
Claim 29
Dependent Claim
25 words
An apparatus according to claim 26 further comprising a second divisor register connected to receive and store three times said divisor from said second adder.
Claim 30
Dependent Claim
70 words
An apparatus according to claim 26 further wherein said first multiplexer is further connected to receive said plurality of sums and carries from said partial remainder register, said multiplexer configured to selectively output either said divisor to said first adder for said determination of three times the divisor or said plurality of sums and carries to said first adder for determining said partial remainder sign and final remainder zero detect.
Claim 31
Dependent Claim
40 words
An apparatus according to claim 28 further comprising an output latch connected to receive said quotient from said quotient register, said output latch further connected to receive signals from said first adder indicative of whether said partial remainder is zero.
Claim 32
Dependent Claim
40 words
An apparatus according to claim 29 further comprising means for providing a return path for said addition of said sums and carries output from said first adder back to said first adder to determine the sign of said partial remainder.
Claim 33
Dependent Claim
22 words
An apparatus according to claim 30 further comprising means for providing said determined sign of said partial remainder to said output latch.
Claim 34
Dependent Claim
47 words
An apparatus according to claim 31 wherein said quotient prediction logic further determines, for every quotient bit determined, the quotient bit minus one, said apparatus further comprising a second quotient register connected to receive and store said quotient bit minus one determined by said quotient prediction logic.
Claim 35
Dependent Claim
73 words
An apparatus according to claim 32 further comprising: square root prediction logic connected to receive a radicand from said adder, said square root prediction logic determining a predicted root bit based upon said radicand; means for providing said predicted root bit to said first quotient register and said first multiplexer; said multiplexer iteratively providing two times said predicted root bit to said square root prediction logic for determining a next predicted root bit.
References Cited (Backward Citations)
US4075704A
Cited
US4546447A
Cited
US4688186A
Cited
US4722069A
Cited
US4683547A
Cited
US4724529A
Cited
US4939686A
Cited
US4878190A
Cited
US4979142A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-07-07 | 1996-01-06 | 1996-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-07-07 | 2000-01-06 | 2000-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-07-07 | 2004-01-06 | 2004-07-07 | $7700.00 | Window Closed / Lapsed |