US4939686A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for shared radix 4 division and radix 4 square root
Assignee: Weitek Corp
•
Filing: 1989-05-30
•
Granted: 1990-07-03
•
Expires: 2009-05-30
Abstract
Abstract An improved logic structure and a method for implementing the same to perform division and square-root operations for radix four and higher is disclosed. The divsion and square-root bits are generated by a non-restoring method with the partial remainder, partial radicand, quotient and root all in redundant form. The partial remainder/radicand is stored in a series of sum and carry registers. The upper bits from these registers are supplied to a carry look-ahead adder for conversion to non-redundant form. These upper bits are then used to select a next divisor or root from a prediction programmable logic array (PLA). The output of the prediction PLA is supplied to a quotient/root register and a divisor/root multiple selector. The output of the selector is supplied to a carry save adder which has its output provided back to the input of the partial remainder/radicand sum and carry registers. The system of the present invention allows both division and square root calculations to be done with the same hardware. The square-root algorithm requires an initial look-up PLA for determining the initial bits of the square-root. Logic is provided for coupling the output of this initial look-up PLA to the quotient/root register and divisor/root multiple select during the first few iterations.
Inventors
- 👤 Jan Fandrianto
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 18:51
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/4824
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
157 words
An apparatus for performing division and calculating a square root comprising: partial remainder/radicand register means for storing a partial remainder or radicand in sum and carry form; a carry save adder having an input coupled to an output of said partial remainder/radicand register means and an output coupled to an input of said partial remainder/radicand register means; quotient/root register means for storing a quotient or root and having an output coupled to said carry save adder; a carry look-ahead adder coupled to receive a plurality of the upper bits from said partial remainder/radicand register means; prediction look-up table means, having an input coupled to said carry look-ahead adder and an output coupled to said quotient/root register means, for producing a predicted next divisor or root; and initial look-up table means, having an input coupled to receive a radicand and an output coupled to said quotient/root register means, for producing an initial plurality of digits of a root.
Claim 2
Independent Claim
157 words
An apparatus for performing division and calculating a square root comprising: partial remainder/radicand register means for storing a partial remainder or radicand in sum and carry form; a carry save adder having an input coupled to an output of said partial remainder/radicand register means and an output coupled to an input of said partial remainder/radicand register means; quotient/root register means for storing a quotient or root and having an output coupled to said carry save adder; a carry look-ahead adder coupled to receive a plurality of the upper bits from said partial remainder/radicand register means; prediction look-up table means, having an input coupled to said carry look-ahead adder and an output coupled to said quotient/root register means, for producing a predicted next divisor or root; and initial look-up table means, having an input coupled to receive a radicand and an output coupled to said quotient/root register means, for producing an initial plurality of digits of a root.
Claim 3
Dependent Claim
31 words
The apparatus of claim 1 further comprising a complementor coupled between said carry look-ahead adder and said prediction look-up table means for complementing any negative outputs of said carry look-ahead adder.
Claim 4
Dependent Claim
32 words
The apparatus of claim 1 further comprising a multiplexer for coupling one of the outputs of said prediction look-up table means and said initial look-up table means to said quotient/root register means.
Claim 5
Dependent Claim
60 words
The apparatus of claim 3 further comprising a divisor/root multiple selector means, coupled to an output of said multiplexer and an output of said quotient/root register, for shifting and complementing an output of said quotient/root register with the amount of the shift being determined by the output of said multiplexer and providing said shifted/complemented output to said carry save adder.
Claim 6
Dependent Claim
18 words
The apparatus of claim 1 further comprising a shifter coupled to the output of said carry save adder.
Claim 7
Dependent Claim
23 words
The apparatus of claim 1 further comprising a full mantissa width carry look-ahead adder coupled to an output of said carry save adder.
Claim 8
Dependent Claim
14 words
The apparatus of claim 1 wherein said look-up table means comprise programmable logic arrays.
Claim 9
Dependent Claim
22 words
The apparatus of claim 1 wherein said quotient/root register means includes means for storing said quotient/root register in Q and Q-1 forms.
Claim 10
Dependent Claim
18 words
The apparatus of claim 1 wherein said initial look-up table provides the initial 5 bits of a root.
Claim 11
Dependent Claim
187 words
A method for performing division using the apparatus of claim 1 comprising the steps of: (a) providing a dividend and a divisor; (b) producing a partial remainder from said dividend and said divisor; (c) converting an upper plurality of bits of said partial remainder into sign and magnitude form using a carry look-ahead adder; (d) using a prediction look-up table to predict the next quotient bits from said upper plurality of bits of said partial remainder in sign and magnitude form; (e) shifting and complementing said divisor in accordance with the output of said prediction look-up table; (f) combining the result of step (e) and said partial remainder in a carry save adder; (g) shifting the result of step (f) to give a new partial remainder; (h) repeating steps (c)-(g) for a plurality of iterations to provide a predetermined precision number; (i) determining the Q and Q-1 forms of the result of step (h); (j) determining the sign of the remainder after said iterations; and (k) selecting one of said Q and Q-1 forms in accordance with the sign of said remainder to provide a final quotient.
Claim 12
Independent Claim
224 words
A method for calculating a square root comprising the steps of: (a) providing a radicand to an initial look-up table; (b) providing an initial 2 bits from said initial look-up table to a quotient/root register and a divisor/root multiple selector; (c) shifting and complementing the output of said quotient/root register in accordance with said 2 bits from said initial look-up table and providing the result to a carry save adder; (d) shifting the output of said carry save adder and providing the shifted output of said carry save adder to a partial remainder/radicand register; (e) repeating steps (b)-(d) for a next 2 bits from said initial look-up table; (f) repeating steps (b)-(d) for a final bit from said initial look-up table; (g) converting a plurality of the upper bits of said partial remainder/radicand register into sign and magnitude form and providing the magnitude to a prediction look-up table; (h) providing the output of said prediction look-up table to said quotient/root register and said divisor/root multiple selector; (i) shifting and complementing the output of said quotient/root register in accordance with the output of said prediction look-up table and providing the result to said carry save adder; shifting the output of said carry save adder and providing said output back to said partial remainder/radicand register; and (k) repeating steps (g)-(j) above for a plurality of iterations.
Claim 13
Independent Claim
224 words
A method for calculating a square root comprising the steps of: (a) providing a radicand to an initial look-up table; (b) providing an initial 2 bits from said initial look-up table to a quotient/root register and a divisor/root multiple selector; (c) shifting and complementing the output of said quotient/root register in accordance with said 2 bits from said initial look-up table and providing the result to a carry save adder; (d) shifting the output of said carry save adder and providing the shifted output of said carry save adder to a partial remainder/radicand register; (e) repeating steps (b)-(d) for a next 2 bits from said initial look-up table; (f) repeating steps (b)-(d) for a final bit from said initial look-up table; (g) converting a plurality of the upper bits of said partial remainder/radicand register into sign and magnitude form and providing the magnitude to a prediction look-up table; (h) providing the output of said prediction look-up table to said quotient/root register and said divisor/root multiple selector; (i) shifting and complementing the output of said quotient/root register in accordance with the output of said prediction look-up table and providing the result to said carry save adder; shifting the output of said carry save adder and providing said output back to said partial remainder/radicand register; and (k) repeating steps (g)-(j) above for a plurality of iterations.
Claim 14
Independent Claim
294 words
An apparatus for performing division and calculating a square root comprising: partial remainder/radicand register means for storing a partial remainder or radicand in sum and carry form; a carry save adder having an input coupled to an output of said partial remainder/radicand register means and an output coupled to an input of said partial remainder/radicand register means; quotient/root register means for storing a quotient or root in Q and Q-1 forms and having an output coupled to said carry save adder; a carry look-ahead adder coupled to receive a plurality of the upper bits from said partial remainder/radicand register means; prediction look-up table means, having an input coupled to said carry look-ahead adder and an output coupled to said quotient/root register means, for producing a predicted next divisor or root; initial look-up table means, having an input coupled to receive a radicand and an output occupied to said quotient/root register means, for producing an initial plurality of digits of a root; a complementor coupled between said carry look-ahead adder and said prediction look-up table means for complementing any negative outputs of said carry look-ahead adder; a multiplexer for coupling one of the outputs of said prediction look-up table means and said initial look-up table means to said quotient/root register means; a divisor/root multiple selector means, coupled to an output of said multiplexer and an output of said quotient/root register means, for shifting and complementing an output of said quotient/root register means with the amount of the shift being determined by the output of said multiplexer and providing said shifted/ complemented output to said carry save adder; a shifter coupled to the output of said carry save adder; and a full mantissa width carry look-ahead adder coupled to an output of said carry save adder.
Claim 15
Independent Claim
294 words
An apparatus for performing division and calculating a square root comprising: partial remainder/radicand register means for storing a partial remainder or radicand in sum and carry form; a carry save adder having an input coupled to an output of said partial remainder/radicand register means and an output coupled to an input of said partial remainder/radicand register means; quotient/root register means for storing a quotient or root in Q and Q-1 forms and having an output coupled to said carry save adder; a carry look-ahead adder coupled to receive a plurality of the upper bits from said partial remainder/radicand register means; prediction look-up table means, having an input coupled to said carry look-ahead adder and an output coupled to said quotient/root register means, for producing a predicted next divisor or root; initial look-up table means, having an input coupled to receive a radicand and an output occupied to said quotient/root register means, for producing an initial plurality of digits of a root; a complementor coupled between said carry look-ahead adder and said prediction look-up table means for complementing any negative outputs of said carry look-ahead adder; a multiplexer for coupling one of the outputs of said prediction look-up table means and said initial look-up table means to said quotient/root register means; a divisor/root multiple selector means, coupled to an output of said multiplexer and an output of said quotient/root register means, for shifting and complementing an output of said quotient/root register means with the amount of the shift being determined by the output of said multiplexer and providing said shifted/ complemented output to said carry save adder; a shifter coupled to the output of said carry save adder; and a full mantissa width carry look-ahead adder coupled to an output of said carry save adder.
References Cited (Backward Citations)
US3631230A
Cited
US3733477A
Cited
US4320464A
Cited
US4477879A
Cited
US4607343A
Cited
US4722069A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-07-02 | 1994-01-01 | 1994-07-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-07-02 | 1998-01-01 | 1998-07-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-07-02 | 2002-01-01 | 2002-07-03 | $7700.00 | Window Closed / Lapsed |