JPH0614318B2 - Processor - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a high-speed arithmetic operation circuit, and more particularly to an operation processing device having a cell array structure, which is suitable for increasing the speed of a divider and for forming an LSI.

Conventional Technology For the conventional high-speed divider, refer to IEICE Transactions, Vo
l.J67-D, No. 4 (1984), pages 450 to 457, where each digit is {-1, 0, 1}.
ECL (Emitter-Coupled-Logic) is a divider based on the subtraction shift type division method using the redundant binary representation represented by the element
It is realized as a combinational circuit using the 4-input NOR / OR element. Although this division circuit is superior to other dividers in terms of calculation time and regular array structure, it is practical in terms of reduction in the number of elements and area, realization in other circuit systems (for example, CMOS), etc. It was not considered.

Further, a divider that has been put into practical use is realized as a sequential circuit including a subtracter (adder) and a shifter, and is widely used. However, it is well known that these require a huge amount of calculation time when the number of digits of the number of operations increases. On the other hand, in a large-scale computer having a high-speed multiplier, a multiplication-type division method of performing division by repeating multiplication is often used. However, a huge amount of hardware is required to realize this multiplication type division method as a combinational circuit, and it is difficult to put it into practical use.

DISCLOSURE OF THE INVENTION Problems to be Solved by the Invention In the above-mentioned conventional technique, a method of realizing a subtraction shift type divider as a combinational circuit is proposed by taking advantage of the features of an ECL logic element capable of simultaneously taking NOR and OR. However, much attention has not been paid to practical use such as reduction of the number of elements and realization with a MOS circuit, etc. (1) The number of elements becomes enormous when the number of digits in the number of operations increases,
It is difficult to realize with one VLSI chip. (2) When realizing with a MOS circuit that cannot take NOR and OR at the same time, it is necessary to configure OR with two elements of NOR and inverter. Since the number of stages of the division circuit is large, there is a problem that the high speed is deteriorated.

An object of the present invention is to improve such conventional problems, to realize a divider as a combinational circuit having an array structure and a small number of elements, prevent propagation of a carry value, and relatively simple circuit configuration. It is an object of the present invention to provide a high-speed division processing device which is easy to be mounted on an LSI.

Means for Solving Problems The above-mentioned object is to obtain a quotient determining means for determining one digit of a quotient in division and a remainder for the quotient obtained by the quotient determining means, and output it as a partial remainder of a signed digit representation. In an arithmetic processing device having a plurality of stages of partial remainder determining means, the partial remainder determining means includes (a) a signed digit as one of two input operation numbers for each digit of the partial remainder of the signed digit representation. A 1-bit signal A representing the sign of each digit of the number and a 1-bit signal B representing the magnitude of this digit are input to represent an intermediate carry (intermediate carry) in the addition (subtraction) of the calculated numbers. An intermediate carry (borrow) determination means for outputting a 1-bit signal C, and (b) a 1-bit signal B representing the size of each digit of the signed digit number as one of the two input operation numbers. input And (c) the intermediate sum (intermediate difference) determining means, which outputs a 1-bit signal S representing the intermediate sum (intermediate difference) in the addition (subtraction) of the calculated numbers. 1-bit signal S representing the intermediate sum (intermediate difference) obtained in step 1 and intermediate carry (intermediate carry) from the lower carry obtained by the intermediate carry (intermediate carry) determining means provided in the lower digit of one digit. By the final sum (final difference) determining means for determining and outputting the result of addition (subtraction) from the 1-bit signal C representing the above, and (d) the value of the 1-bit control signal F from the quotient determining means of the stage, It has first means for inverting the sign of the input operation number, and (e) second means for replacing the divisor with a constant according to the value of another 1-bit control signal D from the quotient determining means of the stage. Achieved by

Further, the first means inputs the 1-bit control signal F from the quotient determining means of the stage and the partial remainder as an input operation number, inverts the sign of the partial remainder according to the value of the control signal, and outputs the intermediate digit. One of the input operation numbers of the raising (intermediate digit borrowing) determining means is generated, and the second means inputs the divisor and another 1-bit control signal D from the quotient determining means of the stage to control the same. It is desirable to replace the divisor with 0 according to the value of the signal and generate one of the input operation numbers of the intermediate carry (intermediate borrow) determining means and the intermediate sum (intermediate difference) determining means.

Operation The subtraction shift type division method is generally expressed by the following recurrence formula.

R ^{(j + 1)} = where _{^{r × R (j) -q j}} × D, j is the index of the recurrence formula, r is the radix, D is the divisor, q _j
Is the jth digit after the decimal point of the quotient, R ^(j) is the partial dividend before determining q _j , and R ^{(j + 1)} is the partial remainder after determining q _j . Therefore, it provided for each index j recurrence formula, or subtracting D from r × R ^(j) according to the value of the quotient q quotient determined cell for determining _j and q _j, the partial remainder decision circuit or not reduce Can be realized as a combinational circuit. Further, in the internal operation, the internal operation number is expressed by using a signed digit (extended SD (Signed Digit)) expression in which each digit is represented by 0, a positive integer, or a negative integer corresponding to the positive integer. That is, each digit is {-1, 0, 1}, {-2, -1,
0,1,2} or {-N, ...,-1,0,1, ...
, N} etc., and redundancy is provided so that one number can be expressed in any number. Thereby, propagation of carry (carry) can be prevented in subtraction (addition), and parallel subtraction (addition) by the combination circuit can be performed in a constant time regardless of the number of digits of the operation number. For example, in the extended SD expression in which each digit is represented by an element of {-1, 0, 1}, carry (carry) of addition (subtraction) can be made to propagate at most one digit. In this regard,
The explanation is given on pages 450 to 457 of the Institute of Electronics and Communication Engineers, Vol.J67-D, No. (1984).

It is possible to realize a high-speed divider by using the extended SD expression for the above internal calculation. At that time, for example, by using the extended SD representation of radix 2, the integer part 1 bit,
Expressing an unsigned binary number X with n bits in the decimal part as X = [x ₀ , x ₁ ... X _n ] _SD2 , Represents the value. However, each digit x _i is {-1, 0,
1} is an element. In this case, in the above recurrence formula, when representing the divisor D and the partial remainder R ^(j) in the extended SD representation of radix-2, depending on the value of q _j, when the q ^_j = -1 R ^_(j)
Is shifted to the left by one digit, D is added, R ^(j) is shifted to the left by 1 digit when q _j = 0, and R ^(j) is shifted by R when q _j = 1.
After shifting ^(j) to the left by one digit, it is necessary to subtract D.

In the present invention, in particular, 0 is set in the means (that is, the first means) and the internal operation number for inverting the internal operation number of the extended SD expression depending on the value of the jth digit q _j below the decimal point of the quotient. The partial remainder R ^{(j + 1)} after q _j is determined by the allocating means (that is, the second means) is R ^{(j + 1)} = P ^(j) (P ^(j) (r × R ^{( j)} ) + D ^(j) ), it can be determined only by addition of the extended SD representation. Here, P ^(j) is a function that performs positive / negative inversion, and D ^(j)
(j) and P ^(j) have several methods. An example is shown below.

(I) (II) However, is the number obtained by inverting the positive and negative numbers of the expanded SD representation numbers D and X, respectively. The positive / negative inversion in this extended SD expression is set to -1 if the digit is 1, and 1 if it is -1, and 0 is left unchanged. But like D
When is a non-negative extended SD expression, it is possible to perform positive / negative inversion by the two's complement display.

Further, the formula for ^{obtaining the} partial remainder R ^{(j + 1)} is: A ^(j) = P ^(j-1) (R ^(j) ) When A ^(j) is introduced, A ^{(j + 1)} = T ^(j) (2 × A ^(j) ) + D ^(j) can be transformed. However, T ^(j) is a function defined by T ^(j) P (X) = ^(j) (P ^(j-1) (X)) with respect to the extended SD expression number X.

In the formula for determining A ^{(j + 1)} , in the case of (II) above, each digit of D ^(j) is always non-negative, and also in the case of (I) , Most digits except the leading digit can be made non-negative, so the above A ^{(j + 1)}
An adder (cell) in which the augend is an expanded SD expression number (that is, a redundant binary expression number) and the addition number is a non-negative expanded SD expression number (that is, a binary expression number) is used to determine be able to.

At this time, in the addition rule that the carry propagates only one digit,
The intermediate sum is determined according to the rules shown in Table 1, and the intermediate carry is determined according to the rules shown in Table 2.

In the present invention, the redundant binary number Is represented by a 1-bit binary signal representing the sign part thereof and a 1-bit binary signal representing the magnitude (that is, absolute value) of the sign part, so that the intermediate sum determining unit for each digit is redundant An exclusive OR B, which receives a 1-bit binary signal B representing the magnitude of B and a 1-bit binary signal C representing a binary number ▲ d ^j _i ▼
It is possible to configure by +. In addition, the intermediate carry determiner for each digit is set to a redundant binary number. A 1-bit binary signal A representing the sign of and a 1-bit binary signal C representing a binary number ▲ d ^j _i ▼ It is possible to form a switching logic circuit A.B + C., Which receives a 1-bit binary signal B representing the magnitude of B and outputs A or C depending on the value of B. Furthermore, if the intermediate carry from the lower digit is K, the required redundant binary number The 1-bit signal representing the magnitude of can be determined as K · (B · C + ·) + · (· C + B ·) by the exclusive OR circuit, The 1-bit signal representing the sign of can be determined as + (· C + B ·) by the NAND circuit. Therefore, the number of elements of each of the adders (cells) can be reduced, and unnecessary signal lines can be omitted. Therefore, by configuring a division circuit with a regular array structure of these adders (cells), a high-speed division processing device can be realized. LSI
It becomes easy to convert.

Embodiment An embodiment of the present invention will be described below with reference to the drawings.

FIG. 2 is a block diagram showing the configuration of an embodiment of the present invention. Particularly, in this embodiment, an n-digit unsigned r-adic fractional divider will be described. Note that in FIG. 2, n = 8, r
It is a block diagram in case of = 2. In the figure, the dividend 20 is
1st digit, 2nd digit, ... nth digit value x ₁ , X ₂ ,
.., x _n are input to the initial partial remainder determination circuit 100 in the form of signals. Similarly, the divisor 40 is also the first digit, second digit, ..., Nth digit value y ₁ , y ₂ , ...
, Y _n in the form of a signal representing the initial partial remainder determination circuit 10
0 and partial remainder decision circuits 101, 102, 103, 1
It is input to 04, 105, .... Quotient 60 is the first integer
Digit Z ₀ , first digit after decimal point Z ₁ , second digit after decimal point Z ₂ ,
.., which is output from the conversion circuit 10 to the r-ary as the r-ary of the nth digit Z _n below the decimal point. Initial partial remainder determination circuit 10
0 is the dividend [0. x ₁ , x ₂ ... X _n ] r20 and divisor [0. as input _{y 1 y 2 ...... y n]} r40, a circuit for outputting the inverse of the sign of the partial remainder or partial remainder after determining the first digit integer quotient. In particular, when the dividend and divisor are normalized, x ₁ = y ₁ = 1
It can be easily obtained as q ₀ = 1. However, q ₀ is a quotient [q ₀ . It is q ₁ q ₂ ...... q _n] integer first digit _SDR. The normalized divisor and divisor will be described below.

Further, the partial remainder decision circuits 101, 102, 103, 10
4, 105 ... are output of the partial remainder determination circuit (or the initial partial remainder determination circuit 100) in the upper stage of the figure and the divisor 40, and quotient determination cells 201, 202, 203, 204, respectively corresponding to the same stage. Control signals 251, 252, 253, 254, 2 output from 205.
55 ... As an input, it is a circuit that outputs a partial remainder or an inversion of the sign of the partial remainder, which is an input to the partial remainder determination circuit of the next stage (that is, the lower stage).

Quotient decision cells 201, 202, 203, 204, 205
... are the upper 3 digits and the upper stage (that is, the j-1th stage after the decimal point) of the partial remainder or the inversion of the sign of the partial remainder which is the output of the partial remainder determination circuit in the upper stage (for example, j-1 stage). The input is the value of the j-1th digit of the quotient expressed in the extended SD expression already determined by the quotient determination cell of
The value of the j-th digit below the decimal point of the quotient and the control signal 25 for the partial remainder determination circuits of the same stage (that is, j stages), respectively.
It is a circuit for outputting 1, 252, 253, 254, 255, ....

The r-adic conversion circuit 10 includes quotient decision cells 201 and 20.
2, 203, 204, 205, ..., Each digit of the quotient expressed in the extended SD expression determined respectively is input, and each digit is a non-negative ordinary r-ary quotient [Z ₀ . Z ₁ Z ₂ ……
Z _n ] r60 is output.

Next, a division method using these blocks will be described by taking as an example the case where sign inversion is applied to the extended SD representation of the augend.

First, in the initial partial remainder determination circuit 100, A ⁽¹⁾ = [0. _{1 2} ...... _n ] _SD2 + [0. y ₁ y ₂ ……
y _n ] _SD2 is calculated to determine the partial remainder A ⁽¹⁾ . However, i
= 1, ..., N, _i is a number obtained by inverting the sign of x _i . Further, since y _i is always non-negative for i = 1, ..., N, the initial partial remainder circuit 100 can be realized by a redundant binary number and binary number addition circuit. Also x ₁ , ...
, X _n , y ₁ , ..., Y _n are non-negative, the initial partial remainder determination circuit 100 can be easily realized by a subtraction circuit between binary numbers.

Next, the partial remainder A ^(j) = [▲ a ^j ₀ ▼. ▲ a ^j ₁ ▼ ▲ a ^j ₂ ▼
... ▲ a ^j _n ▼] _SD2 and the j-1th digit q after the decimal point of the quotient
_The determination of the j-th digit q _j below the decimal point and the partial remainder A ^{(j + 1)} when _j-1 has already been determined will be described.

The jth digit after the decimal point q _j of the quotient is the quotient determination cell 2 of the jth stage.
01, 202, 203, 204, 205 ...
Upper 3 digits of partial remainder A ^(j) [▲ a ^j ₀ ▼. ▲ a ^j ₁ ▼ ▲ a ^j ₂
▼] It is determined by the value of _SD2 and the j-1th digit q _{j-1 after} the decimal point of the quotient. That, A higher-order three digits of the value is a positive _{^{(j) q j = sign (}} -q j-1), 0 if q _j = 0, negative if q _j =
-Sign (-q _j-1 ) is determined. However, sign (-q _j-1 )
Is It is defined as

Further, the partial remainder decision circuits 101, 102, 103, 10
In the circuit of the jth stage among 4, 105, ..., A ^{(j + 1)} = T ^(j) (2 × A ^(j) ) + D ^(j) is calculated, and the partial remainder A ^{(j + 1) )} Is determined. However,
The first term of the above equation is: (i) sign (−q _j−1 ) × sign (−q _j ) = 1, T ^(j) (2 × A ^(j) ) = [▲ a ^j ₀ ▼ ▲ a ^j ₁ ▼ ▲ a ^j ₂ ▼ ……
▲ a ^j _n ▼ 0] _SD2 (ii) When sign (-q _j-1 ) × sign (-q _j ) =-1, T ^(j) (2 × A ^(j) ) = [▲ b ^j ₀ ▼ ▲ b ^j ₁ ▼ ▲ b ^j ₂ ▼ ……
▲ b ^j _n ▼ 0] It is _SD2 . However, for i = 0, ... N, ▲ b ^j _i ▼ =-
▲ a ^j _i ▼. Also, the second term is: (i) q _j ≠ 0, D ^(j) = [0. When _{y 1 y 2 ...... y n]} SD2 (ii) q j = 0, D (j) = [ a 0.00 ...... 0] _SD2, both D ^(j) is a binary number. Therefore, the partial remainder determination circuits 101, 102, 103, 104, 105,
Can be realized by a redundant binary number and a binary number addition circuit, a redundant binary number inversion circuit, and a circuit that determines the addition number. In this case, each control signal 25 to the partial remainder determination circuit
1, 252, 253, 254, 255, ... Respectively represent the size of the corresponding digit q _j of the quotient, and -q _j and -q _j-1.
It is composed of whether or not there is a difference in sign.

Finally, determine each digit q _{j of the} quotient as above from j = 1 to n, and obtain the quotient Q = [q _o . When _{q 1 q 2 ...... q n]} SD2 is determined, converting circuit the quotient Q normal, extended SD represented by 10 r to r advance (i.e. 2) proceeds representation Z = [Z _0. Z ₁ Z ₂
...... converted to Z _n] r60. R-adic conversion circuit 10
, Only digit to become 1 in the quotient Q of the redundant binary representation of unsigned from binary Q ⁺ you 1, unsigned binary number was 1 only digit to become -1 quotient Q Q ^- Normal subtraction of Q ⁺ −
Q ^- was carried out, it can be realized by a ripple carry adder circuit or the carry look-ahead adder circuit.

The above is the description of the division method using the individual blocks constituting the divider shown in FIG.
Each quotient determination cell 202, 203, 204, 2 in the figure
The input signal lines 271, 272, 273, 274, ... To the 05, 206 ,.

Next, the partial remainder determination circuits 101, 102, 103, 10
4, 105, ... Will be described.

FIG. 3 is a partial remainder determination circuit 101, 1 in FIG.
2 is a block diagram showing a configuration example of 02, 103, 104, 105, .... The partial remainder determination circuit 300 is n +
One redundant addition cell 310, 311, 312, 31
3, ..., 329, 330 arrays. Now, assuming that the partial remainder determination circuit 300 is the j-th partial remainder determination circuit in FIG. 2, the input 340, which corresponds to the augend,
341, 342, 343, ..., 359 are the respective digits ▲ a ^j _{1 of} the partial remainder determined in the previous stage (that is, j−1 stage).
The values of ▼, ▲ a ^j ₂ ▼, ..., ▲ a ^j _n ▼ are represented. Inputs 361, 362, 363, ..., 379, 3 corresponding to the number of additions
Reference numeral 80 represents each digit y ₁ , y ₂ , ..., Y _n of the divisor. The control signal 390 is the control signal 25 shown in FIG.
, 252, ..., and the same row (that is, j
Column _{j j} for which the quotient has already been determined in the quotient determination cell
Alternatively, it is a signal determined from q _j-1 . Inputs 441, 44 from the lower redundant addition cell to the upper redundant addition cell
2, 443, ..., 450 respectively represent intermediate carry from the lower digit. In addition, each redundant addition cell 310, 31
1, 312, ..., 330 outputs 410, 411, 41
2, ..., 430 are each digits of partial remainder Represents the value of. In the case of r = 2, that is, the binary representation, the first digit after the decimal point of the divisor is fixed as y ₁ = 1 and thus the input 361 may be omitted. In addition, depending on the case, it is possible to omit the carry 450 of the last digit.

Redundant addition cells 310, 311, 312, 313, ...
..., 329 and 330 are the first integers of the partial remainders A ^{(j + 1)}
It is a cell that determines the digit, the first digit after the decimal point, the second digit after the decimal point, ..., And the nth digit after the decimal point. Among these redundant addition cells, in order to reduce the number of elements, the redundant addition cell 31 from the second digit after the decimal point to the (n-1) th digit after the decimal point is used.
2, 313, ..., 329 are composed of basic cells, and the top 2
The redundant addition cells 310 and 311 of the digits and the redundant addition cell 330 of the least significant digit (that is, the nth digit after the decimal point) may be exceptional cells. Further, the redundant addition cells 310 and 311 in the upper two digits can be combined into one cell for the quotient determination cells in the same stage (that is, j stages), or the cells in the lowest digit of the j stage can be combined. Redundant addition cell 330 and j +
It is also possible to reduce the number of elements by combining the redundant addition cells 329 of the (n-1) th digit below the decimal point in one stage into one cell. In addition, for the integer j in the range of n / 2 <j ≦ n−1, the redundant addition cells after the 2 × (n−j + 1) th digit after the decimal point are omitted in the partial remainder determination circuit at the jth stage. May be. FIG. 2 shows an example in which this part is omitted.

Next, redundant addition cells 310, 311, 312, ...
The basic cell in 330 will be described.

First, an example of binary signalization of the redundant binary representation number in the embodiment of the present invention will be shown below.

Redundant binary representation 1 digit ▲ a ^j _i ▼ or q _j is 2 bits Or q _{j +} q _j- , respectively, where -1 is 11 and 0 is 1
0 and 1 are represented by 01 and a 2-bit binary signal. At this time, the magnitude and sign of the j-th digit q _j below the decimal point of the quotient are
They can be represented by q _j- and q _{j +} , respectively. Further, a signal indicating whether or not there is a sign difference between the j-th digit q _j and the j-1 th digit q _j-1 below the decimal point of the quotient is t _j . That is, if there is a sign difference (sign
_{(-Q j) × sign (-q} j-1) = - when 1), t _j =
0, (when _{sign (-q j) × sign (} -q j-1) of = 1) no words, and t _j = 1. Therefore, t _j is the quotient decision cells 201, 202, ... Can be determined by. Also, q _j- and g _{j +} are respectively Can be determined by the formula. However, · is the logical product (AND),
+ Is a logical sum (OR), and is an exclusive logical sum (exclusive O
R) and Are each And q _j- are the operators that represent the logical negation.

Further, the i-th decimal point ▲ d ^j _i ▼, the intermediate sum ▲ S ^j _i ▼ and the intermediate carry ▲ C ^j _i ▼ of the addend D ^(j) are respectively Can be determined by the formula. Also, the output of the redundant addition cell Is Can be determined by the formula.

FIG. 1 shows an example of a circuit diagram in which the redundant addition cells 312, 313, ..., 329 of FIG. 3 are realized by a CMOS circuit by the binary signal conversion of the present invention.

The gates 611 and 625 are exclusive OR, the gate 612 is an inverter, the gate 613 is a 2-input NR, and the gate 631.
Is a 2-input NAND and the gate 632 is an exclusive NR gate. Also, p-channel transistor 621 and n
Channel transistor 622, and p-channel transistor 623 and n-channel transistor 6
Each 24 constitutes a transfer gate.

Also, 601 and Reference numeral 602 designates the input 2-bit signals 340, 341, ..., 35 to the i + 1th redundant addition cell from the left in FIG.
9 and the logical NOT _i 6 of the _i th digit y _{i after} the decimal point of the divisor
03 is an input 1-bit signal 36 to the redundant addition cell
1,362, ..., 380. _j- 604 and t
_j 605 constitutes the 2-bit control signal 390 in FIG. Further, the signal 614 is the above-mentioned addition number ▲ d ^j _i ▼, and the signals 615 and 602 are the above-mentioned augends. Give information equivalent to. Further, the signal 626 is a 1-bit signal ▲ ^j _i ▼ that represents an intermediate sum, the signal 627 is a 1-bit signal ▲ C ^j _i ▼ that indicates the presence or absence of an intermediate carry, and the signal 628 is a digit from the digit one digit lower. 1-bit signal representing an intermediate carry Is. output 633 and 634 is a 2-bit signal 410, 411, 412, ..., 43 representing the i-th digit after the decimal point of the partial remainder in FIG.
It is 0.

In this case, 1 representing the size of the jth digit q _j below the decimal point of the quotient
The NOR gate 613 implements an addend determining means for replacing the divisor y _i with 0 by the bit signal q _j- and outputting it. The means for reversing the sign of the augend is an exclusive R gate 61.
It is realized by 1. Further, the intermediate sum determination circuit is composed of an exclusive R gate 625 and an inverter 612,
The intermediate carry decision circuit is the transfer gate 621.
622, transfer gates 623 and 624, and an inverter 612. Furthermore, a 1-bit signal ▲ ^j _i ▼ representing the intermediate sum and a 1-bit signal representing the intermediate carry from the lower digit. 2 bit signal of final sum by inputting When The circuit for outputting is composed of a NAND gate 631 and an exclusive NOR gate 632.

Further, the exclusive R circuit in the figure is replaced with an exclusive NR circuit by various combinations with an inverter,
It is known that D can be replaced with NR in combination with an inverter, or vice versa.

Although the transfer gate is used in this example, it can be realized by using a normal gate.

FIG. 4 is an example in which the partial circuit 700 using the transfer gate in FIG. 1 is configured by a NOR gate. Gates 701, 702 and 703 are both 2-input NR gates. However, since the number of stages and the number of elements of the circuit increase, a configuration using a composite gate is also possible.

Further, the initial partial remainder determining circuit 100 is basically similar to the partial remainder determining circuits 101, 102, ... In the case of t _j = 0, _j- = 0 in the redundant addition cell of FIG. It can be configured as an array of cells. Since the initial partial remainder determination circuit 100 is a redundant subtraction between normal binary numbers or a redundant addition of a normal binary number and a non-positive redundant binary number, the intermediate carry of each digit is always 0. And each cell can be simplified.

FIG. 5 is an example of a redundant subtraction circuit (cell) of binary numbers (that is, x _i and y _i ) forming the initial partial remainder determination circuit 100. In the figure, a signal 711 is a 1-bit signal X _i representing the i-th digit below the decimal point of the dividend, and a signal 712 is a 1-bit signal representing the logical negation of the i-th digit below the decimal point of the divide number.
_i , and signals 731 and 732 are 2-bit signals representing the i-th digit after the decimal point of the initial partial remainder A ^(1). Is. In this example, the redundant subtraction circuit (cell) has a 2-input NAN.
It is composed of a D circuit 721 and an exclusive NR circuit 722.

Next, the quotient decision cells 201, 202, 203 of FIG.
204, 205, ... Will be described.

FIG. 6 shows a quotient determination cell 20 by the above-mentioned binary signalization.
1 is a CMS circuit diagram showing a configuration example of 1, 202, 203, 204, 205, .... In the figure, a gate 811 is an inverter, a gate 813 and a gate 823 are 2-input NORs, gates 814, 815 and 822 are 3-input NRs, gates 812 and 821 are 4-input NRs,
Gate 831 is an exclusive NR.

Also, 801 and 802 is the 2-bit signal 410 in FIG. 3, 803 and 804 is 2 bits 411, 805 and 806 is a 2-bit signal 412. Input q _{j-1 +} 807
Is the input signal 2 from the higher quotient decision cell in FIG.
71, 272, 273, ... Also, the output q _{j +} 8
32 and _j- 833 represent the jth digit after the decimal point of the quotient, 2
Bit signal 565, with outputs _j- 833 and t _j 83
4 is each redundant addition cell 310, 311 and 31 in the jth stage
2, ..., A 2-bit signal for controlling 450. The quotient is determined by the inverter 811 and the NR gate 81.
3, 814 and 815, and in particular the sign inversion circuit is an NR gate 823, an exclusive NR gate 83.
It is composed of 1. Also, control signal 2 bit 3
The 1-bit signal t _j 834 out of 90 is determined by an inverter 811, NR gates 812, 813, 814, 821.
And 815. The remaining 1-bit control signal is a 1-bit signal _j- 8 representing the quotient magnitude.
33 is used as it is.

An example of the CMOS circuit that constitutes the divider according to the present embodiment has been described above. In the above example, in the binary signalization, the partial remainder ▲ a _{j i} ▼ and the quotient q _j are assigned the same code.
Different binary signal conversion may be performed.

Although only the addition of the redundant binary number and the normal binary number has been described in the present embodiment, the embodiment can be similarly created for the subtraction.

The redundant addition cell of FIG. 1 has 32 transistors when using exclusive OR of 6 transistors and exclusive NOR, and the gate of the critical path is 3 gates.
In addition, in the quotient determination cell of FIG.
It is a 0 transistor, and the number of gates in the critical path is two stages.

According to the present embodiment, the CMOS circuit is used as the divider to determine the quotient of about 50 transistors and the basic cell composed of elements of about 30 transistors, with a delay of about 5 gates per digit of quotient. Since it can be realized as a combinational circuit with a regular array structure of cells, compared with the conventional subtraction shift type divider using a sequential carry adder,
The number of transistors is about half, the calculation time (the number of stages of gates) is about 1/12 when divided by 32 bits, and about 1/24 of 64 bits. Further, the conventional binary binary adder / subtractor is used. The number of transistors is about half that of the subtractive shift type divider.

Therefore, it is effective in reducing the number of circuit elements of the divider, facilitating the formation of an LSI, and increasing the speed.

EFFECTS OF THE INVENTION According to the present invention, either the addition or subtraction or the digit shift appearing in the internal operation of division is performed by using either the redundant addition circuit or the redundant subtraction circuit in which at least one of the input digits is the number of signed digit expressions that allows a negative value for each digit. Only one of them can be realized as a combinational circuit, and the carry or borrow of each digit of addition and subtraction can be propagated at most one digit, so (1) the number of elements of the arithmetic processing unit can be reduced, and (2) Since addition and subtraction can be processed at high speed in a fixed time regardless of the number of digits, the speed of the arithmetic processing unit can be increased, (3) the circuit configuration can be relatively simplified, and (4) the LSI of the arithmetic processing unit can be easily implemented. And it can be done economically.

[Brief description of drawings]

FIG. 1 is a schematic circuit diagram of a basic circuit constituting an embodiment of the present invention, FIG. 2 is a block diagram showing a configuration of an embodiment of the present invention, and FIG. 3 is a partial remainder determination circuit of FIG. FIG. 4 is a block diagram showing an example of the configuration, FIG. 4 is a diagram for explaining the transfer gate of FIG. 1, and FIG. 5 is a schematic circuit showing an example of a basic circuit constituting the initial partial remainder determination circuit of FIG. FIG. 6 and FIG. 6 are schematic circuit diagrams showing an example of the quotient determining cell of FIG. 100 ... Initial partial remainder determination circuit, 101, 102, 1
03, 104, 105 ... Partial remainder determination circuit, 201,
202, 203, 204, 205 ... quotient decision cell, 1
0 ... R-adic conversion circuit, 20 ... dividend, 40 ... divisor, 60 ... quotient, 310, 311, 312, 313, 3
29, 330 ... Redundant addition cells, 612, 811 ...
Inverter circuit, 613, 701, 702, 703, 8
12, 813, 814, 815, 821, 822, 82
3 ... NR circuit, 611, 625 ... Exclusive OR circuit, 632, 722, 831 ... Exclusive NOR circuit, 6
31,721 ... NAND circuit, 621,623 ... p
Channel transistor, 622, 624 ... n-channel transistor.

Claims (13)

[Claims] 1. A plurality of quotient deciding means for deciding one digit of a quotient in division, and partial remainder deciding means for obtaining a remainder for the quotient obtained by the quotient deciding means and outputting it as a partial remainder of a signed digit representation. An arithmetic processing unit comprising a stage, wherein the partial remainder determining means (a) for each digit of the partial remainder of the signed digit representation represents (a) one digit of the two digits of the signed digit number. The 1-bit signal A representing the sign part and the 1-bit signal B representing the magnitude of this digit are input, and the 1-bit signal C representing the intermediate carry (intermediate carry) in the addition (subtraction) of the calculated numbers is input. An intermediate carry (borrow) borrow determining means for outputting, and (b) inputting a 1-bit signal B representing the size of each digit of the signed digit number as one of the two input operation numbers, and Addition of An intermediate sum (intermediate difference) determining means for outputting a 1-bit signal S representing an intermediate sum (intermediate difference) in (subtraction), and (c) an intermediate sum (intermediate difference) obtained by the intermediate sum (intermediate difference) determining means. Is added from the 1-bit signal S that represents the intermediate carry (borrow) and the 1-bit signal C that represents the intermediate carry (borrow) from the lower digit obtained by the intermediate carry (borrow) determination means provided in the lower digit of one digit. A final sum (final difference) determining means for determining and outputting the result of (subtraction); and (d) inverting the sign of the input operation number according to the value of the 1-bit control signal F from the quotient determining means of the stage. 1) means, and (e) second means for replacing the divisor with a constant according to the value of another 1-bit control signal D from the quotient determining means of the stage. 2. An intermediate carry (borrowing) determination means inputs two 1-bit signals and outputs either one of them.
The arithmetic processing unit according to claim 1, further comprising a selection circuit for selecting according to the value of the 1-bit signal B representing the magnitude of each digit. 3. An exclusive logic in which the intermediate sum (intermediate difference) determining means inputs a 1-bit signal representing the magnitude of the addend (subtraction) and a 1-bit signal representing the magnitude of the addend (subtraction). The arithmetic processing unit according to claim 1, further comprising a summing circuit. 4. A final sum (final difference) determining means outputs a 1-bit signal S representing an intermediate sum (intermediate difference) and a 1-bit signal C representing an intermediate carry (borrowing from an intermediate carry) from a lower digit of one digit. The arithmetic processing unit according to any one of claims 1, 2, and 3, which has an exclusive OR circuit for inputting. 5. The first means inputs the 1-bit control signal F from the quotient determining means of the stage and a partial remainder as an input operation number, and inverts the sign of the partial remainder according to the value of the control signal. , One of the input operation numbers of the intermediate carry (borrow) determination means is generated, and the second means inputs the divisor and another 1-bit control signal D from the quotient determination means of the stage. , The divisor is replaced with 0 according to the value of the control signal, and one of the input operation numbers of the intermediate carry (intermediate carry) determining means and the intermediate sum (intermediate difference) determining means is generated. The arithmetic processing unit according to claim 1. 6. An exclusive means for inputting a 1-bit signal A representing a sign part of each digit of a signed digit number which is an input partial remainder and a 1-bit control signal F from a quotient determining means. The arithmetic processing unit according to claim 5, further comprising an OR circuit. 7. The quotient determining means inputs a signal representing at most the upper three digits as an input of the partial remainder which is the output of the partial remainder determining means of the preceding stage. Item 2, Item 3, Item 5
The arithmetic processing unit according to any one of items 1 and 2. 8. A code for inputting a 1-bit control signal and a number of signed digits from the quotient determining means of the previous stage, and inverting the sign of the number of signed digits according to the value of the control signal. The arithmetic processing device according to claim 5 or 6, further comprising an inverting means. 9. The quotient determining means inputs a signal representing at most three significant digits of the partial remainder output from the partial remainder determining means of the preceding stage and a 1-bit control signal from the preceding stage quotient determining means. The arithmetic processing unit according to claim 8 characterized by the above-mentioned. 10. An initial partial remainder determining means for inputting a dividend X in binary representation and a divisor Y in binary representation and outputting a signed digit number R ₀ having a difference X−Y as a value. The arithmetic processing unit according to any one of claims 1, 2, 3, 5, and 6 characterized in that. 11. The method according to claim 10, wherein the initial partial remainder determining means generates, for each digit of the binary number, one digit of the signed digit number by subtracting the corresponding digits. Processing unit. 12. An initial partial remainder determining means, for each digit of a binary number, is either a signal A representing the digit and a signal representing a corresponding digit of another binary number or a signal obtained by logically inverting the signal. The arithmetic processing according to claim 10 or 11, further comprising: a logical product circuit having a signal B as an input and an exclusive OR circuit having the signals A and B as an input. apparatus. 13. The method according to claim 1, further comprising a binary conversion means for converting a signed digit number into a binary number.
The arithmetic processing device according to any one of the items 1, 3, 5, and 6.