Method for finding quotient in a digital system

This is a continuation of application Ser. No. 08/188,068 filed Jan. 26, 1994 now abandoned.

The present invention relates to a method for finding a quotient, especially to a method for finding a quotient in a digital system by signed-digit operation.

Inherently, division operation is a sequential operation. The quotient digits are produced only after the sign of the remainder have been detected. As a result, division operation is much slower than multiplication operation. Efforts have been put in speeding up the division operation. It is noted that the SRT algorithm (C. V. Freiman, “Statistical Analysis of Certain Binary division algorithms,” Proc. IRE, Vol. 49, January 1961, pp. 91-103; K. Hwang, Computer Arithmetic: Principles, Architectures, and Design, 1979, pp. 222-223) eliminates the restoring operations of the partial remainders. Another algorithm disclosed by K. Hwang in the aforementioned article confines the quotient digits either to be 1 or −1, depending on the signs of remainder. However, the bottleneck of those algorithms lies in sign detection of the remainder. Fast addition algorithms such as CLA (carry-lookahead addition) shorten the operation time, but results in complex hardware structures. The aforementioned articles of C. V. Freiman and K. Hwang are hereby incorporated herein by reference.

Recently, division algorithm based on SD (signed-digit) number representation was proposed which is much faster than the previous algorithm (s. Kuninobu et al., “Design of High Speed MOS Multiplier and Divider Using Redundant Binary Representation,” IEEE Proceeding of Symposium on Computer Arithmetic, 1987, pp. 80-86). This algorithm considerably shortens the time for remainder subtraction by using carry-propagation-free SD addition. However, it is much more complex because in each iteration the SD algorithm must check three most significant digit (MSD) bits of the remainder to decide the quotient digit in the set of {−1, 0, 1}, and then perform the SD addition. Moreover, the final SD result must be converted to binary representation. Also note that the signed-digit addition is more complicated than the conventional carry-save adder (CSA).

Another type of algorithms entirely avoids the slow subtract-detect-shift type of operation previously mentioned. They transform the division operation to a series of multiplication operations that converge to the original quotient. Among the examples are the constant convergence (S. Waser and M. J. Flynn, Introduction to Arithmetic for Digital Systems Designers, New York: CBS College Publishing, Chap. 5, 1982) and quadratic convergence (P. Markenstein, “Computation of Elementary Functions on the IBM RISC System/6000 Processor,” IBM Journal of Research and Development, Vol. 34, 1990, pp. 111-119; D. A. Patterson and J. L. Hennessy, Computer: A Quantitative Approach, San Mateo, Calif., Morgan Kaufman, 1990) division algorithms which are based on Newton-Raphson algorithm. They are often found in multiplier-based processors. They are still sequential type of operation to certain degree, and obviously require much more shift-and-add operations.

There is an on-line division algorithm that facilitates serial/serial division operation (K. S. Trivedi and M. D. Ercegovac, “On-Line Algorithms for Division and Multiplication,” IEEE Trans. on Computers, Vol. C-26, No. 7, July 1977). This algorithm has advantages such as that: (a) it is pipelined at digit level; (b) all operands and results are communicated digit serial, and (c) result digits are on-line obtained after a few initial delay. On the other hand, among some of its disadvantages are: (a) it requires more complex three-input signed-digit addition operation; (b) it needs more complicated quotient decision circuit for range detection of the remainder, and (c) output results have to be converted to binary representations.

In this work, a fast radix-2 division algorithm and its architecture is proposed. The algorithm adheres to the shift/subtract-and-add type of division operation. The key idea behind this algorithm is to separate the sign detection operation of remainder from the remainder subtraction operation. By taking the absolute values of the remainders, we can successively subtract the remainders without the need of knowing the signs of remainders, while signs of the remainders can be decided in parallel and independently at the same time. To enhance the algorithm's performance, several design techniques were incorporated into its architecture realization.

The new algorithm and its architecture retain as many of the advantages of the mentioned algorithms as possible, and simultaneously gets rid of their disadvantages. The algorithm adopts non-restoring division operation and CSA type of operation for fast subtraction. Quotient digit set of {1, −1{ is assumed for fast quotient conversion to binary representation. The algorithm is also an on-line algorithm that facilitates highly pipelined operation while it is much simpler than the existing on-line algorithms.

This object of the present invention is fulfilled by providing a method for finding a quotient Q=a 0 a 1 a 2 . . . a b from a divisor Y=y 1 y 2 . . . y n and a dividend X=x 1 x 2 . . . x n . The method comprises the following steps of: (a) aligning the first non-zero bit of X with the first non-zero digit of Y; (b) defining a signed-digit partial remainder series R i where R 0 =Y, a first sign series of the partial remainder S i where S 0 =0, a second sign series of the partial remainder S n , and a counter i beginning from zero; (c) subtracting X from R i which yields next signed-digit partial remainder R i+1 ; (d) setting the sign of R i+1 to S n+1 ; (e) setting the result of exclusive-OR of S i and S n+1 to the true sign of the next remainder S i+1 ; (f) setting a i to 1 if S i+1 =0 or R i+1 =0; (g) setting a i to 0 if S i+1 =1; (h) inverting the signs of all digits of R i+1 if S i+1 =1; (i) shift R i+1 left by one bit; (j) adding 1 to i; and (k) repeating said steps (c) to (j) until it reaches a predetermined value or R i+1 =0.

Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are give by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.

FIG. 1 shows in block diagram form an overview of the digital information processing system implementing the invention.

For achieving fast division, a new division algorithm is proposed and discussed hereinafter.

New Division Algorithm

Given normalized n-bit sign magnitude operands 1/2≦|X|<1, 1/2≦|Y|<1 (this limitation is used to automatically align the first non-zero bit of X with the first non-zero digit of Y in the later discussion, which is avoided in circuit realization), quotient Q 2 of Y/X can be solved using the following principles, where the quotient digits Q 2 =a s a 0 ·a 1 a 2 . . . a n is in sign-magnitude representation and a s is the sign bit.

Principle 1

a s equals to the result of exclusive-OR of the sign bits y s and x s of Y and X, respectively, i. e., a s =y s ⊕x s .

Principle 2

Partial remainder R i+1 can be solved by modifying the conventional, nonrestoring algorithm stated by K. Hwang as follows. The signed-binary quotient Q has its quotient digit q i ε{1, −1}, and

R i+1 =2| R i −q i+1 ′X|   (1)

where R 0 =|y|, q 0 =1, q i ′ is the i-th pseudo quotient digit. Since R i+1 is always positive, Eq. (1) can be rewritten as

R i+1 =2 |R i −X|   (2)

q i + 1 = { 1 , if ⁢ ⁢ S i + 1 = 0 1 , if ⁢ ⁢ Z i + 1 = 1 - 1 , if ⁢ ⁢ S i + 1 = 0 ( 3 ) a i = { 1 , if ⁢ ⁢ q i + 1 = 1 0 , if ⁢ ⁢ q i + 1 = - 1 ( 4 )

where

S n =The sign of remainder (R i −X),

S i =True sign of i-th remainder=S i−1 ⊕S n ,

Z i =Zero Flag, Z 0 =0, and

S 0 =S r0 =Sign{R 0 }=0.

The algorithm can be performed using the method described below.

New Division Method

Define signed magnitude numbers Y s =y s ·y 1 y 2 . . . y n , X s =x s ·x 1 x 2 . . . x n , and Q s =q s q 0 ·q 1 q 2 . . . q b in signed-binary representation, q s ε{−1, 1}, and converted to sign magnitude representation Q 2 =a s a 0 ·a 1 a 2 . . . a b , a i ε{0, 1}. The quotient Q 2 of X s /Y s can be solved by the following steps:

a s =y s ⊕x s .

Define Y=y 1 y 2 . . . y n , X=x 1 x 2 . . . x a , Q=a 0 a 1 a 2 . . . a b , R 0 =Y, i=0, and S 0 =0.

Subtract X from R i and yield next signed-digit partial remainder R i+1 . Set the sign of R i+1 to S ri+1 (note that the sign of R i+1 equals the sign of first non-zero digit of R i+1 ). Set the result of S i ⊕S ri+1 to the true sign of the next remainder S i+1 . Set a i to 1 if S i+1 =0 (means the remainder is positive) or R i+1 =0. Set a i to 0 if S i+1 =1 (means the remainder is negative).

If S i+1 =1, then take the absolute value of R i+1 (by inverting the signs of all digits). Shift R i+1 left by one bit. Add 1 to i. Repeat step 3 until i reaches a predetermined value or R i+1 =0.

For better comprehension, two examples are used to demonstrate the division method hereinafter:

Y=01010001 2 =81

X=00001001 2 =9 (X will be shifted left 3 places to align its highest non-zero digit with highest non-zero digit of R 0 )

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

0110110

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

Result:

The quotient=a 0 a 1 a 2 a 3 =1001 2 =9, and remainder=0

In this example, note that a digit with a bar means a digit having negative value, e.g.

1 1 2 =2+(−1)=1.

Y=10101110 2 =174

X=11 2 =3

⁢

⁢

⁢

⁢

01

⁢

1

_

⁢

0

⁢

111

_

⁢

0

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

1001110

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

10

⁢

1

_

⁢

00000

⁢

⁢

⁢

⁢

⁢

⁢

⁢

The quotient=a 0 a 1 a 2 a 3 a 4 a 5 a 6 =0111010 2 =58, and remainder=0

Since absolute values of the partial remainders are computed instead of their actual values, the algorithm facilities parallel computations of partial remainder and quotient digit. To further speed up the operation of subtraction in the preferred embodiment, we used specified signed-digit operation.

Specific Signed-Digit Subtraction

Since computations of Eq. (2) involves only the subtraction operation of two positive numbers, R i and X, we can speed up the computation by defining the CSA-like operation as follows.

y j −x j =2 c j+1 +t j   (5.a)

t j +c j =r j   (5.b)

wherein y j , r j ε{−1, 0, 1}

x j , t j ε{0, 1}

c j ε{−1, 0}.

Here, a signed-digit y j (represents the j-th digit of R i ) subtracts a binary digit x j , then generates carry c j+i and intermediate result t j . The final result r j (represents the j-th digit of R i+1 ) is obtained by adding t j and the carry-in bit c j . Since r j ε{−1, 0, 1}, there will be no carry generated from t j +c j . As a result, the specified signed-digit subtraction efficiently eliminates carry propagation. In addition, the complexity of this operation is similar to that of conventional CSA. Example 3 depicts the modified subtraction method where T i =t 1 t 2 . . . t n and C i =c 1 c 2 . . . c n .

Y=01010001 2 =81

X=00001001 2 =9

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

1

⁢

1

_

⁢

00

⁢

1

_

⁢

0

⁢

1

_

⁢

0

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

⁢

Result:

The quotient=1001 2 =9, and remainder=0

As shown in the above example, T i and C i are calculated first, then R i can be easily decided. The truth table of t j and c j+1 value are listed in table 1, where the signed-digit r j of R i is represented by two bits, r j 1 and r j 2 . r j 1 =sign(r j }.r j 2 =|r j |.

The truth table of r j (represents the j-th digit of R i+1 ) is listed in table 2.

From the above tables we can see that the signed-digit subtraction can be achieved by a simple digital circuit, and can be pipe-lined for better performance.

In summary, the division algorithm have the advantages as follows:

a) It uses a smaller quotient digit set of {1, −1} than {−1, 0, 1}, that simplifies that quotient decision circuits like some known algorithms do, but achieves the exact division and trivial conversion of the results from signed-binary representation to binary representation.

b) It needs no quotient estimator.

c) In each iteration, the algorithm computes partial remainders without knowing the signs of previous remainders and decides the signs of remainders independently and in parallel. In addition, these two operations are done in pipelined fashion and in digit level with maximum throughput rate.

d) Its architecture basically consists of the simple CSA type cells.

e) It can handle either positive or negative operands.

From above discussion, the proposed division algorithm and its architecture is very efficient. The new algorithm's realization is composed of highly regular cellular array, which is suitable for VLSI implementation and can be easily extended to bit-parallel implementation. As can be seen in FIG. 1 , digital information processing system 10 includes arithmetic unit 12 and memory 14 . Arithmetic unit 12 typically contains VLSI binary logic circuit elements (such as adders, shifters, exclusive-or circuits, etc) which, under system control, receives binary divisor and dividend data from memory 14 , performs the steps of the invention, and thereupon provides the resulting quotient data back to memory 14 . Those skilled in the art of digital information processing systems can readily provide the interconnection of needed logic circuit elements (and their appropriate control) to implement the invention.

The algorithm can be extended to higher radix divisions such as radix-4 division. Since the remainders are taken absolute values, the digit set contains only digits 1 and 2 is sufficient for the entire radix-4 operation. This greatly reduces the number of search regions for the quotient digits, in contrast to the bigger set of {0, 1, 2, 3} that existing algorithms allow.

While the invention has been described by way of an example and in terms of several preferred embodiments, it is to be understood that the invention need not be limited to the disclosed embodiment. On the contrary, it is intended to cover various modifications and similar arrangements included within the spirit and scope of the appended claims, the scope of which should be accorded the broadest interpretation so as to encompass all such modifications and similar structures.