1. Field of the Invention
This invention relates to binary division. More particularly, this invention relates to binary division of the type that is accomplished by repeated subtraction using multiples of the divisor.
2. Related Art
Binary division, as performed by digital computers, has been conventionally accomplished by iteratively subtracting multiples of the divisor from a partial dividend. By performing division in such a manner, multiple bits of the quotient can be developed in each iteration, thus saving a significant number of machine cycles over the course of a divide operation.
In a typical divide iteration, the following operation is performed: EQU Rn=PDn-Mn*D
where
R.sub.n =remainder at the end of iteration n PA1 PD.sub.n =partial dividend at the start of iteration n PA1 D=divisor (1/2.ltoreq.D.ltoreq.1) PA1 M.sub.n =divide multiple used in iteration n PA1 (An "*" indicates multiplication)
For a 2-bit divide, PD.sub.n+1 =4*R.sub.n (left shift of two bits). If M.sub.n is restricted to the values -2, -1, 0, +1, +2 then, EQU .vertline.R.sub.n /D.ltoreq.2/3, or .vertline.PD.sub.n /D-M.sub.n .vertline..ltoreq.2/3
Therefore, once the ratio of PD.sub.n /D is know, the divide multiple M.sub.n can be determined by Table I:
TABLE I ______________________________________ Xn = PDn/D Mn ______________________________________ 4/3 .ltoreq. X.sub.n .ltoreq. 8/3 2 1/3 .ltoreq. X.sub.n .ltoreq. 5/3 1 -2/3 .ltoreq. X.sub.n .ltoreq. 2/3 0 -5/3 .ltoreq. X.sub.n .ltoreq. -1/3 -1 -8/3 .ltoreq. X.sub.n .ltoreq. -4/3 -2 ______________________________________
Further, Q.sub.n can be determined by the relationships of Table II:
TABLE II ______________________________________ Mn Qn(Rn &gt; or = 0) Qn(Rn &lt; 0) ______________________________________ 2 2 1 1 1 0 0 0 3 -1 3 2 -2 2 1 ______________________________________
As indicated above, a typical divide operation will include two serial operations: 1) determine M.sub.n from PD.sub.n /D; 2) determine R.sub.n by R.sub.n =PD.sub.n -M.sub.n *D. In prior techniques it has been shown that Mn+1 can be generated in parallel with Rn. Hence, the iteration time is limited by generating Rn. Conventionally, M.sub.n is determined by providing both PD.sub.n and D to decoders (one for negative PDn values and a separate decoder for positive PD.sub.n values) and determining M.sub.n by using look up tables.
To determine M.sub.n, only the high-order bits of PD.sub.n and D are needed. Since PD.sub.n =4R.sub.n-1 =4(PD.sub.n -1-M.sub.n-1 *D), the higher order bits of PD.sub.n (designated PD.sub.n ') can be generated in parallel with PD.sub.n from the higher order bits of PD.sub.n-1 and M.sub.n-1 *D. The PD.sub.n ' so generated ignores the carry-in from the lower order bits. This error can be compensated for by selecting the multiple boundary in the overlapped region between the multiples. Since: ##EQU1## Therefore, the high-order bits of PD.sub.n (PD.sub.n), and hence Mn, can be determined from PD.sub.n-2, M.sub.n-2, and M.sub.n-1.
The quotient bits Q.sub.n (2 bits per iteration) are determined by the relations: EQU Q.sub.n =M.sub.n if C.sub.n =1, Q.sub.n =M.sub.n -1 if C.sub.n =0
where C.sub.n is a carry out bit indicative of the sign of the remainder (R.sub.n).
An example of an apparatus for performing non-restoring division and embodying the foregoing principles is illustrated in FIG. 1. FIG. 1 depicts a fixed point binary divider 100. Data locations refer to the start of the nth iteration. The remainder from the previous iteration n-1 is latched into the remainder latch 102 of the carry propagate adder 104. The last carry (off the end of the remainder) is used by the quotient generator 106 to generate Qn-1, since Qn-1=Mn-1-Cn-1, where Cn-1 represents the last carry that occurred. Cn-1 indicates the sign of Rn-1 (1 if negative, 0 if positive) and is generated by counting carries out of the carry propagate adder 104. This covers the case where Qn-1=Mn-1 -1. Mn-1 is represented by two's compliment form in the multiple latches 108. The quotient generator 106 is a two-bit down counter and binary trigger.
The last remainder Rn-1 wraps back on the carry propagate adder 104 through a two-bit wired left shift 110 to become PDn. Mn*D feeds the other side of the carry propagate adder from the multiple gates 112. The multiple gates form 1X or 2X divisor multiples in true or compliment form from the divisor register 114 as selected by the multiple select lines 116. The multiple select lines generate the extra carry into the adder (hot one) when a two's compliment divisor is selected.
The last remainder (left shifted by 2 bits) also feeds the ratio decoder adder 118 which resolves its high order bits, along the high order bits of Mn*D into the high order bits of Rn. The high order bits of Rn, shifted left by two bits to form PDn+1, feed two ratio decoders 120, 122 that select a positive and negative Mn+1 from the ratio of PDn+1 to the divisor D. The carry-out of the multiple decoder adder indicates the sign of PDn+1, and is used to select the opposite signed Mn+1 from the multiple latch drivers 124. The selected Mn+1 is then latched into the quotient multiple latches 108 and is ready for the next iteration.
In the divider of FIG. 1, the sign of Rn-1 is formed by counting the carries out of the carry propagate adder with a binary trigger, and the sign of PDn+1 is formed by waiting for the carry out of the decoder adder 118. In any event, either method can be used as determined by the adder organization. The initial dividend is not shown in FIG. 3. A typical hardware saving location for the initial dividend is the quotient register 126 (by time-sharing).
As explained above, two ratio decoders are provided. A positive ratio decoder 120 and a negative ratio decoder 122. The two separate decoders are provided because the positive and negative regions are not completely symmetrical. That is to say, for a given divisor, the proper value of Mn where the partial dividend PDn is positive will not necessarily be the same as where the partial dividend PDn is of the same magnitude but negative. This principle is illustrated in the charts of FIGS. 2A and 2B.
Horizontally on each chart are plotted partial dividend values in sixteenths while divisor values are plotted vertically in sixteenths. The chart of FIG. 2A represents positive partial dividends and the chart of FIG. 2B represents negative partial dividends.
Within each chart there are four slanted lines referred to as exact "boundaries." The exact boundaries 202-216 represent the four possible ratios of PDn/D which are of interest in decoding Mn and were taken from Table I. The crooked lines 218, 220 near the 2/3 and 5/3 exact boundaries represent the nearest integer ratio whose magnitude is less than or equal to the exact ratio. In the decoder adder 118, PD and D are represented to a bit position weight of 64 (thus the low order bit of PDn+1 as available to the decoder has a weight of sixteen). Thus each square on the chart represents a possible ratio between PD.sub.n+1 and D which can be seen by the ratio decoders.
The positive and negative regions as delimited by the integer boundaries are not symmetrical. The negative region really shows the 1's compliment form of the partial dividend and is therefore off by one bit. The boundary regions, however, where two multiples overlap are equal in the positive and negative region.
In the chart for the positive partial dividends, the point in the upper left corner of each square represents the bit patterns of PD.sub.n+1 and D, while the exact ratio of that particular PD.sub.n+1 to D is represented by any point within the square or on its upper or left boundary.
Overlap of multiple ranges for some values of PDn/D (see the bottom of FIG. 2) permits some flexibility in choosing the decode boundary for a particular multiple. However, much of the flexibility is lost because of the error introduced by ignoring the carry into the lowest bit position of PD.sub.n in the decoder adder 118. For example, the positive decoder 120 for multiple zero must select on all bit patterns of PD.sub.n and D as represented by squares to the left or cut by the one-third exact boundary. A line which is drawn through the right most extreme of these squares would be referred to as the one-third integer boundary. Because of the overlap in the range for selection of M.sub.n =0 and M.sub.n =1, the decoder for M.sub.n =0 could select on any square between the one-third and two thirds boundaries. But because the carry-in error may permit PD.sub.n to be low by one bit, the multiple zero decoder may not select on any square which is just to the left of the two thirds integer boundary. The dashed lines represent the left edge of those squares whose bit patterns are decoded to select M.sub.n =1. The remaining squares in the upper range are then decoded to select M.sub.n =2.
The negative ratio decoder 122 (the decoder for negative partial dividends) is derived in a similar manner. The truncation and carry-in errors in this case are toward the zero partial dividend so that the point at the upper left corner of each square represents the bit pattern seen by the decoder. The dashed lines represent the left edges of the squares selected for Mn=-1. The Mn=0 line is shown to imply the right edge for Mn=-1.
In the ratio decoders 120, 122 and the tables of FIG. 2, the variables are defined as divisor=0,1xyz and partial dividend=ab.cdef.
While the divider of FIG. 1 has provided a successful mechanism for performing non-restoring binary division it does have a number of features which are open for improvement. For example, having separate decoders for the positive and negative partial dividend regions does not make for an efficient integrated circuit real estate. Further, in some instances, the implementation of these decoders can create engineering limitations on the speed of division.