US4873660A  Arithmetic processor using redundant signed digit arithmetic  Google Patents
Arithmetic processor using redundant signed digit arithmetic Download PDFInfo
 Publication number
 US4873660A US4873660A US07/066,817 US6681787A US4873660A US 4873660 A US4873660 A US 4873660A US 6681787 A US6681787 A US 6681787A US 4873660 A US4873660 A US 4873660A
 Authority
 US
 United States
 Prior art keywords
 digit
 determining
 radix
 digits
 arithmetic
 Prior art date
 Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
 Expired  Lifetime
Links
 230000000875 corresponding Effects 0.000 claims description 12
 238000006243 chemical reaction Methods 0.000 abstract description 10
 230000014509 gene expression Effects 0.000 description 29
 238000010586 diagram Methods 0.000 description 14
 239000000203 mixture Substances 0.000 description 5
 230000000295 complement Effects 0.000 description 2
 230000000694 effects Effects 0.000 description 2
 241001442055 Vipera berus Species 0.000 description 1
 230000001413 cellular Effects 0.000 description 1
 239000002131 composite material Substances 0.000 description 1
 239000000470 constituent Substances 0.000 description 1
 230000001276 controlling effect Effects 0.000 description 1
 235000021163 supper Nutrition 0.000 description 1
Images
Classifications

 G—PHYSICS
 G06—COMPUTING; CALCULATING; COUNTING
 G06F—ELECTRIC DIGITAL DATA PROCESSING
 G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
 G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
 G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using noncontactmaking devices, e.g. tube, solid state device; using unspecified devices
 G06F7/4824—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using noncontactmaking devices, e.g. tube, solid state device; using unspecified devices using signeddigit representation

 G—PHYSICS
 G06—COMPUTING; CALCULATING; COUNTING
 G06F—ELECTRIC DIGITAL DATA PROCESSING
 G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
 G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
 G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using noncontactmaking devices, e.g. tube, solid state device; using unspecified devices
 G06F7/52—Multiplying; Dividing
 G06F7/535—Dividing only
 G06F7/537—Reduction of the number of iteration steps or stages, e.g. using the SweenyRobertsonTocher [SRT] algorithm
 G06F7/5375—Non restoring calculation, where each digit is either negative, zero or positive, e.g. SRT
Abstract
A high speed arithmetic processor which may compactly be fabricated on an LSI chip is disclosed. The arithmetic processor in a firststep arithmetic operation determines an intermediate carry (or intermediate borrow) for a higher order arithmetic operation from an internal operand such as augend (or minuend) and an addend (or subtrahend) for each digit in addition (or subtraction) of signed digit numbers, carried out as an internal arithmetic operation, and determines an intermediate sum (or intermediate difference). In a second step arithmetic operation, the processor obtains a final sum (or difference) for each digit from the intermediate sum (or intermediate difference) obtained in the first step arithmetic operation and an intermediate carry (or intermediate borrow) from a lower order arithmetic operation. The sign of an internal operand is either inverted or the internal operand is converted to 0 in accordance with the value of a control signal and then provided as the internal operand for processing in the first step arithmetic operation. Such sign inversion or conversion of the operand to zero enables the first and second step arithmetic operations to be performed utilizing addition and/or subtraction only.
Description
The present invention relates to an arithmetic processor capable of highspeed arithmetic operation and, more particularly, to an arithmetic processor which has a cellular array structure and which may be compactly fabricated on an LSI chip.
One type of conventional highspeed multiplier is discussed in Trans. of IECE Japan, Vol.J66D, No. 6, 1983, pp. 683 to 690, and one type of conventional highspeed divider is discussed in Trans. of IECE Japan, Vol. J67D, No. 4, 1984, pp. 450 to 457. That multiplier and that divider are arithmetic units each arranged to execute multiplication or division by means of combinational circuitry using the redundant binary expression (a kind of signed digit expression) in which each digit is represented by a set of elements {1, 0, 1}. While those devices have a regular array structure and have faster arithmetic processing speeds than other types of conventional arithmetic units, no consideration is given to factors which are important for fabricating them commercially, such as a reduction in the number and size of constituent elements and use of MOS technology for a multiplier and divider which are capable of highspeed operation.
In particular, dividers in wide use today are sequential circuits each consisting of a subtracter (adder) and a shifter. However, it is well known that, as the number of digits of the operands increases, an exceedingly long time is required for those dividers to perform arithmetic operations. On the other hand, largesize computers having highspeed multipliers often employ multiplicationtype division in which division is performed by repetition of multiplication. However, realization of such multiplicationtype division by combinational circuitry requires large numbers of hardware elements, and is therefore impractical.
With respect specifically to a highspeed arithmetic unit employing signed digit numbers for arithmetic operation, a method has been proposed in which an arithmetic operation such as multiplication or division is realized by combinational circuitry utilizing an ECL logic element that enables NOR and OR operations to be simultaneously performed. However, exhaustive consideration has heretofore not been given to problems which must be solved to put that proposed highspeed arithmetic unit into practical use, such as reducing the number of elements required and the use of other types of circuitry to construct the unit, and, therefore, the following problems are associated with that proposed signed digit highspeed arithmetic unit:
(1) As the number of digits of the operands increases, the number of elements required increases, which makes it difficult to fabricate an arithmetic unit capable of handling a large number of digits on a single LSI chip.
(2) When the arithmetic unit is realized using, for example, a MOS circuit which cannot perform NOR and OR operations at the same time, the OR circuit is realized by elements formed in two stages, that is, a NOR gate and an inverter, and the number of stages or gates required in the arithmetic circuit increases correspondingly, resulting in an increase in operation time.
It is an object of the present invention to provide a highspeed arithmetic processor which can readily be fabricated compactly on an LSI chip.
It is another object of the present invention to provide such a highspeed arithmetic processor utilizing combinational circuitry in which signed digit numbers are employed for internal addition and subtraction.
It is another object of the present invention to provide a highspeed arithmetic processor which adopts an array structure and in which the number of required elements (transistors) is substantially reduced (e.g., by half) as compared to prior art highspeed arithmetic processors.
It is another object of the present invention to provide such a highspeed arithmetic processor which minimizes the number of digits which need carry propagation for internal addition and subtraction (e.g., one digit at most).
It is another object of the present invention to provide a highspeed arithmetic processor which is of simplified circuit configuration.
In achieving the above and other objects, the present invention provides an arithmetic processor which comprises: firststep arithmetic means for determining (a) an intermediate carry (or intermediate borrow) for a higher order arithmetic operation from an internal operand such as an augend (or minuend) and an addend (or subtrahend) for each digit in addition (or subtraction) of signed digit numbers, carried out as an internal arithmetic operation, and (b) an intermediate sum (or intermediate difference); secondstep arithmetic means for obtaining a final sum (or difference) for a respective digit from the intermediate sum (or intermediate difference) obtained in the first step and an intermediate carry (or intermediate borrow) of a lower order arithmetic operation; and means for either inverting the sign of an internal operand or converting an internal operand to 0 in accordance with the value of a control signal and providing the inverted or converted operand as the internal operand to the first step arithmetic means.
According to a first embodiment, an arithmetic processor performs arithmetic operations by obtaining an intermediate carry or borrow, an intermediate sum and then a final sum or difference for a respective digit from the intermediate carry or borrow, respectively, and a carry or borrow from a lower order arithmetic operation, the arithmetic processor including: first (addend determining or sign inversion) means for receiving a control signal and an operand, and providing one of the operand, a zero and an operand which is inverted in sign from the operand in accordance with the value of the control signal; second (intermediate carry determining) means for receiving internal operands including an augend and an addend or a minuend and a subtrahand, and an operand or zero from the first means and providing an output signal indicating an intermediate carry or borrow, respectively, for a higher order arithmetic operation; third (intermediate sum determining) means for receiving the internal operands and an operand or zero from the first means and providing an intermediate sum or difference, respectively; and fourth (final sum determining) means for receiving the intermediate sum or difference and a signal indicating an intermediate carry or borrow from a lower order arithmetic operation and providing a final sum or difference, respectively. The first means enables the second, third and fourth means to perform arithmetic operations utilizing only addition and/or subtraction steps, whereby arithmetic operations may be executed by the processor utilizing addition and/or subtraction.
According to a preferred first embodiment, the second means and part of the first means comprise an arithmetic cell, and the third means and part of the first means comprise an arithmetic cell, each of the cells performing an arithmetic operation for one digit of an internal operand and being arranged in an array structure.
According to a second embodiment of the invention, the arithmetic processor includes first (sign inversion) means for receiving a control signal and internal operands, and providing either the internal operands or internal operands having a sign inversion in accordance with the value of that control signal; second (divisor conversion) means for receiving a control signal and an operand, and providing either the operand or a zero in accordance with the value of that control signal; third (intermediate carry determining) means for receiving from the first means a zero or an operand including an augend and an addend or a minuend and a subtrahand and the operand from the second means, and providing an output signal indicating an intermediate carry or borrow, respectively, for a higher order arithmetic operation; fourth (intermediate sum determining) means for receiving an operand or zero from the first means and the operand from the second means and providing an intermediate sum or difference, respectively; and fifth (final sum determining) means for receiving the intermediate sum or difference and a signal indicating an intermediate carry or borrow from a lower order arithmetic operation and providing a final sum or difference, respectively. The first and second means enabling the third, fourth and fifth means to perform arithmetic operations utilizing only addition and/or subtraction steps, whereby arithmetic operations may be executed by the processor utilizing addition and/or subtraction.
According to a preferred second embodiment, the third means and part of the first and second means comprise an arithmetic cell, and the fourth means and part of the first and second means comprise an arithmetic cell, each of the cells performing an arithmetic operation for one digit of an internal operand and being arranged in an array structure.
As described in more detail below, arithmetic processors according to the invention use operands in the form redundant numbers in a signed digit expression in which each digit may have a positive value, 0, or a negative value, and internal operands in the form of radix r numbers.
An arithmetic processor according to the invention also includes quotient determining means for determining one digit of a quotient in division and a partial remainder determining means for obtaining a remainder with respect to the quotient determined by the quotient determining means. In the first embodiment, the partial remainder determining means comprises the second, third and fourth means; the second means receives the remainder from the quotient determining means; and the quotient determining means, the partial remainder determining means and the first means are defined by an array structure comprising a plurality of combinational circuitry stages for executing division. Preferably, the quotient determining means includes the first means.
In the second embodiment, the partial remainder determining means comprises the second, third and fourth means, the second means receives the remainder from the quotient determining means; and the quotient determining means, the partial remainder determining means, the first means and the second means are defined by an array structure comprising a plurality of combinational circuitry stages for executing division. Preferably, the quotient determining means includes the first and second means.
A specific embodiment of the invention is described below by way of example with respect to a divider.
The shiftsubtract/add division method is generally represented by the following recurrence formula:
R.sup.(j+1) =r×R.sup.(j) q.sub.j ×D,
where
j = exponent of the recurrence formula,
r = radix,
D = divisor,
q_{j} = jth quotient digit from a decimal point,
r×R.sup.(j) = partial dividend before determination of q_{j}, and
R.sup.(j+1) = partial remainder after determination of q_{j}.
Thus, the divider can be realized in the form of combinational circuitry by providing, for each value of the index j of the recurrence formula, a quotientdetermining cell for determining the quotient q_{j} and a partial remainder determining circuit which subtracts or does not subtract D from r×R.sup.(j) in accordance with the value of q_{j}. For arithmetic operation, internal operands are expressed using the signed digit expression (hereinafter referred to as "SD expression") in which each digit is expressed by one of the following elements: "0"; a positive integer; and a negative integer corresponding to the positive integer. More specifically, each digit is expressed by any of the following elements: {1, 0, 1}; {2, 1, 0, 1, 2}; {N, . . . , 1, 0, 1, . . . , N}, etc., whereby redundancy is provided so that one number can be expressed in a plurality of different ways. This makes it possible to prevent borrow (or carry) propagation in subtraction (or addition) and thus enables parallel subtraction (or addition) to be executed by the combinational circuitry within a predetermined time irrespective of the number of digits of the operands. For example, in the SD expression in which each digit is expressed in an element set {1, 0, 1}, it is possible to prevent carry (or borrow) propagation in addition (or subtraction) from occurring at more than one digit. This is described in, for example, Trans of IECE Japan, Vol. J67D, No. 4, 1984, pp. 450 to 457.
Employment of the SD expression for the arithmetic operation as described above enables realization of a highspeed divider. For example, if an SD expression of radix 2 and a signless binary number X consisting of one bit for the integer part and n bits for the decimal part is expressed as follows:
X=[x.sub.0.x.sub.1. . . x.sub.n ].sub.SD2,
then X may be expressed as follows: ##EQU1## where each digit x_{1} is expressed in an element set {1, 0, 1}.
If the divisor D and each partial remainder R.sup.(j) in the abovedescribed recurrence formula are expressed in an SD expression of radix 2, it is necessary to add or subtract D in accordance with the value of q_{j} in such a manner that, when q_{j} =1, R.sup.(j) is shifted leftward by one digit and D is added; when q_{j} =0, R.sup.(j) is shifted leftward by one digit; and when q_{j} =1, R.sup.(j) is shifted leftward by one digit and D is subtracted.
In particular, according to the present invention, the partial remainder R.sup.(j+1) after determination of the jth quotient digit from a decimal point can be determined by addition using only the SD expression, in accordance with the value of q_{j} by a means for inverting the sign of an internal operand in the SD expression and a means for assigning "0" to an internal operand, as follows:
R.sup.(j+1) =p.sup.(j) (P.sup.(j) (r×R.sup.(j))+D.sup.(j)).
P(j) the above relationship is a function for sign inversion, and D(j) and P(j) may be set in a variety of ways, two of which are as follows: ##EQU2##
P.sup.(j) (X)=X (i.e., P.sup.(j) is an identity mapping); ##EQU3##
D and X are numbers obtained by inverting the signs of D and X in the SD expression. The sign inversion in the SD expression is effected in such a manner that, if the digit is 1, the digit is changed to 1; if the digit is 1, it is changed to 1; and if the digit is 0, it is left unchanged. However, when D is expressed in the SD expression in which each digit is nonnegative as in the case of D, the sign inversion can be effected by the 2's complement binary representation.
Accordingly, where D.sup.(j) and P.sup.(j) are set according to Case (II) above, each digit of D.sup.(j) is nonnegative at all times; and where D.sup.(j) and P.sup.(j) (X) are set according to Case (I) above, most of the digits except for the most significant digit can be made nonnegative by expressing D using the 2's complement binary representation. Therefore, a partial remainder may be obtained using an array of 1digit redundant addition circuits (cells) according to an SD expression in which one operand (addend) is nonnegative, and a partial remainder determining circuit for each j may be provided by such an array. Thus, it is possible to reduce the number of elements required for each redundant addition circuit (cell) and provide a highspeed divider circuit in the form of a regularly arranged array of these addition circuits (cells), which makes it possible to fabricate a highspeed divider compactly on a VLSI chip.
FIG. 1 is a block diagram of an arithmetic processor in accordance with one embodiment of the invention;
FIG. 2 is a block diagram of one embodiment of each of the partial remainder determining circuits of the arithmetic processor of FIG. 1;
FIG. 3 is a block diagram of one embodiment of the basic cell structure of each redundant addition cell of the partial remainder determining circuit of FIG. 2.
FIG. 4 is a block diagram of another embodiment of the basic cell structure of each redundant addition cell of the partial remainder determining circuit of FIG. 2;
FIG. 5 is a block diagram of one embodiment of each quotientdetermining cell of the arithmetic processor of FIG. 1;
FIG. 6 is a circuit diagram showing a CMOS circuit which defines the basic cell shown in FIG. 4;
FIG. 7 is a circuit diagram of an embodiment of the transfer gate shown within broken lines in FIG. 6; and
FIG. 8 is a circuit diagram showing a CMOS circuit which defines the quotientdetermining circuit shown in FIG. 5.
FIG. 1 is a block diagram showing one embodiment of the present invention which is described below in connection with a divider for ndigit and rradix signless decimals, specifically for the case where n=8 and r=2. Referring to FIG. 1, a dividend within the brokenline block 20 (hereinafter referred to as "divided 20") is input to an initial partial remainder determining circuit 100 in the form of signals respectively corresponding to values x_{1}, x_{2}, . . . , x_{n} for the 1st, 2nd, . . . , nth digits to the right of the decimal point. Similarly, a divisor within the brokenline box 40 (hereinafter referred to as "divisor 40") is input to the initial partial remainder determining circuit 100 and to the partial remainder determining circuits 101, 102, 103, 104, 105, . . . in the form of signals representing values y_{1}, y_{2}, . . . , y_{n} for the 1st, 2nd, . . . , nth digits to the right of the decimal point. A quotient within brokenline block 60 (hereinafter referred to as "quotient 60") is output from an rradix conversion circuit 10 in the form of an rradix number consisting of the 1st integral digit z_{0} and the 1st decimal digit z_{1}, the second decimal digit z_{2}, . . . , the nth decimal digit z_{n}. The initial partial remainder determining circuit 100 receives dividend 20, [0.x_{1} x_{2}. . . x_{n} ]_{r}, and divisor 40, [0.y_{1} y_{2}. . . y_{n} ]_{r}, as its inputs, and outputs a partial remainder, or a value obtained by inverting the sign of this partial remainder, is determined after the 1st integral digit of the quotient. In particular, if the dividend and the divisor are normalized, then x_{1} =y_{1} =1, is readily obtained. The following description will be made with respect to division in which the dividend and the divisor are normalized.
Each of the partial remainder determining circuits 101, 102, 103, 104, 105 . . . receives the output of a respective partial remainder determining circuit (or the initial partial remainder determining circuit 100) which is immediately above it as viewed in FIG. 1, together with the divisor 40 and a respective control signal 251, 252, 253, 254, 255 . . . which is output from a respective quotientdetermining cell 201, 202, 203, 204, 205 . . . disposed adjacent to a respective partial remainder determining circuit 101, 102, 103, 104, 105 . . . , and outputs a partial remainder or a value obtained by inverting the sign of the partial remainder, which is then input to a subsequent (i.e., lower) partial remainder determining circuit.
Each of the quotientdetermining cells 201, 202, 203, 204, 205 . . . receives at its inputs the three most significant digits of a partial remainder, or a value obtained by inverting the sign of this partial remainder, output from the partial remainder determining circuit immediately above the respective quotientdetermining cell (e.g., from the (j1)th partial remainder determining circuit), together with the value of the (j1)th decimal digit of the quotient in the SD expression which has been determined in the quotientdetermining cell immediately above (i.e., the j1th quotientdetermining cell), and outputs the value for the jth decimal digit of the quotient, together with the respective control signal 251, 252, 253, 254, 255 . . . , which is supplied to the partial remainder determining circuit in the same stage (i.e, the jth stage).
The rradix conversion circuit 10 receives at its inputs the digits of a quotient in the SD expression which have been determined in quotientdetermining cells 201, 202, 203, 204, 205 . . . , respectively, and outputs a quotient 60, ]z_{0}.z_{1} a_{2}. . . z_{n} ]_{r}, which is an ordinary rradix number in which each digit is nonnegative.
The division method employing the embodiment of FIG. 1 will briefly be explained using mathematical expressions with respect to two methods for determining R.sup.(j+1), i.e. a method in which the addend is inverted (Case (I)) and a method in which the augend is inverted (Case (II)).
Case (I) inversion of the addend (i.e., divisor):
R.sup.(1) =[0.x.sub.1 x.sub.2. . . x.sub.n ].sub.SD2 [0.y.sub.1 y.sub.2. . . y.sub.n ].sub.SD2
is first calculated in initial partial remainder determining circuit 100 to determine a partial remainder R.sup.(1). It should be noted that the relationship above for determining R.sup.(1) is calculated in the redundant binary expression (i.e., the SD expression of radix 2), and R.sup.(1) is therefore a redundant binary number. Since x_{1} =1 and y_{1} =1, the first integral digit of the quotient is q_{0} =1. Further, since x_{1}, x_{2}, . . . , x_{3}, y_{1}, y_{2}, . . . , y_{n} are nonnegative, the initial partial remainder determining circuit 100 can readily be realized using a subtraction circuit for handling redundant binary numbers each digit of which is nonnegative, or an ordinary subtraction circuit. The relationship above for determining the partial remainder R.sup.(1) may be changed as follows:
R.sup.(1) =[0.x.sub.1 x.sub.2. . . x.sub.n ].sub.SD2 +[0.y.sub.1 y.sub.2. . . y.sub.n ].sub.SD2.
In other words, the partial remainder R.sup.(1) may be determined by addition of a redundant binary number each digit of which is nonnegative and an ordinary redundant binary number. In this case, y_{i} is a value obtained by inverting the sign of y_{i}. More specifically, when y_{i} =1, y_{i} =1, whereas, when y_{i} =0, y_{i} =0, where i is an integer having a value from 1 to n. Accordingly, the initial partial remainder determining circuit 100 can also be realized as an addition circuit for an ordinary redundant binary number and a redundant binary number each digit of which is nonnegative.
The jth quotient digit q_{j} from a decimal point and the partial remainder R.sup.(j+1), which is made after determination of the partial remainder R.sup.(j) =[r_{0} ^{j}.r_{1} ^{j} r_{2} ^{j} . . . r_{n} ^{j} ]_{SD2} and the j1th decimal digit q_{j} of the quotient, are determined as follows. It is assumed that j is an integer having a value from 1 to n. The jth decimal digit q_{j} of the quotient can be determined by the value of the three most significant digits [r_{0} ^{j}.r_{1} ^{j} r_{2} ]_{SD2} of the partial remainder R.sup.(j). More specifically, the determination is made as follows: if the value of the three most significant digits of R.sup.(j) is positive, q_{j} =1; if that value is 0, q_{j} =0,; and if that value is negative, q_{j} =1. Determination of the jth decimal digit q_{j} of the quotient is made in the jth cell (counted from the top of FIG. 1) of the quotientdetermining cells 201, 202, 203, 204, 205 . . . .
The partial remainder R.sup.(j+1) is determined in the jth circuit (counted from the top of FIG. 1) of the partial remainder determining circuits 101, 102, 103, 104, 105 . . . by performing the following calculations:
(i) when q_{j} =1,
R.sup.(j+1) =[r.sub.0.sup.j r.sub.1.sup.j.r.sub.2.sup.j. . . r.sub.n.sup.j 0].sub.SD2 +[0.y.sub.1 y.sub.2. . . y.sub.n ].sub.SD2 ;
(ii) when q_{j} =1,
R.sup.(j+1) =[v.sub.0.sup.j v.sub.1.sup.j.r.sub.2.sup.j. . . r.sub.n.sup.j 1].sub.SD2 +[0.u.sub.1 u.sub.2. . . u.sub.n ].sub.SD2 ;
where u_{i} =1y_{i} for i=1, . . . , n; when r_{1} ^{j} =1, then v_{0} ^{j} =r_{0} ^{j} and v_{1} ^{j} =0; when r_{1} ^{j} =0, then v_{0} ^{j} =r_{0} ^{j} and v_{1} ^{j} =1; and when r_{1} ^{j} =1, then v_{0} ^{j} =0 and v_{1} ^{j} =0. D which is opposite in sign to D=[0.y_{1} y_{2}. . . y_{n} ]_{SD2}, is obtained utilizing the fact that D can be expressed as follows:
D=[(1)..00. . . 1].sub.SD2 =[0.u.sub.1 u.sub.2. . . u.sub.n ].sub.SD2.
(iii) when q_{j} =0,
R.sup.(j+1) =[r.sub.0.sup.j r.sub.1.sup.j.r.sub.2.sup.j. . . r.sub.n.sup.j 0].sub.SD2 +[0.00. . .0].sub.SD2.
In the equations for determining the partial remainder R.sup.(j+l) employed in cases (i), (ii) and (iii) above, each digit in the second term is nonnegative in all cases, and therefore each of the partial remainder determining circuits 101, 102, 103, 104, 105 . . . can be realized using an addition circuit which handles an ordinary redundant binary number and a redundant binary number each digit of which is nonnegative, and a circuit which determines an addend. In that case, the control signals 251, 252, 253, 254, 255 . . . are q_{j} in the corresponding stages.
Finally, after each digit q_{j} of the quotient has been determined for from j=1 to j=n as described above to obtain the quotient Q=[q_{0}.q_{1} q_{2}. . . q_{n} ]_{SD2}, the quotient (Q) 60 in the SD expression is converted into z=[z_{0}.z_{1} z_{2}. . . z_{n} ]_{r} in an ordinary rradix (i.e. binary) expression by rradix conversion circuit 10. Circuit 10 performs ordinary subtraction Q^{+} Q^{}, that is, circuit 10 subtracts a signless binary number Q^{}, obtained by changing "1" digits to "1" in the quotient Q in the redundant binary expression, from a signless binary number Q^{+}, obtained by leaving the "1" digits in the quotient Q unchanged. Circuit 10 can be realized using ripplecarry addition circuitry or carry lookahead circuitry.
In Case (II) of inversion of the augend (i.e., partial remainder), consider a value A.sup.(j) in place of the partial remainder R.sup.(j), the former being different from the latter only in terms of sign. The value A.sup.(j) will also be referred to hereinafter as a partial remainder. A.sup.(j+1) is defined as follows:
A.sup.(j=1) =p.sup.(j) (r×R.sup.(j))=D.sup.(j),
where p.sup.(j) is a function for effecting sign inversion in accordance with the value of q_{j} described above.
A.sup.(1) =[0.x.sub.1 x.sub.2. . . x.sub.n ].sub.SD2 +[0.y.sub.1 y.sub.2. . . y.sub.n ].sub.SD2
is first calculated in initial partial remainder determining circuit 100 to determine a partial remainder A.sup.(1). It should be noted that x_{1} is a number obtained by inverting the sign of x_{1} for i=1, . . . , n. Since y_{i} is nonnegative at all times for i=1, . . . n, initial partial remainder determining circuit 100 can be realized using an addition circuit which handles an ordinary redundant binary number and a redundant binary number each digit of which is nonnegative. Circuit 100 can also be realized using a subtraction circuit which handles redundant binary numbers each digit of which is nonnegative in the same way is in Case (I). It should be noted that the 1st integral digit of the quotient in the redundant binary expression is q_{0} =1 as in Case (I).
Next, a description will be made of the determination of the jth quotient digit q_{j} from a decimal point and the partial remainder A.sup.(j+1) in the case where the partial remainder A.sup.(j) =[a_{0} ^{j}.a_{1} ^{j} a_{2} ^{j}. . . a_{n} ^{j} ]_{SD2} and the (j1)th decimal digit of q_{j1} of the quotient have already been determined.
The jth decimal q_{j} of the quotient is determined in accordance with the value of the most significant three digits [a_{0} ^{j}.a_{1} ^{j} a_{2} ^{j} ]_{SD2} of the partial remainder A.sup.(j) and the j1th decimal digit q_{jl} of the quotient in the jth cell of the quotientdetermining cells 201, 202, 203, 204, 205 . . . . More specifically, determination is made as follows: if the value of the most significant three digits of A.sup.(j) is positive, q_{j} =sign(q_{j1}); if it is 0, q_{j} =0; and if it is negative, q_{j} =sign(q_{j1}). sign(q_{j1}) is defined as follows: ##EQU4##
In the jth circuit of the partial remainder determining circuits 101, 102, 103, 104, 105 . . . ,
A.sup.(j+1) =p.sup.(j) (2×p.sup.(j1) (A.sup.(j)))+D.sup.(j)
is calculated to determine the partial remainder A.sup.(j+1). It should be noted that the first term of the above equation for A.sup.(j+1) is as follows:
(i) when sign (q_{j1})×sign(q_{j})=1,
p.sup.(j) (2×p.sup.(j1) (A.sup.(j)))=[a.sub.0.sup.j a.sub.1.sup.j.a.sub.2.sup.j. . . a.sub.n.sup.j 0].sub.SD2,
(ii) when sign(q_{j1})×sign(q_{j})=1,
p.sup.(j) (2×p.sup.(j1) (A.sup.(j)))=[a.sub.0.sup.j a.sub.1.sup.j.a.sub.2.sup.j. . . a.sub.n.sup.j 0].sub.SD2,
and the second term is as follows:
(i) when q_{j}≠ 0,
D.sup.(j) =[0.y.sub.1 y.sub.2. . . y.sub.n ].sub.SD2 ;
(ii) when q_{j} =0,
D.sup.(j) =[0.00. . . 0].sub.SD2.
Thus, each digit is a nonnegative redundant binary number. Accordingly, each of the partial remainder determining circuits 101, 102, 103, 104, 105 . . . can be realized using an addition circuit which handles an ordinary redundant binary number and a redundant binary number each digit of which is nonnegative, a circuit which inverts a redundant binary number and a circuit which determines an operand. In that case, each of the control signals 251, 252, 253, 254, 255 . . . which are delivered to the corresponding partial remainder determining circuits is formed in accordance with the size of the corresponding quotient digit q_{j} and as to whether or not q_{j} and q_{j1} are different from each other in terms of sign.
Finally, the quotient in the redundant binary expression, i.e., Q=[q_{0}.q_{1} q_{2}. . . q_{n} ]_{SD2}, is converted into a quotient in the ordinary binary expression, i.e., z=[z_{0}.z_{1} z_{2}, in the rradix conversion circuit 10 in the same way as in Case (I).
The description above was made for performing the Case (II) division method using each of the blocks of the divider embodiment shown in FIG. 1. For Case (I), input signal lines 271, 272, 273, 274 in FIG. 1 for inputting signals to the quotientdetermining cells 202, 203, 204, 205, 206 . . . from respective upper quotientdetermining cells are not used and therefore may be omitted.
FIG. 2 is a block diagram showing an embodiment of the partial remainder determining circuits 101, 102, 103, 104, 105 . . . of FIG. 1. A partial remainder determining circuit 300 is defined by an array of n+1 redundant addition cells 310, 311, 312, 313 . . . 329, 330. Assuming that partial remainder determining circuit 300 is the jth partial remainder determining circuit in the arrangement shown in FIG. 1, inputs 340, 341, 342, 343 . . . 359 corresponding to augends respectively represent values for digits r_{1} ^{j}, r_{2} ^{j}, . . . , r_{n} ^{j} of the partial determined in the previous stage (i.e., the j1th stage), or values for a_{1} ^{j}, a_{2} ^{j}, . . . , a_{n} ^{j}. Inputs 361, 362, 363, . . . , 380 corresponding to addends respectively represent digits y_{1}, y_{2}, . . . , y_{n} of the divisor. Control signal 390 is one of the control signals 251, 252 . . . shown in FIG. 1 and is determined in accordance with the previously determined digit q_{j} or q_{j1} of the quotient in the quotientdetermining cell in the same stage (i.e., the jth stage). Inputs 441, 442, 443, . . . , 450 which are supplied from lowerorder redundant addition cells to higherorder redundant addition cells represent intermediate carries from the lowerorder digits. Outputs 410, 411, 412, . . . , 430 of redundant addition cells 310, 311, 312, . . . , 330 respectively represent the values of digits r_{0} ^{j+1}, r_{1} ^{j+1},r_{2} ^{j+1}, . . . , r_{n} ^{j+1} of the reamainder or values for a_{0} ^{j+1}, a_{1} ^{j+1}, a_{2} ^{j+1}, . . . , a_{n} ^{j+1}. It should be noted that, when r=2, that is, when the binary expression is employed, the 1st decimal digit of the divisor is fixed as y_{1} =1, and therefore input 361 may be omitted. In Case (II), the carry 450 from the final digit may also be omitted.
Redundant addition cells 310, 311, 312, 313, . . . , 329, 330 determine the 1st integral digit, the 1st decimal digit, the 2nd decimal digit, . . . , the nth decimal digit, respectively, of the partial remainder R.sup.(j+1) or A.sup.(j+1). Of these redundant addition cells, cells 312, 313, . . . , 329 for the 2nd decimal digit to the n1th decimal digit may be constituted by basic cells and cells 310 and 311 for the most two significant digits and cell 330 for the least significant digit (i.e., the nth decimal digit) may be constituted by high order cells for the purpose of reducing the number of elements. Further, redundant addition cells 310 and 311 for the two most significant digits may be combined with the quotientdetermining cell in the same stage (i.e., the jth stage) in the form of a single cell, or redundant addition cell 330 for the least significant digit in the jth stage and redundant addition cell 329 for the n1th decimal digit in the j+1th stage may be combined together in the form of a single cell, for the purpose of reducing the number of elements. It is also possible to omit redundant addition cells corresponding to each digit up to the nth decimal digit in the jth partial remainder determining circuit as long as the condition n/2<j≦n1 is satisfied. FIG. 1 shows a first embodiment with such redundant addition cells omitted.
FIG. 3 is a block diagram showing a first embodiment of a basic cell 470 which may constitute each of the redundant addition cells 312, 313, . . . , 329 shown in FIG. 2 for Case (I), that is, in the case of inversion of the addend. Basic cell 470 comprises an addend determining (sign inversion) circuit 472 (first means of the first embodiment) an intermediate sum determining circuit 473 (third means of the first embodiment), an intermediate carry determining circuit 474 (second means of the first embodiment) and a final sum determining circuit 475 (fourth means of first embodiment). Input signal 481 represents the value of the i+1th decimal r_{i+1} ^{j} of the partial remainder R.sup.(j), and since r_{i+1} ^{j} is a redundant binary number, it is a 2bit signal. Input signal 482 is a signal d_{i} which represents the value y_{i} for the ith decimal digit of the divisor. Since y is a binary number, input signal 482 may be a 1bit signal. Control signal 483 represents the jth decimal digit q_{j} of the quotient and may take any one of the values 1, 0 and 1; therefore, control signal 483 is a 2bit signal. Addend signal 485 output by addend determining circuit 472 is a binary number having a 0 or 1 level and is, therefore, a 1bit signal. Signal 486 output by intermediate sum determining circuit 473 is a 1bit signal which represents the intermediate sum S_{i} ^{j} for the ith decimal digit. Signal 487 is a 1bit signal which indicates whether or not there is an intermediate carry from the ith decimal digit. Signal 488 is a 1bit signal which indicates whether or not there is an intermediate carry from the i+1th decimal digit. Output 489 from final sum determining circuit 375 is a 2bit signal which represents the value of the ith decimal digit r_{i} ^{j+1} of the partial remainder R.sup.(j+1).
Addend determining circuit 472 determines the ith decimal digit d_{i} ^{j+1} of the addend in accordance with the value for the jth decimal digit q_{j} of the quotient. More specifically, circuit 472 determines an addend by inversion of sign or alloting a 0 in such a manner that, when q_{j} =1, d_{i} ^{j} =d_{i} ; when q_{j} =0, d_{i} ^{j} =0; and when q_{j} =1, d_{i} ^{j} =1d_{i}.
Intermediate sum determining circuit 473 determines an intermediate sum by redundant addition of a redundant binary augend r_{i+1} ^{j} and an ordinary binary addend d_{i} ^{j}. More specifically, an intermediate sum is determined as shown in Table 1.
TABLE 1______________________________________ Augend (redundant binary number) 1 0 1______________________________________addend 0 1 0 1(binary number) 1 0 1 0______________________________________
Intermediate carry determining circuit 474 determinesan intermediate carry by redundant addition of an augend r_{i+1} ^{j} and an addended d_{i} ^{j}. More specifically, circuit 474 determines an intermediate carry as shown in Table 2.
TABLE 2______________________________________ Augend (redundant binary number) 1 0 1______________________________________addend 0 0 0 1(binary number) 1 0 1 1______________________________________
Final sum determining circuit 475 obtains the sum of the intermediate sum for the ith decimal digit (signal 486) and the intermediate carry from the i+1th decimal digit (signal 488) and determines the value for the ith decimal digit r_{i} ^{j+1} of the partial remainder R^{j+1}.
FIG. 4 is a block diagram showing a second embodiment of a basic cell 510 which may constitute each of the redundant addition cells 312, 313, . . . , 329 shown in FIG. 2 for Case (II), that is, in the case of inversion of the augend. Basic cell 510 comprises a sign inversion circuit 511 (first means of second embodiment), a divisor conversion circuit 512 (second means of the second embodiment), an intermediate sum determining circuit 513 (fourth means of the second embodiment), an intermediate carry determining circuit 514 (third means of the second embodiment) and a final sum determining circuit 515 (fifth means of the second embodiment). Input signal 521 is a 2bit signal which represents the value for the i+1th decimal digit a_{a+1} ^{j} of the partial remainder A.sup.(j). Control signal 523 is a 2bit input signal which represents the size of the jth decimal digit q_{j} of the quotient and indicates whether or not there is a difference in sign between q_{j1} and q_{j}. Input signal 522 is a signal d_{i} which represents the value y_{i} for the ith decimal digit of the divisor. Signal 524 output by sign inversion circuit 511 is a 2bit signal which represents a redundant binary augend e_{i} ^{j}. Signals 525, output by divisor conversion circuit 512 is a 1bit signal which represents a binary addend d_{i} ^{j}. Signals 526, 527 and 528 represent the same things as signals 486, 487 and 488, respectively, shown in FIG. 3. Output signal 529 from final sum determining circuit 515 is a 2bit signal which represents the value of the ith decimal digit a_{i} ^{j+1} of the partial remainder A.sup.(j+1).
Sign inversion circuit 511 determines the i+1th decimal digit a_{i+1} ^{j} of the partial remainder in accordance with the difference in sign between the jth decimal digit q_{j} and j1th decimal digit q_{j1} of the quotient. More specifically, circuit 511 determines an augend by effecting sign inversion in such a manner that, when sign (q_{j1})×sign(q_{j})=1, e_{i} ^{j} =a_{i+1} ^{j}, whereas when sign (q_{j1})×sign(q_{j})=1,e_{i} ^{j} =a_{i+1} ^{j}. In that case, if a_{i+1} ^{j} =1, then a_{i+1} ^{j} =1; if a_{i} ^{j} =0, then a_{i+1} ^{j} =0; and if a_{i+1} ^{j} =1, then a_{i+1} ^{j} =1.
Divisor conversion circuit 512 determines the ith decimal digit d_{i} ^{j} of the addend in accordance with the size of the jth decimal digit q_{j} of the quotient. More specifically, circuit 512 determines an addend by assigning a 0 in such a manner that, when q_{j} ≠0, d_{i} ^{j} =d_{i} whereas when q_{j} =0, then d_{i} ^{j} =0. In that case, d_{i} represents the value for the ith decimal digit y_{i} of the divisor.
Intermediate sum determining circuit 513, intermediate carry determining circuit 514 and final sum determining circuit 515 are similar to circuits 473, 474 and 475, respectively, in FIG. 3.
Initial partial remainder determining circuit 100 in FIG. 1 may basically be embodied similar to partial remainder determining circuits 101, 102, . . . , that is, circuit 100 can be defined by an array of cells which are similar to basic cell 470 (FIG. 3) or basic cell 510 (FIG. 4) adapted for the case of q_{o} =1. It should be noted that, since initial partial remainder determining circuit 100 performs redundant subtraction of ordinary binary numbers or redundant addition of an ordinary binary number and a redundant binary number each digit of which is nonpositive, the intermediate carry for each digit can be made 0 at all times, which makes it possible to simplify the arrangement of each cell.
FIG. 5 is a block diagram showing an embodiment of a quotient determining cell 550 which may constitute the quotient determining cells 201, 202, 203, 204, 205 . . . shown in FIG. 1. Quotient determining cell 550 comprises a quotient determining circuit 551, a sign inversion circuit 552 and a control signal determining circuit 553. Input signals 560, 561 and 562 are 2bit signals which respectively represent r_{0} ^{j}, r_{1} ^{j} and r_{2} ^{j} of the most significant three digits of the partial remainder or a_{0} ^{j}, a_{1} ^{j} and a_{2} ^{j}. Input signal 563 is a 1bit signal which is determined from the j1th decimal digit q_{j1} of the quotient. Signal 564 output by quotient determining curcuit 551 is a 2bit signal which represents a tentative value different in sign from the jth decimal digit q_{j} of the quotient. Output signal 565 from sign inversion circuit 552 is a 2bit signal which represents the value of the jth decimal digit q_{j} of the quotient. Output signal 566 from control signal determining circuit 553 is a 2bit control signal which controls a corresponding partial remainder determining circuit 101, 102 . . . .
Quotient determining circuit 551 determines the tentative value of signal 564 for the jth decimal digit q_{j} of the quotient in accordance with the value [r_{0} ^{j}. r_{1} ^{j} r_{2} ^{j} ]_{SD2} of the three most significant digits 560, 561 and 562 of the partial remainder or the value [a_{0} ^{j}.a_{1} ^{j} a_{2} ^{j} ]. More specifically, when the value of the supper three most significant digits of the partial remainder is positive, the tentative value is 1; when the value of the three most significant digits it is 0, the tentative value is 0; and when the value of the three most significant digits is negative, the tentative value is 1.
Sign inversion circuit 552 may be omitted in Case (I), whereas, in Case (II), circuit 552 effects inversion of sign in accordance with the value of the j1th decimal digit q_{j1} of the quotient to determine the jth decimal digit q_{j} of the quotient. More specifically, when q_{j1} =1, circuit 552 effects sign inversion so that 1 is replaced with 1, and 1 is replaced with 1, whereas, when q_{j1} =1 or 0, circuit 552 outputs the value as it is.
Control signal determining circuit 553 may be omitted in Case (I) since the jth digit q_{j} of the quotient may be used as a control signal without change. In Case (II), circuit 553 determines the size of q_{j} and makes a decision as to whether or not there is a difference in sign between q_{j} and q_{j1}. It should be noted that many portions of circuit 553 are common to those of quotient determining circuit 551; therefore, these two circuits are generally combined to commonly use mutual portions to reduce the number of elements required.
Circuits embodying a basic cell 510 and quotient determining cell 550 are described below in connection with Case II, preceded by an example of binary coding of each of the concerned signals.
One digit a_{i} ^{j}, or q_{j} in a redundant binary expression is expressed by two bits a_{1} ^{j} +a_{i} ^{j} , or q_{j+} q_{j}, respectively, and 1, 0 and 1 are binarycoded into 11, 10 and 01, respectively. At this time, the size and sign of the jth decimal digit q_{j} of the quotient can be represented by q_{j} and q_{j+}, respectively. Further, the signal which indicates whether or not there is a difference in sign between the jth decimal digit q_{j} and j1th decimal digit q_{jl} of the quotient is assumed to be t_{j}. More specifically, it is assumed that, if there is a difference in sign (i.e., when sign (q_{j})×sign(q_{j1})=1), then t_{j} =0, whereas, if there is no difference in sign (i.e., when sign (q_{j})×sign(q_{j1})=1), then t_{j} =1. Accordingly, t_{j} can be determined in control signal determining circuit 553 as follows:
t.sub.j =a.sup.j.sub.0+.(a.sup.j.sub.0 +a.sup.j.sub.1+).(a.sup.j.sub.0 +a.sup.j.sub.1 +a.sup.j.sub.2+)
. a.sup.j.sub.0 +a.sup.j.sub.1 a.sup.j.sub.2 +q.sub.j1+).
Further, q_{j} and q_{j+} can be determined according to the following equations, respectively: ##EQU5## where . , + and ⊕ represent AND, OR and EXOR, respectively, and a_{1} ^{j} +a_{k+} ^{j} and q_{j} are operators representing logical negation of a^{j} _{i} +a^{j} _{k+} and q_{j}, respectively.
Further, the addend d^{j} _{i} on output 525 (FIG. 4), the intermediate sum S_{i} ^{j} on output 526 and the intermediate carry C^{j} _{i} on output 527 can be determined according to the following equations, respectively:
d.sub.i.sup.j =y.sub.j.q.sub.i
S.sub.i.sup.j =a.sub.i+1.sup.j ⊕d.sub.i
C.sup.j.sub.i =(a.sup.j.sub.i+1+ ⊕t.sub.j).a.sub.i.sup.j +1+d.sup.j.sub.i.a.sup.j.sub.i+1.
The output a_{i} ^{j+1} of basic cell 510 can be determined according to the following equations:
a.sub.i+.sup.j+1 =S.sup.j.sub.i+ C.sub.i+1.sup.j
a.sub.i.sup.j+1 =S.sup.j.sub.i ⊕C.sub.i+1 .sup.j
FIG. 6 is a circuit diagram of an embodiment of basic cell 510 shown in FIG. 4 which is realized in the form of a CMOS circuit by virtue of the binary coding described above. Gates 611 and 625 are EXOR gates. Gate 612 is an inverter, gate 613 is twoinput NOR gate, gate 631 is a twoinput NAND gate, and gate 632 is an EXNOR gate. A pchannel transistor 621/nchannel transistor 622 pair and a pchannel transistor 623/nchannel transistor 624 pair constitute transfer gates, respectively.
Further, a_{i+1+} ^{j} on input 601 and a^{j} _{i+1} on input 602 constitute in combination the 2bit input signal 521 shown in FIG. 4, and logical negation y _{i} on input 603 of the ith decimal digit y_{i} is the input signal 522 shown in FIG. 4. Input signals q_{j} on input 604 and t_{j} on input 605 constitute in combination the 2bit control signal 523 shown in FIG. 4. Signal d_{i} ^{j} on output 614 of gate 613 corresponds to the addend 525 shown in FIG. 4. The signals on line 615 (output of gate 611) and on line 602 (output of transistor pairs) represent data corresponding to the augend 524. Signal S^{j} _{i} on output 626 representing an intermediate sum, and signal C^{j} _{i} on output 627 of the transistor pair and C^{j} _{i+1} on inputs 628 to gates 631 and 632 each indicating whether or not there is an intermediate carry, correspond to the 1bit signals 526, 527 and 528, respectively. Signals a_{i+} ^{j+1} on output 633 of gate 631 and a_{i} ^{j+1} on output 634 of gate 632 constitute in combination with 2bit signal 529 (FIG. 4) the ith decimal digit of the partial remainder which is shown in FIG. 4.
Divisor conversion circuit 512 shown in FIG. 4 is constituted by NOR gate 613 in FIG. 6; sign inversion circuit 511 is constituted by EXOR gate 611 and transfer gates 621, 622; the core of the intermediate sum determining circuit 513 is constituted by EXOR gate 625; intermediate carry determining circuit 514 is constituted by inverter 612, transfer gates 621, 622 and transfer gates 623, 624; and final sum determining circuit 515 is constituted by NAND gate 631 and EXNOR gate 632.
It should be noted that, although transfer gates are employed in this embodiment, it is also possible to realize basic cell 510 using ordinary gates.
FIG. 7 shows an embodiment of the transfer gate portion 700 of the circuit shown in FIG. 6 in which portion 700 is constituted by NOR gates. Gates 701, 702 and 703 are 2input NOR gates, gate 701 with inverter 612 constituting a part of sign inversion circuit 511 shown in FIG. 4, while gates 702 and 703 constitute intermediate carry determining circuit 527. However, since the arrangement shown in FIG. 7 leads to an increase in the number of stages and elements of the circuit, composite gates may be employed to realize circuit portion 700 of FIG. 6.
A description of a CMOS circuit embodiment of quotient determining cell 550 shown in FIG. 5, realized by virtue of the abovedescribed binary coding system, will now be made with reference to FIG. 8. In FIG. 8, gate 811 is an inverter, gates 813 and 823 are twoinput NOR gates, gates 814, 815 and 822 are threeinput NOR gates, gates 812 and 821 are fourinput NOR gates, and gate 831 is an EXNOR gate.
Signal a^{j} _{0+} on input 801 and signal a^{j} _{0} on input 802 constitute in combination the 2bit input signal 560 shown in FIG. 5; signal a^{j} _{1+} on output 803 and signal a^{j} _{1} on output 804 constitute the 2bit input signal 561; and signal a^{j} _{2+} on input 805 and signal a^{j} _{2} on input 806 constitute the 2bit input signal 562. Signal q_{j1+} on output 807 corresponds to input signal 563 from a higherorder quotient determining cell shown in FIG. 5. Signal q_{j+} on output 832 and signal q_{j} on output 833 constitute in combination 2bit signal 565 representing the jth decimal digit of the quotient; and signal q_{j} on output 833 and signal t_{j} on output 834 and constitute the 2bit signal for controlling each of the basic cells 510 in the jth stage.
Quotient determining circuit 551 shown in FIG. 5 is constituted by inverter 811 and NOR gates 813, 814 and 815 in FIG. 8, and sign inversion circuit 552 in FIG. 5 is constituted by NOR gate 823 and EXNOR gate 831 in FIG. 8. Control signal determining circuit 553 in FIG. 5 is constituted by inverter 811 and NOR gates 812, 813, 814, 821 and 815 in FIG. 8. It should be noted that inverter 811 and NOR gates 813, 814 and 815 are used in common by quotient determining circuit 551 and control signal determining circuit 553.
Although in the abovedescribed embodiment of a CMOS circuit for Case (II) the same sign is allotted to the partial remainder a^{j} _{i} and the quotient q_{j} in the binary coding, these values may be binarycoded so as to have different signs. A CMOS circuit embodiment for Case (I) can similarly be realized. Although addition of a redundant binary number and an ordinary binary number alone has been described above for Case (II), a similar embodiment can be formed with respect to subtraction of a redundant binary number and an ordinary binary number.
It should be noted that, when the basic cell shown in FIG. 6 employs 6transistor EXOR and EXNOR gates, the number of transistors is 32, and the number of gates on the critical path is 3. In the quotient determining cell shown in FIG. 8, the number of transistors is 50, and the number of gates on the critical path is 2.
Although in the described embodiment the divider is realized by binary logic using CMOS circuits, the present invention can also readily be realized using other kinds of circuitry (e.g., NMOS, ECL, TTL, etc.) or higherradix logics. Further, the present invention can similarly be realized with respect to a multiplier.
According to the present invention, a divider can be realized by combinational CMOS circuitry having an array structure formed from regularly arranged basic cells and quotient determining cells. Each basic cell involves a delay in arithmetic operations required per digit of a quotient equivalent to 5 gates and includes about 30 transistors, and each quotient determining cell includes about 50 transistors.
Accordingly, the divider according to the present invention has a reduced number of transistors which is substantially half of that in the conventional shift, subtract restore, divide units using ripplecarry addition units, and the calculation time (the number of transfer gates) is reduced to about 1/12 and about 1/24 of those of the prior art in the case of division operations with 32 bits and 64 bits, respectively. Further, the number of transistors required in the divider according to the present invention is substantially half of that of the conventional shift, subtract, restore divide units using redundant binary addition and subtraction units.
Thus, the present invention is effective in reducing the number of circuit elements required to form a divider, enabling a divider to be realized compactly on a VLSI chip and increasing operational speed.
According to the present invention, addition and subtraction in an arithmetic operation such as division or multiplication can be realized in the form of a combinational circuitry using either a redundant addition circuit employing, for example, numbers in the signed digit (SD) expression in which each digit is allowed to have a negative value, or a redundant subtraction circuit, and it is possible to minimize carry or borrow propagation in addition or subtraction to one digit at most, thus providing the following advantages:
(1) it is possible to halve the number of elements required to constitute an arithmetic processor;
(2) since addition and subtraction can be performed at high speed within a predetermined period of time irrespective of the number of digits, it is possible to increase the operational speed of the arithmetic processor; and
(3) the arithmetic processor can readily and economically be realized compactly on a LSI chip.
Claims (20)
1. An arithmetic processor which performs addition or subtraction of two redundant signeddigit numbers X and Y of radix r having N digits denoted by single digits x_{i} and y_{i}, where i is an index which assumes integer values ranging from 1 to N to denote digits in descending order, said arithmetic processor for each order comprising:
(a) means for receiving a control signal and a single digit, and in response to the value of said control signal, producing an output operand by either inverting the sign of said single digit, leaving said single digit unchanged, or replacing said single digit operand with 0;
(b) a first arithmetic means for receiving said output operand and for receiving a second single digit, and determining therefrom, in the case of addition an intermediate sum and an intermediate carry, or, in the case of subtraction, determining therefrom an intermediate difference and an intermediate borrow, said intermediate carry or borrow being output by said first arithmetic means for utilization in the processing of the next higher order digits; and
(c) a second arithmetic means for determining the final sum by combining an intermediate carry obtained from processing the digits of the next lower order and said intermediate sum, or in the case of subtraction, determining the final difference by combining an intermediate borrow obtained from processing the digits of the next lower order and said intermediate difference;
whereby said arithmetic processor performs addition or subtraction of said two redundant signeddigit numbers X and Y in a manner which eliminates carrypropagation.
2. An arithmetic processor which performs addition or subtraction of two redundant signeddigit numbers X and Y of radix r having N digits denoted by single digits x_{i} and y_{i}, where i is an index which assumes integer values ranging from 1 to N to denote digits in descending order, said arithmetic processor for each order comprising:
(a) first means for receiving a control signal and a single digit, and in response to the value of said control signal, producing an output operand by either inverting the sign of said single digit, leaving said single digit unchanged, or replacing said single digit with 0;
(b) second means for receiving said output operand from said first means and for receiving a second singledigit and in the case of addition, determining therefrom, an intermediate carry or, in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said second means for utilization in the processing of the next higher order digits; and
(c) third means for receiving said output operand from said first means and for receiving said second single digit, determining therefrom an intermediate sum, or in the case of subtraction, an intermediate difference, and combining the intermediate carry, or in the case of subtraction, the intermediate borrow obtained from the processing of digits of the next lower order with said intermediate sum or difference respectively to determine a final sum or difference;
whereby said arithmetic processor performs addition or subtraction of said two redundant signeddigit numbers X and Y in a manner which eliminates carrypropagation.
3. An arithmetic processor in accordance with claim 2 wherein said first, second and third means are incorporated into each of a plurality of redundant arithmetic cells connected in an array, said array performing addition or subtraction operations on said single digits of said redundant signeddigit numbers X and Y to obtain a sum or difference.
4. An arithmetic processor which performs addition or subtraction of two redundant signeddigit numbers X and Y of radix r having N digits denoted by single digits x_{i} and y_{i}, where i is an index which assumes integer values ranging from 1 to N to denote digits in descending order, said arithmetic processor for each order comprising:
(a) means for receiving a control signal and a single digit, and in response to the value of said control signal, producing a first output operand by either inverting the sign of said single digit or leaving said single digit unchanged;
(b) second means for receiving a control signal and a second single digit, and in response to the value of said control signal, producing a second output operand by either leaving said second single digit unchanged, or replacing said second single digit with 0;
(c) third means for receiving said first and second output operands, and in the case of addition, determining therefrom an intermediate carry, or in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or intermediate borrow being output by said third means for utilization in the processing of the next higher order digits;
(d) fourth means for receiving said first and second output operands, and, in the case of addition determining therefrom an intermediate sum, or in the case of subtraction determining therefrom an intermediate difference; and
(e) fifth means for receiving the intermediate sum or difference from said fourth means and an intermediate carry or borrow from the processing of the next lower order digits and respectively determining therefrom a final sum or difference in the form of a signeddigit number of radix r.
5. An arithmetic processor in accordance with claim 4 wherein said first, second, third, fourth and fifth means are incorporated into each of a plurality of redundant arithmetic cells connecting in an array, said array performing addition or subtraction operations on said single digits of said redundant signed digit numbers X and Y to obtain a sum or difference.
6. An arithmetic processor for performing internal addition or subtraction operations using signeddigit radix r arithmetic on an rradix signeddigit number and an ordinary rradix number, said arithmetic processor comprising:
(a) first means for receiving a control signal and a digit of said ordinary rradix number, and in response to the value of said control signal producing an output digit by either leaving said digit unchanged, replacing said digit with 0, or obtaining the logical inversion of said digit;
(b) second means for receiving said output digit and for receiving a digit of the said redundant signeddigit number, and in the case of addition, determining therefrom an intermediate carry, or in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said second means for utilization in the processing of the next higher order digits;
(c) third means for receiving said output digit and for receiving a digit of said redundant signeddigit number, and determining therefrom in the case of addition, an intermediate sum digit, or in the case of subtraction, determining therefrom an intermediate difference digit; and
(d) fourth means for receiving said intermediate sum or difference digit and an intermediate carry or borrow from the processing of the next lower order digits, and combining said intermediate sum and carry digits, or in the case of subtraction, combining said intermediate difference and borrow digits to determine therefrom a final sum or difference digit in the form of a signeddigit of radix r.
7. An arithmetic processor in accordance with claim 6 wherein the radix r=2.
8. An arithmetic processor in accordance with claim 6, wherein said first, second, third and fourth means are incorporated into each of a plurality of redundant arithmetic cells connecting in an array, said array performing addition or subtraction operations on said single digits of said rradix signeddigit number and said ordinary rradix number.
9. An arithmetic processor in accordance with claim 8, wherein the radix r=2.
10. An arithmetic processor in which a divider performs division in a plurality of stages, said divider having a quotient determining means for determining each digit of a quotient and partial remainder determining means for determining a partial remainder corresponding to each digit of the quotient, said partial remainder determining means for each digit comprising:
(a) first means for receiving a digit of said quotient from said quotient determining means for use as a control signal, and for receiving a digit of an rradix divisor, and determining therefrom an output digit, depending upon the value of said control signal;
(b) second means for receiving a digit of the partial remainder expressed as a signeddigit number of radix r derived from a higher stage operation and said output digit, and determining therefrom an intermediate carry;
(c) third means for receiving a digit of the partial remainder expressed as a signeddigit number of radix r derived from a higher stage operation and said output digit, and determining therefrom an intermediate sum; and
(d) fourth means which combines said intermediate sum with an intermediate carry from a lower order arithmetic operation to determine therefrom one digit of said partial remainder as a signeddigit number of radix r.
11. An arithmetic processor in accordance with claim 10, wherein the radix r=2.
12. An arithmetic processor in accordance with claim 10 wherein said quotient determining means and said partial remainder determining means are incorporated into each of a plurality of arithmetic cells connected in an array, said array performing division.
13. An arithmetic processor which performs addition or subtraction operations utilizing radix r signeddigit arithmetic on a signeddigit number of radix r and an ordinary number of radix r comprising:
(a) first means for receiving a control signal and a digit of said signeddigit number of radix r, and in response to the value said control signal, producing a first output digit by either inverting the sign of said single digit or leaving said single digit unchanged;
(b) second means for receiving a control signal and a digit of said ordinary number of radix r, and in response to the value said control signal, producing a second output digit by either leaving said digit of said ordinary number unchanged, or replacing said digit of said ordinary number with 0;
(c) third means for receiving said first and second output digits, and for the case of addition determining therefrom an intermediate carry or for the case of subtraction determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said third means for utilization in the processing of the next higher order digits;
(d) fourth means for receiving said first and second output digits, and in the case of addition determining therefrom an intermediate sum, or in the case of subtraction determining therefrom an intermediate difference; and
(e) fifth means for receiving the intermediate sum or difference from said fourth means and an intermediate carry or borrow from the processing of the next lower order digits and respectively determining therefrom a final sum or difference in the form of a signeddigit of radix r.
14. An arithmetic processor in accordance with claim 13, wherein said first, second, third, fourth and fifth means are incorporated into each of a plurality of redundant arithmetic cells connecting in an array, said array performing addition or subtraction operations on said single digits of said redundant signeddigit number of radix r and said ordinary number of radix r.
15. An arithmetic processor in accordance with claim 14, wherein said radix r is radix 2.
16. An arithmetic processor of claim 13 in which a divider performs division in a plurality of stages, said divider having a quotient determining means for determining each digit of a quotient and partial remainder determining means for determining a partial remainder corresponding to each digit of the quotient, wherein said partial remainder determining means for each digit comprises:
(a) first means for receiving a digit of said quotient from said quotient determining means for use as said control signal, and a digit of the partial remainder determined in the previous higher stage operation expressed as a signeddigit of radix r and determining therefrom an output digit, depending upon the value of the control signal,
(b) second means for receiving a digit of said quotient from said quotient determining means for use as a control signal, and a digit of a divisor expressed as an ordinary number of radix r, producing therefrom a second output digit of radix r;
(c) third means for receiving said first and second output digits and determining therefrom an intermediate carry or borrow;
(d) fourth means for receiving said first and second output digits and determining therefrom an intermediate sum or difference; and
(e) fifth means for combining said intermediate carry or borrow with said intermediate sum or difference respectively to form a digit of a partial remainder expressed as a signed digit of radix r.
17. An arithmetic processor in accordance with claim 16, wherein said radix r is radix 2.
18. An arithmetic processor in accordance with claim 16, wherein said first, second, third, fourth and fifth means are incorporated in each of a plurality of partial remainder determining cells connected in an array, said array, in combination with said quotient determining means performing division operations.
19. An arithmetic processor in accordance with claim 16, wherein said quotient determining means includes said first means.
20. An arithmetic processor in accordance with claim 13, wherein said radix r is radix 2.
Priority Applications (6)
Application Number  Priority Date  Filing Date  Title 

JP61152452  19860627  
JP61152455A JPH061435B2 (en)  19860627  19860627  Processor 
JP61152455  19860627  
JP61152452A JPH061434B2 (en)  19860627  19860627  Processor 
JP61152451  19860627  
JP61152451A JPH061433B2 (en)  19860627  19860627  Processor 
Applications Claiming Priority (1)
Application Number  Priority Date  Filing Date  Title 

US07/857,644 US5206825A (en)  19870527  19920324  Arithmetic processor using signeddigit representation of external operands 
Related Parent Applications (1)
Application Number  Title  Priority Date  Filing Date  

US07/070,565 ContinuationInPart US4878192A (en)  19860711  19870707  Arithmetic processor and divider using redundant signed digit arithmetic 
Related Child Applications (7)
Application Number  Title  Priority Date  Filing Date 

US07/070,565 ContinuationInPart US4878192A (en)  19860711  19870707  Arithmetic processor and divider using redundant signed digit arithmetic 
US07/074,971 ContinuationInPart US4864528A (en)  19860718  19870717  Arithmetic processor and multiplier using redundant signed digit arithmetic 
US07/074,892 ContinuationInPart US4866655A (en)  19860718  19870717  Arithmetic processor and divider using redundant signed digit 
US07/086,967 ContinuationInPart US4866657A (en)  19860718  19870818  Adder circuitry utilizing redundant signed digit operands 
US07/095,525 ContinuationInPart US4868777A (en)  19860912  19870910  High speed multiplier utilizing signeddigit and carrysave operands 
US07/136,365 ContinuationInPart US4935892A (en)  19861224  19871222  Divider and arithmetic processing units using signed digit operands 
US19931888A ContinuationInPart  19880526  19880526 
Publications (1)
Publication Number  Publication Date 

US4873660A true US4873660A (en)  19891010 
Family
ID=27320276
Family Applications (1)
Application Number  Title  Priority Date  Filing Date 

US07/066,817 Expired  Lifetime US4873660A (en)  19860627  19870625  Arithmetic processor using redundant signed digit arithmetic 
Country Status (1)
Country  Link 

US (1)  US4873660A (en) 
Cited By (8)
Publication number  Priority date  Publication date  Assignee  Title 

US4985861A (en) *  19880129  19910115  Nec Corporation  High speed digital signal processor for signed digit numbers 
US5031136A (en) *  19860627  19910709  Matsushita Electric Industrial Co., Ltd.  Signeddigit arithmetic processing units with binary operands 
US5097434A (en) *  19901003  19920317  The Ohio State University Research Foundation  Hybrid signeddigit/logarithmic number system processor 
US5148480A (en) *  19900214  19920915  Inmos Limited  Decoder 
US5255238A (en) *  19880908  19931019  Hitachi, Ltd.  Firstin firstout semiconductor memory device 
US5365471A (en) *  19910808  19941115  Mitsubishi Denki Kabushiki Kaisha  Divider for performing signed division using a redundant signed digit 
US5416733A (en) *  19940126  19950516  United Microelectronics Corp.  Apparatus for finding quotient in a digital system 
US5619664A (en) *  19940104  19970408  Intel Corporation  Processor with architecture for improved pipelining of arithmetic instructions by forwarding redundant intermediate data forms 

1987
 19870625 US US07/066,817 patent/US4873660A/en not_active Expired  Lifetime
NonPatent Citations (28)
Title 

A Class of Binary Divisions Yielding Minimally Represented Quotients Metze IRE Transactions on Electronic Computers, pp. 761 764 12/62. * 
A Class of Binary Divisions Yielding Minimally Represented Quotients Metze IRE Transactions on Electronic Computers, pp. 761764 12/62. 
A New Class of Digital Division Methods, James Robertson, IRE Transactions on Electronic Computers, pp. 218 222, 9/58. * 
A New Class of Digital Division Methods, James Robertson, IRE Transactions on Electronic Computers, pp. 218222, 9/58. 
A VLSI Oriented High Speed Divider Using Redundant Binary Representation, Takagi, et al, IECE Japan, vol. 167 D 4, pp. 450 457 4/84. * 
A VLSI Oriented High Speed Multiplier Using Redundant Binary Adder Tree, Takagi, et al. IECE Japan, vol. J66.d, pp. 683 690 6/84. * 
A VLSIOriented HighSpeed Divider Using Redundant Binary Representation, Takagi, et al, IECE Japan, vol. 167 D #4, pp. 450457 4/84. 
A VLSIOriented HighSpeed Multiplier Using Redundant Binary Adder Tree, Takagi, et al. IECE Japan, vol. J66.d, pp. 683690 6/84. 
Atkins, "Design of the Arithmetic Units of Illiac III: Use of Redundancy & Higher Radix Methods" IEEE Trans. on Computers, vol. c19 No. 8, Aug. 1970, pp. 720733. 
Atkins, Design of the Arithmetic Units of Illiac III: Use of Redundancy & Higher Radix Methods IEEE Trans. on Computers, vol. c 19 No. 8, Aug. 1970, pp. 720 733. * 
Avizienis, "BinaryCompatible SignedDigit Arithmetic" ProceedingsFall Joint Computer Conference, 1964, pp. 663672. 
Avizienis, Binary Compatible Signed Digit Arithmetic Proceedings Fall Joint Computer Conference, 1964, pp. 663 672. * 
Concise Papers, Lyon, IEEE Transactions on Communications, pp. 418 425, 4/76. * 
Concise Papers, Lyon, IEEE Transactions on Communications, pp. 418425, 4/76. 
Design of High Speed MOS Multiplier and Divider Using Redundant Binary Representation, Kuninobu, et al., Proceedings 8th Symposium on Computer Arithmetic, pp. 80 86, 5/87. * 
Design of High Speed MOS Multiplier and Divider Using Redundant Binary Representation, Kuninobu, et al., Proceedings 8th Symposium on Computer Arithmetic, pp. 8086, 5/87. 
High Speed Multiplier Using a Redundant Binary Adder Tree, Harata, et al. IEEE International Conference on Computer Design, pp. 165 170, 1984. * 
High Speed Multiplier Using a Redundant Binary Adder Tree, Harata, et al. IEEE International Conference on Computer Design, pp. 165170, 1984. 
High Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree, Takagi, et al. IEEE Transactions on Computers, vol. C 34, No. 9, pp. 1789 1795, 9/85. * 
High Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree, Takagi, et al. IEEE Transactions on Computers, vol. C34, No. 9, pp. 17891795, 9/85. 
Multiple Operand Addition and Multiplication, Shanker Singh et al. IEEE Transactions on Computers, vol. C 22, No. 2 pp. 113 120, 2/73. * 
Multiple Operand Addition and Multiplication, Shanker Singh et al. IEEE Transactions on Computers, vol. C22, No. 2 pp. 113120, 2/73. 
Real Time Processing Gains Ground with Fast Digital Multiplier, Waser, et al. Electronics, pp. 93 99, 9/77. * 
RealTime Processing Gains Ground with Fast Digital Multiplier, Waser, et al. Electronics, pp. 9399, 9/77. 
Signed Digit Representations for Fast Parallel Arithmetic, Avizienis, IRE Transactions on Electronic Computers, pp. 389 400, 9/61. * 
SignedDigit Representations for Fast Parallel Arithmetic, Avizienis, IRE Transactions on Electronic Computers, pp. 389400, 9/61. 
Tung "Division Algorithm for SignedDigit Arithmetic" IEEE Trans. on Computers, Sep. 1968, pp. 887889. 
Tung Division Algorithm for Signed Digit Arithmetic IEEE Trans. on Computers, Sep. 1968, pp. 887 889. * 
Cited By (8)
Publication number  Priority date  Publication date  Assignee  Title 

US5031136A (en) *  19860627  19910709  Matsushita Electric Industrial Co., Ltd.  Signeddigit arithmetic processing units with binary operands 
US4985861A (en) *  19880129  19910115  Nec Corporation  High speed digital signal processor for signed digit numbers 
US5255238A (en) *  19880908  19931019  Hitachi, Ltd.  Firstin firstout semiconductor memory device 
US5148480A (en) *  19900214  19920915  Inmos Limited  Decoder 
US5097434A (en) *  19901003  19920317  The Ohio State University Research Foundation  Hybrid signeddigit/logarithmic number system processor 
US5365471A (en) *  19910808  19941115  Mitsubishi Denki Kabushiki Kaisha  Divider for performing signed division using a redundant signed digit 
US5619664A (en) *  19940104  19970408  Intel Corporation  Processor with architecture for improved pipelining of arithmetic instructions by forwarding redundant intermediate data forms 
US5416733A (en) *  19940126  19950516  United Microelectronics Corp.  Apparatus for finding quotient in a digital system 
Similar Documents
Publication  Publication Date  Title 

Takagi et al.  Highspeed VLSI multiplication algorithm with a redundant binary addition tree  
US4878192A (en)  Arithmetic processor and divider using redundant signed digit arithmetic  
EP0316036A2 (en)  Digital multiplier circuit and a digital multiplieraccumulator circuit which preloads and accumulates subresults  
US3610906A (en)  Binary multiplication utilizing squaring techniques  
US4864528A (en)  Arithmetic processor and multiplier using redundant signed digit arithmetic  
US5023827A (en)  Radix16 divider using overlapped quotient bit selection and concurrent quotient rounding and correction  
US5132925A (en)  Radix16 divider using overlapped quotient bit selection and concurrent quotient rounding and correction  
US4495593A (en)  Multiple bit encoding technique for combinational multipliers  
US3711693A (en)  Modular bcd and binary arithmetic and logical system  
US4873660A (en)  Arithmetic processor using redundant signed digit arithmetic  
US4110831A (en)  Method and means for tracking digit significance in arithmetic operations executed on decimal computers  
JP3436994B2 (en)  Shift device  
US4709346A (en)  CMOS subtractor  
JP3313002B2 (en)  Floating point arithmetic unit  
US5251164A (en)  Lowpower areaefficient absolute value arithmetic unit  
US4866655A (en)  Arithmetic processor and divider using redundant signed digit  
US3842250A (en)  Circuit for implementing rounding in add/subtract logic networks  
US4866657A (en)  Adder circuitry utilizing redundant signed digit operands  
Kuninobu et al.  High speed MOS multiplier and divider using redundant binary representation and their implementation in a microprocessor  
US4935892A (en)  Divider and arithmetic processing units using signed digit operands  
US5206825A (en)  Arithmetic processor using signeddigit representation of external operands  
US5031136A (en)  Signeddigit arithmetic processing units with binary operands  
US5153847A (en)  Arithmetic processor using signed digit representation of internal operands  
US3462589A (en)  Parallel digital arithmetic unit utilizing a signeddigit format  
JPH061437B2 (en)  Processor 
Legal Events
Date  Code  Title  Description 

AS  Assignment 
Owner name: MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD., 1006 OAZ Free format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:NISHIYAMA, TAMOTSU;KUNINOBU, SHIGEO;REEL/FRAME:004733/0057 Effective date: 19870616 

STCF  Information on status: patent grant 
Free format text: PATENTED CASE 

CC  Certificate of correction  
FPAY  Fee payment 
Year of fee payment: 4 

FPAY  Fee payment 
Year of fee payment: 8 

FPAY  Fee payment 
Year of fee payment: 12 