Patent ID: 7660842

Claim:
A circuit that performs a carry-save division operation, wherein the carry-save division operation divides a numerator, N, where N=C*R, by a denominator, D, to produce an approximation of a quotient, Q=N/D, the circuit comprising: circuitry for approximating Q iteratively, and circuitry for performing selection logic, wherein: the circuitry for approximating Q iteratively is configured to approximate Q by iteratively selecting an operation to perform based on higher order bits of a remainder, r, and then performing the operation; wherein K defines the ranges for R, D, and C, such that R lies in [−2 K+1 , 2 K+1 ), D lies in [2 K , 2 K+1 ), and C lies in [0, 2 K+1 ); wherein L defines the desired accuracy in the computed quotient, Q, such that the error in the approximated Q is less than 2 L ; wherein the number of iterations performed, n, initialized as n=0, and incremented by 1 after each iteration, depends on the relationship, n−=K+L+2; wherein q, the quotient calculated thus far is maintained in a carry-save form, wherein the carry-save form involves maintaining a sum component, q 0 , and a carry component, q 1 ; and the remainder, r, is maintained in a carry-save form, wherein the carry-save form involves maintaining a sum component r 0 , and a carry component, r 1 , such that s 0 is the most significant bit of r 0 , s 0 is the negation of s 0 ; s 1 is the second most significant bit of r 0 , s 1 is the negation of s 1 , c 0 is the most significant bit of r 1 , c 0 is the negation of c 0 ; c 1 is the second most significant bit of r 1 ; and c 1 is the negation of c 1 ; and the circuitry for performing selection logic is configured to determine the value of the logic relationship, s 0 ·s 1 ·c 0 ·c 1 + s 0 · s 1 ·c 0 ·c 1 ; wherein the circuitry for approximating Q iteratively is further configured such that: when the value returned by the circuitry for performing selection logic for the logic relationship, s 0 ·s 1 ·c 0 ·c 1 + s 0 · s 1 ·c 0 ·c 1 , is true, then the circuitry for approximating Q iteratively performs an operation on the higher order bits of the remainder, r, wherein r is related to the quotient calculated thus far, q, and a coefficient, c, by the relationship, q*D+c*r=N; wherein the operation involves multiplying both r 0 and r 1 by 2, and dividing c by 2; and wherein after the iterations are complete, performing a carry completion addition that adds q 0 and q 1 to produce Q in a non-redundant form; whereby the operation eliminates the need for carry propagation and thereby speeds up the division operation.