Dividers:Subtract-and-Shift Dividers.

Introduction

There are two major classes of division methods: subtract-and-shift methods and multiplicative methods. For details of division methods and dividers, see Refs. 2, 5–11, and also Ref. 3 for subtract-and-shift division. Suppose two binary numbers, X and Y, are normalized in the range equal to or greater than 1/2 but smaller than 1 and also X < Y holds for the sake of simplicity. Then, a dividend X = [0.1x2 … xn], which is an n-bit normalized binary fraction, is to be divided by a divisor, Y = [0.1y2 … yn], which is another n-bit normalized binary fraction, where each of xi and yi takes a value of 0 or 1. We assume to calculate the quotient Z = [0.1z2 … zn] which satisfies |X/Y – Z | < 2–n, where zi takes a value of 0 or 1.

Subtract-and-Shift Dividers

The subtract-and-shift divider works in a manner similar to manual division of one decimal number by another, using paper and pencil. In the case of manual division of decimal numbers, each xi of dividend X and yi of divisor Y is selected from {0, 1, … , 9} (i.e., the radix is 10). Each zi of quotient Z is selected from {0, 1,…, 9}. In the following case of dividers for a digital system, dividend X and divisor Y are binary numbers, so each xi of X and yi of Y is selected from {0, 1}, but the quotient (which is not necessarily represented as a binary number) is expressed in radix r. The radix r, is usually chosen to be 2k (i.e., 2, 4, 8, and so on.) So, a quotient is denoted with Q = [0.q1q2 … q én/kù], to be differentiated from Z = [0.1z2 … zn] expressed in binary numbers, although both Q and Z will henceforth be called quotients.

The subtract-and-shift method with a radix r iterates the recurrence step of replacing Rj by r · Rj–1 – qj ·Y, where qj is the j-th quotient digit and Rj is the partial remainder after the determination of qj. Initially, Rj –1 for j – 1 = 0; that is, R0 is X. Each recurrence step consists of the following four substeps. Suppose that r = 2k.

1. Shift of the partial remainder Rj –1 to the left by k bit positions to produce r · Rj –1.

2. Determination of the quotient digit qj by quotient-digit selection.

3. Generation of the divisor multiple qj · Y.

4. Subtraction of qj · Y from r · Rj –1 to calculate Rj .

The dividers for a digital system have many variations, depending on the methods in choosing the radix, the quotient-digit set from which qj is chosen (qj is not necessarily 0 or 1, even if it is in radix 2), and the representation of the partial remainder. The simplest cases are with a radix of 2 and the partial remainder represented in the non-redundant form. When r = 2, the recurrence is Rj = 2Rj –1 – qj · Y. There are three methods: the restoring, the non-restoring, and the SRT methods.

Restoring Method

In the radix-2 restoring method, a quotient digit, qj, is chosen from the quotient-digit set {0, 1}. When 2Rj –1 – Y ³ 0 (2Rj –1 means shift of Rj –1 by one bit position to the left), 1 is selected, and otherwise 0 is selected. Namely, Rj¢ = 2Rj –1 – Y is calculated first, and then, when Rj¢ ³ 0 holds, we set qj =1 and Rj = Rj¢, and otherwise qj = 0 and Rj = Rj¢ + Y (i.e., Y is added back to Rj¢). For every j, Rj is kept in the range, 0 £ Rj < Y. The j-th bit of the quotient in binary number Z = [0.1z2 …zn], zj, is equal to qj (i.e., zj is the same as qj in radix 2 in this case of the restoring method). This method is called the restoring method, because Y is added back to Rj¢ when Rj¢ < 0. For speed-up, we can use 2Rj –1 as Rj by keeping Rj –1, instead of adding back Y to Rj¢, when Rj¢ < 0. Figure 43.1 shows an example of radix-2 restoring division.

Non-Restoring Method

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 = 1. 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.111111] where 1 denotes –1, we have Z = [0.110011]. (The given number [0.111111] 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 1’s by 1’s in the given number is subtracted from the number derived by replacing all 1’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 43.2 shows an example of radix-2 non-restoring 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 Figures 43.1 and 43.2, where R6 = 1 in Figure 43.2 indicates that the remainder is negative.)

Figure 43.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.

SRT Method

In the radix 2 SRT method, the quotient-digit set is {–1, 0, 1}. In this case, –1 or 0 or 1 is selected as qj , based on whether 2Rj –1 < –(1/2) or –(1/2) £ 2Rj –1 < (1/2) or (1/2) £ 2Rj –1. When 0 is selected as qj, no addition or subtraction is performed for the calculation of Rj, and hence, the computation time may be shortened. Quotient digit qj is determined from the values of the three most significant bits (shown in each of the dot-lined rectangles in Figure 43.4) of 2Rj –1, as the radix-2 SRT division is exemplified in Figure 43.4. Rj –1 satisfies –Y £ Rj –1 < Y and is represented in a two’s complement representation with 1-bit integral part (and n-bit fractional part).

In the above three methods, carry (or borrow) propagates in the calculation of Rj in each recurrence step because the partial remainder is represented in the non-redundant form. We can accelerate the SRT method by using a redundant form for representing the partial remainder, and performing the calculation of Rj without carry (or borrow) propagation. Let us consider the use of the carry save form. Rj, which satisfies –Y £ Rj < Y, is represented in a two’s complement carry save form with 1-bit integral part (and n-bit fractional part.) (In the two’s complement carry save form, both the partial carry and the partial sum are represented in the two’s complement representation.) In this case, –1 or 0 or 1 is selected as qj, based on whether 2Rˆ j –1 £ –1 or 2Rˆ j –1 = –(1/2), or 2Rˆ j –1 ³ 0, where 2Rˆ j –1 denotes the value of the three most significant digits (shown in each of the dot-lined rectangles in Figure 43.5), i.e., down to the

first binary position, of 2Rj –1. Note that 2Rˆ j–1 £ 2Rj –1 < 2Rˆ j –1 + 1. Figure 43.5 shows an example of radix-2 SRT division with the partial remainder represented in the carry save form.

In the radix-2 SRT method with the partial remainder represented in the carry save form, as in the original SRT method, the conversion of the quotient into the ordinary binary representation is required because the quotient is represented in the redundant binary representation with digit set {–1, 0, 1}. There is a method called the on-the-fly conversion [4] that performs the conversion without carry propagate addition. It converts the quotient on-the-fly as quotient digits are produced. Expressing the bits up to the j-th of Q and Z as Qj = [0.q1q2 … qj] and Zj = [0.z1z2 … zj] respectively, Zj is the ordinary binary representation of Qj or that of Qj – 2– j. The latter is the case when the remaining (lower) part of Qn is negative. Therefore, we can obtain Z immediately after qn is determined (i.e., all quotient digits are determined), by holding the ordinary binary representation of Qj and that of Qj – 2–j at each recurrence step. Let them be ZPj and ZNj, respectively. At each step, ZPj and ZNj are calculated as follows. When qj = –1, ZPj = ZNj –1 + 2–j and ZNj = ZNj –1. When qj = 0, ZPj = ZPj –1 and ZNj = ZNj –1 + 2–j. When qj = 1, ZPj = ZPj –1 + 2–j and ZNj = ZPj –1. In any case, each calculation of ZPj and ZNj is performed by a selection of ZPj –1 or ZNj –1 and a concatenation of 0 or 1. Figure 43.6 shows an example of on-the-fly conversion.

Figure 43.7 shows a radix-2 SRT divider with a carry save adder. Register For Partial Carry For Rj –1 and Register For Partial Sum For Rj –1 together store partial remainder Rj –1 represented in the carry save form, i.e., by two binary numbers, partial carry, and partial sum. The three most significant bits of these two registers are fed to the Quotient-Digit Selector, which produces qj. Divisor Multiple Generator generates Y, 0, or –Y, based on whether qj is –1, 0, or 1. Shift Registers For Zj –1 consists of two shift registers for storing ZPj –1 and ZNj –1 and two selectors controlled by qj.