# Patent

## Title
Method for finding quotient in a digital system

## Abstract

A fast division method which uses a smaller quotient digit set of {−1, 1} than {−1, 0, 1} that is used by known algorithms, therefore accelerates the speed of calculation. Partial remainders can be computed with the signals of remainders decided independently and in parallel. 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. The algorithm adopts non-restoring division operation and CSA type of operation for fast subtraction. The algorithm is also an on-line algorithm that facilitates highly pipelined operation while it is much simpler than the existing on-line algorithms.

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


BACKGROUND OF THE INVENTION
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.
SUMMARY OF THE INVENTION
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=a0a1a2 . . . ab from a divisor Y=y1y2 . . . yn and a dividend X=x1x2 . . . xn. 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 Ri where R0=Y, a first sign series of the partial remainder Si where S0=0, a second sign series of the partial remainder Sn, and a counter i beginning from zero; (c) subtracting X from Ri which yields next signed-digit partial remainder Ri+1; (d) setting the sign of Ri+1 to Sn+1; (e) setting the result of exclusive-OR of Si and Sn+1 to the true sign of the next remainder Si+1; (f) setting ai to 1 if Si+1 =0 or Ri+1=0; (g) setting ai to 0 if Si+1=1; (h) inverting the signs of all digits of Ri+1 if Si+1=1; (i) shift Ri+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 Ri+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.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows in block diagram form an overview of the digital information processing system implementing the invention.



DETAILED DESCRIPTION OF THE EMBODIMENTS
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 Q2 of Y/X can be solved using the following principles, where the quotient digits Q2=asa0 ·a1a2 . . . an is in sign-magnitude representation and as is the sign bit.
Principle 1
as equals to the result of exclusive-OR of the sign bits ys and xs of Y and X, respectively, i. e., as=ys⊕xs.
Principle 2
Partial remainder Ri+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 qiε{1, −1}, and

Ri+1=2|Ri−qi+1′X|  (1)

where R0=|y|, q0=1, qi′ is the i-th pseudo quotient digit. Since Ri+1 is always positive, Eq. (1) can be rewritten as

Ri+1=2|Ri−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

Sn=The sign of remainder (Ri−X),
Si=True sign of i-th remainder=Si−1⊕Sn,
Zi=Zero Flag, Z0=0, and
S0=Sr0=Sign{R0}=0.
The algorithm can be performed using the method described below.
New Division Method
Define signed magnitude numbers Ys=ys·y1y2 . . . yn, Xs=xs·x1x2 . . . xn, and Qs=qsq0·q1q2 . . . qb in signed-binary representation, qsε{−1, 1}, and converted to sign magnitude representation Q2=asa0·a1a2 . . . ab, aiε{0, 1}. The quotient Q2 of Xs/Ys can be solved by the following steps:
Step 1:
as=ys⊕xs.
Step 2:
Define Y=y1y2 . . . yn, X=x1x2 . . . xa, Q=a0a1a2 . . . ab, R0=Y, i=0, and S0=0.
Step 3:
Subtract X from Ri and yield next signed-digit partial remainder Ri+1. Set the sign of Ri+1 to Sri+1 (note that the sign of Ri+1 equals the sign of first non-zero digit of Ri+1). Set the result of Si⊕Sri+1 to the true sign of the next remainder Si+1. Set ai to 1 if Si+1=0 (means the remainder is positive) or Ri+1=0. Set ai to 0 if Si+1=1 (means the remainder is negative).
Step 4:
If Si+1=1, then take the absolute value of Ri+1 (by inverting the signs of all digits). Shift Ri+1 left by one bit. Add 1 to i. Repeat step 3 until i reaches a predetermined value or Ri+1=0.
For better comprehension, two examples are used to demonstrate the division method hereinafter:
EXAMPLE 1
Y=010100012=81
X=000010012=9 (X will be shifted left 3 places to align its highest non-zero digit with highest non-zero digit of R0)



  
    
      
        
          
            
          
          ⁢
          1010001
        
      
      
        
          
            
          
          ⁢
          
            
              R
              0
            
            =
            Y
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            
          
          ⁢
          0001001
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  1
                
                >
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      1
                    
                  
                
              
              =
              0
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                1
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      1
                    
                  
                  ⊕
                  
                    S
                    0
                  
                
                =
                0
              
            
            ,
            
              
                a
                0
              
              =
              1
            
          
        
      
    
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          
            
          
          ⁢
          0010010
        
      
      
        
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          -
          0110110
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  2
                
                <
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      2
                    
                  
                
              
              =
              1
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                2
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      2
                    
                  
                  ⊕
                  
                    S
                    2
                  
                
                =
                1
              
            
            ,
            
              
                a
                2
              
              =
              0
            
          
        
      
    
  




  
    TAKE
    ⁢
    
      
    
    ⁢
    ABSOLUTE
    ⁢
    
      
    
    ⁢
    VALUE
  




  0110110




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          
            
          
          ⁢
          1101100
        
      
      
        
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            
          
          ⁢
          0100100
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  3
                
                >
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      3
                    
                  
                
              
              =
              0
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                3
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      3
                    
                  
                  ⊕
                  
                    S
                    2
                  
                
                =
                1
              
            
            ,
            
              
                a
                2
              
              =
              0
            
          
        
      
    
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          
            
          
          ⁢
          1001000
        
      
      
        
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            
          
          ⁢
          0000000
        
      
      
        
          
            
          
          ⁢
          
            
              R
              4
            
            =
            
              
                0
                ⁢
                
                  
                
                ⁢
                then
                ⁢
                
                  
                
                ⁢
                
                  a
                  3
                
              
              =
              1
            
          
        
      
    
  



Result:

    
    
        The quotient=a0a1a2a3=10012=9, and remainder=0
    
    


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


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


Y=101011102=174
X=112=3



  
    
      
        
          
            
          
          ⁢
          10101110
        
      
      
        
          
            
          
          ⁢
          
            
              R
              0
            
            =
            Y
          
        
      
    
    
      
        
          
            -
            11
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            
          
          ⁢
          
            0
            ⁢
            
              1
              _
            
            ⁢
            101110
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  1
                
                <
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      1
                    
                  
                
              
              =
              1
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                1
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      1
                    
                  
                  ⊕
                  
                    S
                    0
                  
                
                =
                1
              
            
            ,
            
              
                a
                0
              
              =
              0
            
          
        
      
    
  




  
    TAKE
    ⁢
    
      
    
    ⁢
    ABSOLUTE
    ⁢
    
      
    
    ⁢
    VALUE
  




  
    01
    ⁢
    
      1
      _
    
    ⁢
    0
    ⁢
    
      111
      _
    
    ⁢
    0
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          1
          ⁢
          
            1
            _
          
          ⁢
          0
          ⁢
          
            111
            _
          
          ⁢
          00
        
      
      
        
          
        
      
    
    
      
        
          
            -
            11
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            1
            _
          
          ⁢
          00
          ⁢
          
            111
            _
          
          ⁢
          00
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  2
                
                <
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      2
                    
                  
                
              
              =
              1
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                2
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      2
                    
                  
                  ⊕
                  
                    S
                    1
                  
                
                =
                0
              
            
            ,
            
              
                a
                1
              
              =
              1
            
          
        
      
    
  




  
    TAKE
    ⁢
    
      
    
    ⁢
    ABSOLUTE
    ⁢
    
      
    
    ⁢
    VALUE
  




  1001110




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        100111000
      
      
        
          
        
      
    
    
      
        
          
            -
            11
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        01111000
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  3
                
                >
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      3
                    
                  
                
              
              =
              0
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                3
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      3
                    
                  
                  ⊕
                  
                    S
                    2
                  
                
                =
                0
              
            
            ,
            
              
                a
                2
              
              =
              1
            
          
        
      
    
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          
            
          
          ⁢
          1001000
        
      
      
        
          
        
      
    
    
      
        
          
            -
            11
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            
          
          ⁢
          00110000
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  4
                
                >
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      4
                    
                  
                
              
              =
              0
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                4
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      4
                    
                  
                  ⊕
                  
                    S
                    3
                  
                
                =
                0
              
            
            ,
            
              
                a
                3
              
              =
              1
            
          
        
      
    
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        01100000
      
      
        
          
        
      
    
    
      
        
          
            -
            11
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            1
            _
          
          ⁢
          0100000
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  5
                
                <
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      5
                    
                  
                
              
              =
              1
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                5
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      5
                    
                  
                  ⊕
                  
                    S
                    4
                  
                
                =
                1
              
            
            ,
            
              
                a
                4
              
              =
              0
            
          
        
      
    
  




  
    TAKE
    ⁢
    
      
    
    ⁢
    ABSOLUTE
    ⁢
    
      
    
    ⁢
    VALUE
  




  
    10
    ⁢
    
      1
      _
    
    ⁢
    00000
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          
            10
            ⁢
            
              1
              _
            
            ⁢
            00000
          
        
        
          
            
          
        
      
      
        
          
            
              -
              11
            
            _
          
        
        
          
            
              
            
            ⁢
            X
          
        
      
      
        
          00000000
        
        
          
            
              
            
            ⁢
            
              
                
                  R
                  6
                
                =
                
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    then
                    ⁢
                    
                      
                    
                    ⁢
                    
                      a
                      5
                    
                  
                  =
                  1
                
              
              ,
              
                
                  a
                  6
                
                =
                0
              
            
          
        
      
    
    ⁢
    
      
        
          
            
          
        
        
          
            
          
        
      
    
  



    
    
        The quotient=a0a1a2a3a4a5a6=01110102=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, Ri and X, we can speed up the computation by defining the CSA-like operation as follows.

yj−xj=2cj+1+tj  (5.a)

tj+cj=rj  (5.b)

wherein yj, rjε{−1, 0, 1}

    
    
        xj, tjε{0, 1}
        
            cjε{−1, 0}.
        
        
    
    


Here, a signed-digit yj (represents the j-th digit of Ri) subtracts a binary digit xj, then generates carry cj+i and intermediate result tj. The final result rj (represents the j-th digit of Ri+1) is obtained by adding tj and the carry-in bit cj. Since rjε{−1, 0, 1}, there will be no carry generated from tj+cj. 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 Ti=t1t2 . . . tn and Ci=c1c2 . . . cn.
EXAMPLE 3
Y=010100012=81
X=000010012=9



  
    
      
        
          
            
          
          ⁢
          1010001
        
      
      
        
          
            
          
          ⁢
          
            
              R
              0
            
            =
            Y
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            
          
          ⁢
          0011001
        
      
      
        
          
            
          
          ⁢
          
            T
            1
          
        
      
    
    
      
        
          
            -
            0001000
          
          _
        
      
      
        
          
            
          
          ⁢
          
            C
            1
          
        
      
    
    
      
        
          
            
          
          ⁢
          0001001
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  1
                
                >
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      1
                    
                  
                
              
              =
              0
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                1
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      1
                    
                  
                  ⊕
                  
                    S
                    0
                  
                
                =
                0
              
            
            ,
            
              
                a
                0
              
              =
              1
            
          
        
      
    
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          
            
          
          ⁢
          0010010
        
      
      
        
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        
          
            
          
          ⁢
          1011010
        
      
      
        
          
            
          
          ⁢
          
            T
            2
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        
          
            
          
          ⁢
          
            C
            2
          
        
      
    
    
      
        
          
            1
            _
          
          ⁢
          1001010
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  2
                
                <
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      2
                    
                  
                
              
              =
              1
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                2
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      2
                    
                  
                  ⊕
                  
                    S
                    1
                  
                
                =
                1
              
            
            ,
            
              
                a
                1
              
              =
              0
            
          
        
      
    
  




  
    TAKE
    ⁢
    
      
    
    ⁢
    ABSOLUTE
    ⁢
    
      
    
    ⁢
    VALUE
  




  
    1
    ⁢
    
      1
      _
    
    ⁢
    00
    ⁢
    
      1
      _
    
    ⁢
    0
    ⁢
    
      1
      _
    
    ⁢
    0
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          1
          ⁢
          
            1
            _
          
          ⁢
          00
          ⁢
          
            1
            _
          
          ⁢
          0
          ⁢
          
            1
            _
          
          ⁢
          00
        
      
      
        
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        
          
            
          
          ⁢
          X
        
      
    
    
      
        111011100
      
      
        
          
            
          
          ⁢
          
            T
            3
          
        
      
    
    
      
        
          
            -
            011011100
          
          _
        
      
      
        
          
            
          
          ⁢
          
            C
            3
          
        
      
    
    
      
        
          
            
          
          ⁢
          
            001
            ⁢
            
              1
              _
            
            ⁢
            00100
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                
                  R
                  3
                
                >
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  then
                  ⁢
                  
                    
                  
                  ⁢
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      3
                    
                  
                
              
              =
              0
            
            ,
          
        
      
    
    
      
        
          
        
      
      
        
          
            
          
          ⁢
          
            
              
                S
                3
              
              =
              
                
                  
                    S
                    
                      r
                      ⁢
                      
                        
                      
                      ⁢
                      3
                    
                  
                  ⊕
                  
                    S
                    2
                  
                
                =
                1
              
            
            ,
            
              
                a
                2
              
              =
              0
            
          
        
      
    
  




  
    SHIFT
    ⁢
    
      
    
    ⁢
    LEFT
    ⁢
    
      
    
    ⁢
    ONE
    ⁢
    
      
    
    ⁢
    BIT
  




  
    
      
        
          
            
          
          ⁢
          
            1
            ⁢
            
              1
              _
            
            ⁢
            001000
          
        
      
      
        
          
        
      
    
    
      
        
          
            -
            1001000
          
          _
        
      
      
        X
      
    
    
      
        
          
            
          
          ⁢
          10000000
        
      
      
        
          T
          4
        
      
    
    
      
        
          
            -
            01000000
          
          _
        
      
      
        
          C
          4
        
      
    
    
      
        
          
            
          
          ⁢
          0
        
      
      
        
          
            R
            4
          
          =
          
            
              0
              ⁢
              
                
              
              ⁢
              then
              ⁢
              
                
              
              ⁢
              
                a
                3
              
            
            =
            1
          
        
      
    
  



Result:

    
    
        The quotient=10012=9, and remainder=0
    
    


As shown in the above example, Ti and Ci are calculated first, then Ri can be easily decided. The truth table of tj and cj+1 value are listed in table 1, where the signed-digit rj of Ri is represented by two bits, rj1 and rj2. rj1=sign(rj}.rj2=|rj|.







TABLE 1







TRUTH TABLE OF tj AND cj+1











xj
rj1
rj1
cj+1
tj





0
0
0
0
0


0
0
1
0
1


0
1
1
1
1


1
0
0
1
1


1
0
1
0
0


1
1
1
1
0





Note that rj represents j-th digit of Ri here.






The truth table of rj (represents the j-th digit of Ri+1) is listed in table 2.







TABLE 2







TRUTH TABLE OF rj (the j-th digit of Ri+1)












cj
tj
rj1
ri2







0
0
0
0



0
1
0
1



1
0
1
1



1
1
0
0










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.
CONCLUSION
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.

## Claims

1. In a system for digital information processing, said system having a memory, a method for generating data representative of a quotient Q=a0a1a2 . . . ab from data representative of a divisor Y=y1y2 . . . yn and data representative of a dividend X=x1x2 . . . xa, comprising the 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 Ri where R0=Y, a first sign series of the partial remainder Si where S0=0, a second sign series of the partial remainder Sri, a quotient bit series ai, and a counter i beginning from zero;
(c) subtracting X from Ri which yields next signed-digit partial remainder Ri+1;
(d) setting the sign of Ri+1 to Sri+1;
(e) setting the result of exclusive-OR of Si and Sri+1 to the true sign of the next remainder Si+1;
(f) setting ai to 1 if Si+1=0 or Ri+1=0;
(g) setting ai to 0 if Si+1=1;
(h) inverting the signs of all digits of Ri+1 if Si+1=1;
(i) shift Ri+1 left by one bit;
(j) adding 1 to i;
(k) repeating steps (c) to (j) until i reaches a predetermined value or Ri+1=0; and
(l) storing in said memory as said data representative of a quotient, a quotient resulting from step (k).

2. In a system for digital information processing, said system having a memory for storing data, a method for generating data representative of a signed magnitude quotient Q2=asa0a1a2 . . . ab from data representative of a signed divisor Ys=ys·y1y2 . . . yn, and data representative of a signed dividend Xs=xs·x1x2 . . . xs, comprising the steps of:
(a) obtaining as from the result of exclusive-OR of ys and xs;
(b) defining a divisor Y=y1y2 . . . yn , a dividend X=x1x2 . . . xs, a signed-digit partial remainder series Ri where R0=Y, a first sign series of the partial remainder Si where S0=0, a second sign series of the partial remainder Sri, a quotient bit series ai, and a counter i beginning from zero;
(c) aligning the first non-zero bit of X with the first non-zero digit of Y;
(d) subtracting X from Ri which yields next signed-digit partial remainder Ri+1;
(e) setting the sign of Ri+1 to Sri+1;
(f) setting the result of exclusive-OR of Si and Sri+1 to the true sign of the next remainder Si+1;
(g) setting ai to 1 if Si+1=0 or Ri+1=0;
(h) setting ai to 0 if Si+1=1;
(i) inverting the signs of all digits of Ri+1 if Si+1=1;
(j) shift Ri+1 left by one bit;
(k) adding 1 to i; and
(l) repeating steps (d) to (k) until i reaches a predetermined value or Ri+1=0; and
(l) storing in said memory as said data representative of a signed magnitude quotient, a quotient resulting from step (k).

3. A system for digital information processing, said system having a memory for storing data, including data representative of a quotient Q=a0a1a2 . . . ab from data representative of a divisor Y=y1y2 . . . yn and data representative of a dividend X=x1x2 . . . xa, said data representative of a quotient generated by a method comprising the 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 Ri where R0=Y, a first sign series of the partial remainder Si where S0=0, a second sign series of the partial remainder Sri,a quotient bit series ai, and a counter i beginning from zero;
(c) subtracting X from Ri which yields next signed-digit partial remainder Ri+1;
(d) setting the sign of Ri+1 to Sri+1;
(e) setting the result of exclusive-OR of Si and Sri+1 to the true sign of the next remainder Si+1;
(f) setting ai to 1 if Si+1=0 or Ri+1=0;
(g) setting ai to 0 if Si+1=1;
(h) inverting the signs of all digits of R+1 if S+1=1;
(i) shift Ri+1 left by one bit;
(j) adding 1 to i;
(k) repeating steps (c) to (j) until i reaches a predetermined value or Ri+1=0; and
(l) storing in said memory as said data representative of a quotient, a quotient resulting from step (k).

4. A system for digital information processing, said system having a memory for storing data, including data representative of a signed magnitude quotient Q2=asa0·a1a2 . . . ab from data representative of a signed divisor Ys=ys·y1y2 . . . yn, and data representative of a signed dividend Xs=xs·x1x2 . . . xs, said data representative of a signed magnitude quotient generated by a method comprising the steps of:
(a) obtaining as from the result of exclusive-OR of ys and xs;
(b) defining a divisor Y=y1y2 . . . yn, a dividend X=x1x2 . . . xs, a signed-digit partial remainder series Ri where R0=Y, a first sign series of the partial remainder Si where S0=0, a second sign series of the partial remainder Sri, a quotient bit series ai, and a counter i beginning from zero;
(c) aligning the first non-zero bit of X with the first non-zero digit of Y;
(d) subtracting X from Ri which yields next signed-digit partial remainder Ri+1;
(e) setting the sign of Ri+1 to Sri+1;
(f) setting the result of exclusive-OR of Si and Sri+1 to the true sign of the next remainder Si+1;
(g) setting ai to 1 if Si+1=0 or Ri+1=0;
(h) setting ai to 0 if Si+1=1;
(i) inverting the signs of all digits of Ri+1 if Si+1=1;
(j) shift Ri+1 left by one bit;
(k) adding 1 to i;
(l) repeating steps (d) to (k) until i reaches a predetermined value or Ri+1=0; and
(m) storing in said memory as said data representative of a signed magnitude quotient, a quotient resulting from step (l).