ABSTRACT
In the radix-2 non-restoring method, a quotient digit, qj is chosen from the quotient-digit set {–1, 1}. Quotient digit qj is chosen according to the sign of Rj – 1. In other words, we set qj = 1 when Rj – 1 ≥ 0 and, otherwise, we set qj = –1, abbreviated as qj = . Then, Rj = 2Rj – 1 – qj · Y is calculated. Even if Rj is
negative, Y is not added back in this method, so this method is called the non-restoring method. Note that since we have R0 = X > 0 and (1/2) ≤ X < Y < 1 by the assumption, we always have q1 = 1 and R1 = 2R0 – Y = 2X – Y > 0, and hence, q2 = 1. For every j, Rj is kept in the range, –Y ≤ Rj < Y. The j-th bit of the quotient in binary number Z = [0.1z2…zn], zj, is 0 or 1, based on whether qj + 1 is –1 or 1. And we have always zn = 1. For example, when Q = [0.111 1] where denotes –1, we have Z = [0.110011]. (The given number [0.111 1] is calculated as [0.111001] – [0.000110] = [0.110011]. In other words, the number derived by replacing all 1’s by 0’s and all ’s by 1’s in the given number is subtracted from the number derived by replacing all ’s by 0’s in the given number. This turns out to be a simple conversion between zj and qj + 1, as stated above, without requiring the subtraction.) Combining this conversion with the recurrence on Rj yields the method in which R1 = 2X – Y, and for j ≥ 2, when Rj – 1 ≥ 0, zj – 1 = 1 and Rj = 2Rj – 1 – Y and, otherwise, zj – 1 = 0 and Rj = 2Rj – 1 + Y. Figure 40.2 shows an example of radix-2 nonrestoring division. Note that the remainder for the restoring method is always negative, whereas the remainder for the non-storing method (also the SRT method to be described in the following) can be negative, and consequently when the remainder is negative, the quotient of the latter is greater by 2-n
than the former. (This explains the difference between the quotients in Figs. 40.1 and 40.2, where R6 = 1 in Fig. 40.2 indicates that the remainder is negative.)
Figure 40.3 shows a radix-2 non-restoring divider that performs one recurrence step in each clock cycle. Register For Partial Remainder Rj – 1 initially stores the dividend X and then, during the division, stores a partial remainder Rj – 1 which may become negative. Divisor, Y, in Register For Divisor Y is added to or subtracted from the twice of the Rj – 1 stored in Register For Partial Remainder Rj – 1 by Adder/Subtracter, based on whether the left-most bit of Register For Partial Remainder Rj – 1 (i.e., the sign bit of Rj – 1) is 1 or 0, and then the result (i.e., Rj) is stored back into Register For Partial Remainder Rj – 1. Concurrently, the complement of the sign bit of Rj – 1 (i.e., zj – 1) is fed to Shift Register For Zj – 2 (which stores the partial quotient Zj – 2 = [0.1z2…zj – 2]) from the right end, and the partial quotient stored in Shift Register For Zj –2 is shifted one position to the left. The divider performs one recurrence step in each clock cycle. After n cycles, Shift Register For Zj -2 holds the quotient Z. We can use any carry propagate adder (subtracter) as the Adder/Subtracter. The faster the adder, the shorter the clock cycle, and hence, the faster the divider.
