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

2. Description of the Related Art Conventionally, as for high-speed dividers, IEICE Transactions, V
ol. J67-D, No. 4 (1984), pages 450 to 457, with each digit being {-
A divider based on a subtractive shift type division method using a redundant binary representation represented by elements of 1,0,1} is an ECL (Emitter-Couple
It is realized as a combinational circuit using a 4-input NOR / OR element of d-Logic). This division circuit is superior to other dividers in terms of calculation time and regular array structure,
No consideration was given to reduction of the number of elements and area, and practical application such as realization with other circuit system (for example, CMOS).

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 for realizing a subtraction shift type divider as a combinational circuit is proposed by taking advantage of the characteristics 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, and the number of stages of the division circuit increases, so high speed is achieved. Is reduced.

There was a problem such as.

An object of the present invention is to improve such conventional problems, to realize a divider with an array structure and as a combinational circuit with a small number of elements, minimize propagation of a carry value, and simplify the circuit configuration. The purpose of this is to provide a high-speed division circuit that is easy to mount 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 the arithmetic processing device provided with the partial remainder determining means, the partial remainder determining means includes (a) an intermediate carry in addition (subtraction) of the number of signed digits for each angular digit of the partial remainder of the signed digit representation ( Intermediate carry (intermediate carry) determining means for determining intermediate carry, (b) intermediate sum (intermediate difference) determining means for determining intermediate sum (intermediate difference) in the addition (subtraction), and (c) The intermediate sum (intermediate difference) obtained by the intermediate sum (intermediate difference) determining means and the intermediate carry (intermediate carry) from the lower digit obtained by the intermediate carry (borrowing) determining means provided in the one-digit lower digit (intermediate carry). Borrow) and add from The final sum (final difference) determining means for determining the result of (subtraction) and outputting it as a signed digit number, and (d) the control signal and the signed digit number or binary number are input, and the value of the control signal By means of a sign inverting means for inverting the sign of the signed digit number or binary number, and the intermediate carry (intermediate carry borrow) determining means and the intermediate sum (intermediate difference) determining means both serve as the sign inverting means. This is accomplished by having the output be at least one common input.

Further, the partial remainder determination means has (e) a constant signal setting means for inputting a control signal and a divisor, replacing the divisor with a constant according to the value of the control signal, and outputting the constant. ) Both the determining means and the intermediate sum (intermediate difference) determining means are achieved by making the output of the constant setting means at least one common input.

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

^{R (j + 1) = r} + R (j) -q j × D where, 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 calculation, the internal calculation number is expressed by using a signed digit (extended SD (Signed Digit)) representation 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 {-0, 0, 1}, {-2, -1,
0,1,2} or {-N, ...,-1,0,1, ...,
It is represented by any element such as N} and has redundancy 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, replace each digit with {-
Addition (decrease) in the extended SD expression represented by the elements of 1,0,1}
In arithmetic, carry (carry) can be set to propagate at most one digit. Regarding this, the Institute of Electronics and Communication Engineers, Journal, Vol. J67-D, No. 4 (1984).
Year) Explain from page 450 to page 457.

A high-speed divider can be realized by using the extended SD expression for the above-mentioned internal operation. At that time, for example, using the extended SD representation of radix 2, 1 bit of the integer part,
An unsigned binary number X having a decimal part of n bits is represented by X = [x ₀ . Expressed in 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 by one digit to the left when q _j = 0, and R ^(j) is shifted to 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, q is provided by means (circuit) for inverting the positive / negative of the internal operation number of the extended SD expression and means for assigning 0 to the internal operation number according to the value of the jth digit q _j below the decimal point of the quotient. The partial remainder R ^{(j + 1)} after determining _j is an extended SD like R ^{(j + 1)} = P _(j) (P ^(j) (r x R ^(j) ) + D ^(j) ). It can be determined only by adding expressions. 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.

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,
When D is an extended SD expression in which each digit is non-negative, it is possible to perform positive / negative inversion by the two's complement display.

Therefore, in the case of (II) above, each digit of D ^(j) is always non-negative, and in the case of (I), by displaying 2's complement, most digits except the leading digit are Since it is possible to make it non-negative, a column of redundant adder circuits (cells) in the one-digit extended SD representation, where one (addition number) is non-negative, is used to determine the partial remainder. Configure the decision circuit. As a result, the number of elements of each redundant adder circuit (cell) can be reduced, and the high-speed divider circuit can be configured as a regular array of these circuits (cells), so that the high-speed divider can be realized as VLSI.

Embodiment An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 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. Incidentally, FIG. 1 is a block diagram in the case of n = 8 and r = 2. In the figure, the dividend 20 is the value x ₁ , x ₂ , ..., X of the first digit, second digit, ..., Nth digit below the decimal point.
_The signals are input to the initial partial remainder determination circuit 100 in the form of signals corresponding to _n . Similarly, the divisor 40 also has the initial partial remainder determining circuit 100 and the partial remainder determining circuit 101 in the form of a signal representing the values y ₁ , y ₂ , ..., Y _n of the first digit, the second digit, ... , 102, 103, 104, 105,
It is input to ... The quotient 60 is output from the conversion circuit 10 to the r-ary as an r-ary number having an integer first digit z ₀ , a decimal point first digit z ₁ , a decimal point second digit z ₂ , ..., And a decimal point n-th digit z _n. It The initial partial remainder determination circuit 100 uses the dividend [0.
x ₁ x ₂ ... X _n ] _r 20 and divisor [0. y ₁ y ₂ ... y _{n] r} 4
It is a circuit which inputs 0 and outputs the partial remainder after deciding the integer first digit of the quotient or the one obtained by inverting the sign of the partial remainder. Particularly, when the dividend and the divisor are normalized, x ₁ = y ₁ = 1 and q ₀ = 1 can be easily obtained. However, q ₀ is a quotient [q ₀ . q ₁ . q ₂ …… q _n ]
It is the first digit of the integer in _SDr . The normalized divisor and divisor will be described below.

Also, the partial remainder determination circuits 101.102, 103, 10
4 and 105 are the 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, 205 respectively corresponding to the same stage. Control signals 251, 252, 253, 254, 255 which are outputs of ...
It is a circuit that receives ... as an input and outputs a partial remainder or an inverted version of the sign of the partial remainder that 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 three digits and the upper stage (that is, j-1) of the partial remainder or the inversion of the sign of the partial remainder output from the partial remainder determination circuit of the upper stage (for example, j-1 stage), respectively.
(Stage) with the value of the j-th digit below the decimal point of the quotient represented in the extended SD expression already determined in the quotient determination cell as input,
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, ... Inputting each digit of the quotient expressed in the extended SD expression determined respectively,
Ordinary r-adic quotient [z ₀ . z ₁ z ₂ … z _n ] _r
This circuit outputs 60.

Next, the division method using these blocks will be briefly described by using mathematical formulas for the above two cases of the method of determining R ^{(j + 1)} .

(I) Inversion of addend (that is, divisor): First, in the initial partial remainder determination circuit 100, R ⁽¹⁾ = [0. x ₁ x ₂ ... x _{n] SD2} - performs the computation of _{[[0, y 1 y 2 ... y} n ] _SD2, determining the partial remainder R ^(1). However, in the above equation, counting is performed in redundant binary (that is, extended SD of radix 2), and R ⁽¹⁾ is a redundant binary number. Also, x ₁ = 1, y ₁ =
Since it is 1, the first digit of the integer of the quotient is q ₀ = 1. Further, since x ₁ , x ₂ , ... X _n , y ₁ , y ₂ , ... Y _n are non-negative, the initial partial remainder determination circuit 100 is a subtraction circuit for redundant binary numbers whose digits are non-negative or a normal one. Can be easily realized by the subtraction circuit of. Further, the determinant of the partial remainder R ⁽¹⁾ is R ⁽¹⁾ = [0. x ₁ x ₂ ... x _{n] SD2} + [0. ▲ ₁ ▼ ▲ ₂ ▼ ... ▲ _n ▼] It is possible to add a redundant binary number with non-negative digits and a redundant binary number like _SD2 . However, ▲ ₁ ▼ means the inversion of y _i . In other words, when y ₁ = 1 ▲ ￣ _O ▼ i =-
1, ▲ ￣ _O ▼ When i = 0, y _i = 0. Where i
Is an integer from 1 to n. Therefore, the initial partial remainder determination circuit 100 can also be implemented as a redundant binary number and a redundant binary number addition circuit in which each digit is non-negative.

Next, now, the partial remainder R ^(j) = [r ₀ ^j , r ₁ ^j r ₂ ^j ... r _n ^j ]
_SD2 and the j-th digit q _j-1 below the decimal point of the quotient have already been determined, and the j-th digit q _j below the decimal point of the quotient and the partial remainder R
The determination of ^{(j + 1)} will be described. However, j is 1 to n
Up to an integer. The jth digit after the decimal point q _j of the quotient is the upper 3 digits of the partial remainder R ^(j) [r ₀ ^j . r ₁ ^j r ₂ ^j ] _SD2 . That is, if the upper 3 digits of R ^(j) are positive, then q _j
If = 1 and 0, q _j = 0, and if negative, q _j = −1. The determination of the j-th digit q _j below the decimal point of this quotient is made by the quotient determination cell 2
Of the cells 01, 202, 203, 204, 205, ...

Further, the partial remainder decision circuits 101, 102, 103, 10
In the _j -th circuit from the higher order of 4, 105, ..., When (i) q _j = -1, R ^{(j + 1)} = [r ₀ ^j r ₁ ^j . r ₂ ^j ... r _n ^j 0] _SD2 + _{[0, y 1 y 2 ... y} n ] _SD2 (ii) when ^{_{q j = 1, R (j}} + 1) = [v ₀ ^j v ₁ ^j .r ₂ ^j ... r _n ^j 1] _SD2 + [0. u ₁ u ₂ ... u _{n] SD2} However, i = 1, ..., with respect to n, a _{u i = 1-y i,} v 0 j and v ₁ the value of ^j when the r ₁ ^j = 1 v _{When j} ⁰ = r ₀ ^j , v ₁ ^j = 0, r ₁ ^j = 0, v ₀ ^j = v ₀ ^j , v
₁ = -1, _{v 0 = 0, v 0 =} 0 when v ₁ ^j = -1.
Here, D = [0. y ₁ y ₂ ... Y _n ] _SD2 is represented by the two's complement notation: = [(-1). 00 ... 1] _SD2 + [0, u ₁ u ₂ ... is based on the fact u _{n] SD2} and expressed.

(iii) When q _j = 0, R ^{(j + 1)} = [r ₀ ^j r ₁ ^j . r ₂ ^j ... R _n ^j 0] _SD2 + [0.00 ... 0] _SD2 is calculated to determine the partial remainder R ^{(j + 1)} . Above (i),
In the formulas for determining the partial remainder R ^{(j + 1)} in (ii) and (iii), in each case, since the second term is non-negative in each digit, the partial remainder determining circuits 101, 102, 103, 104, 105, ...
Can be realized by a redundant binary number and a redundant binary number addition circuit in which each digit is non-negative, a circuit for determining the addition number, and the like.

In this case, the control signals 251, 252, 253, 254,
255, ... Are q _j of the corresponding stages.

Finally, when each digit q _j of the quotient is determined as described above from j = 1 to n and the quotient Q = [q ₀ · q ₁ q ₂ ... q _n ] _SD2 is obtained,
quotient Q expressed in extended SD by the conversion circuit 10 to r-ary
Is a normal r (that is, binary) representation z = [z ₀ · z ₁ z ₂ ...
z _n ] _r 60. The r-adic conversion circuit 10 changes the unsigned binary number Q ⁺ in which only the digit that is 1 in the quotient Q of the redundant binary representation is set to 1 to the digit that is −1 in the quotient Q. The normal subtraction Q ⁺ −Q ⁻ of the unsigned binary number Q ⁻ is performed and can be realized by a carry adder circuit or a carry lookahead adder circuit.

(II) When augend inversion (i.e. partial remainder): Now, consider the partial remainder R ^(j) and only the sign value different A ^(j) in place of the partial remainder R ^(j). Hereinafter, this value is also called a partial remainder. A ^{(j + 1)} is defined as A ^{(j + 1)} = P ^(j) (r × R ^(j) ) + D ^(j) . However, P ^(j) is a function that performs positive / negative inversion according to the value of q _j .

First, in the initial partial remainder determination circuit 100, A ⁽¹⁾ = [0. x ₁ x ₂ ... x _{n] SD2} + [0. y ₁ y ₂ ... y _n]
SD2 is calculated to determine the partial remainder A ⁽¹⁾ . However, i
= 1, ..., N, x ₁ is the number inverted to the sign of x ₁ . 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 a redundant binary number addition circuit in which each digit is non-negative.
Further, as in the case of (I), it can also be realized by using a subtraction circuit for redundant binary numbers in which each digit is non-negative. The first digit of the integer in the redundant binary representation is q ₀ = 1 as in the case of (I).

Next, the partial remainder A ^(j) = [a ₀ . a ₁ a ₂ ... a _n ] _SD2 and the determination of the j-th digit after the decimal point q _j and the partial remainder A ^{(j + 1)} when the j-1 th digit after the decimal point q _{j-1 of the} quotient is already determined explain.

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 ] The value of _SD2 and the decimal point j of the quotient
-1 determined by the digit qj _-1 . That is, if the upper three digits of the value is a positive _{^{A (j) q j = sign}} (-q j-1), 0 if q _j =
If 0 or negative, q _j = -sign (-q _j-1 ) is determined. Tatashi s
ign (-q _j-1 ) is It is defined as

Further, the partial remainder decision circuits 101, 102, 103, 10
In the j-th stage circuit among 4, 105, ..., A ^{(j + 1)} = P ^(j) (2 × P ^(j-1) (A ^(j) )) + D ^(j) is calculated, Determine the partial remainder A ^{(j + 1)} . However,
The first term of the above equation is: (i) sign (-q _j-1 ) × sign (-q _j ) = 1, P ^(j) (2 × P ^(j-1) (A ^(j) ) ) = [A ₀ ^j a ₁ ^j . a ₂ ^j …
a _n ^j 0] _SD2 (ii) sign (-q _j-1 ) × sign (-q _j ) =-1, P ^(j) (2 x P ^(j-1) (A ^(j) )) = [ a ₀ ^j a ₁ ^j . a ₂ ^j …
a _n ^j ] _SD2 , and the second term is (i) q _j ≠ 0, D ^(j) = [0. y ₁ y ₂ ... Y _n ] _SD2 (ii) When q _j = 0, D ^(j) = [0.00 ... 0] _SD2 , and each digit is a non-negative redundant binary number. Therefore, the partial remainder determination circuits 101, 102, 103, 104, 10
5, ... Can be realized by a redundant binary number and a redundant binary number addition circuit in which each digit is non-negative, a redundant binary number inversion circuit, and a circuit for determining the additional number. In this case, each control signal 251, 252, 243, 254, 25 to the partial remainder determination circuit
5, ... Are respectively composed of the size of the corresponding digit q _j of the quotient and the presence / absence of the difference in the signs of -q _j and -q _j-1 .

Finally, the redundant binary representation of the quotient Q = [q ₀ . q ₁ q ₂ ... q _{n]
From SD2 the} usual binary representation z = [z ₀ . The conversion into z ₁ z ₂ ... Z _n ] ₂ is performed in the r-adic conversion circuit 10 in the same manner as in the case of (I).

The above is the description of the division method using the individual blocks constituting the divider shown in FIG. 1. In the case of (I), the first division
Each quotient determination cell 202, 203, 204, 2 in the figure
The input signal lines 271, 272, 273, 274, ... from the upper quotient decision cells to 05, 206, ... Are unused and may be omitted.

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

FIG. 2 is a partial remainder determination circuit 101, shown in FIG.
It is a block diagram showing an example of 1 composition of 102,103,104,105, .... Partial remainder determination circuit 300 (10
1, 102, ...) are n + 1 redundant addition cells 31.
An array of 0, 311, 312, 313, ..., 329, 330. Now, assuming that the partial remainder determination circuit 300 is the j-th partial remainder determination circuit in FIG. 1, the inputs 340, 341, 342, 343, ...
Reference numeral 359 denotes each digit r ₁ ^j , r ₂ ^j , ..., R _n ^{j of} the partial remainder determined in the previous stage (that is, j−1 stage), or
^Represents the values of a ₁ ^j , a ₂ ^j , ..., _An ^j . The inputs 361, 362, 363, ..., 379, 380 corresponding to the number of additions are
Represents each digit y ₁ , y ₂ , ..., Y _n of the divisor. The control signal 390 corresponds to the control signals 251, 252,
, Which is one of the ..., And in the quotient determination cell of the same row (that is, j row), the already determined digit q _j or q _j-1 of the quotient
It is a signal determined from. Inputs 441, 442, 443, ... Of lower redundant addition cells to higher redundant addition cells
Each 450 indicates an intermediate carry from the lower digit. Further, each redundant addition cell 310, 311, 312, ..., 33
The outputs 410 of 0, 410, 411, 412, ..., 430 are respectively the digits r ^{j + 1} ₀ , r ^{j + 1} ₁ , r ^{j + 1} ₂ , ..., R of the partial remainder.
^{j + 1} _n , or a ^{j + 1} ₀ , a ^{j + 1} ₁ , a ^{j + 1} ₂ , ..., a ^{j + 1} _n
Represents the value of. In the case of r = 2, that is, in the case of 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. Further, in the case of (II), the carry 450 of the last digit can be omitted.

Redundant addition cells 310, 311, 312, 313, ...
329 and 330 are the first digit of the integer of the partial remainder R ^{(j + 1)} or A ^{(j + 1)} , the first digit after the decimal point, the second digit after the decimal point,
The cell that determines the nth digit below the decimal point.
Of these redundant addition cells, in order to reduce the number of elements, the redundant addition cells 312, 313, ..., 329 from the second digit after the decimal point to the (n-1) th digit after the decimal point are configured by basic cells,
The two-digit redundant addition cells 310 and 311 and the least significant digit (that is, the nth digit after the decimal point) redundant addition cell 33.
0 may be an exceptional cell. 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 the cell 3 for redundancy addition of the (n + 1) th digit after the decimal point of j + 1 stages
It is also possible to combine 29 into one cell and reduce the number of elements. In addition, for the integer j in the range of n / 2 <j ≦ n−1, in the partial remainder determination circuit of the jth stage, the redundant addition cells after the 2 × (n−j + 1) th digit after the decimal point are added. It may be omitted. FIG. 1 particularly shows an example in which this part is omitted.

Next, the basic cell in the redundant addition cell will be described for each of the cases (I) and (II).

FIG. 3 is a block diagram showing an example of the configuration of the basic cell constituting (I), that is, the redundant addition cells 312, 313, ..., 329 in FIG. 2 in the case of inverting the number of additions.

The basic cell 470 (312, 313, ...) Is composed of an addition number determination circuit 472, an intermediate sum determination circuit 473, an intermediate carry determination circuit 474, and a final sum determination circuit 475. The input 481 is a signal representing the value of the _{i +} ^1th digit r ^j _{i + 1} below the decimal point of the partial remainder R ^(j) . Since r ^j _{i + 1} is redundant binary, a 2-bit signal is required. is there. Input 48
2 is a signal d _i representing the value _i i of the i-th digit after the decimal point of the divisor, and since d _i is a binary number, it may be a 1-bit signal.
Further, the control signal 483 is a signal representing the j-th digit q _j below the decimal point of the quotient, and since q _j can take values of 1, 0 and -1, it must be a 2-bit signal. Addition number 485
Is a 1-bit signal because it is a binary number that takes the values 0 and 1. The signal 486 is the intermediate sum ▲ r ^j _{i of} the i-th digit after the decimal point.
The signal 487 is a 1-bit signal indicating ▼, and the signal 487 is a 1-bit signal indicating whether or not there is an intermediate carry of the i-th digit below the decimal point.
The signal 488 is a 1-bit signal indicating the presence / absence of an intermediate carry from the (i + 1) th digit after the decimal point. Further, the output 489 of the final sum determination circuit 475 is a 2-bit signal representing the value of the i-th digit r ^{j + 1} _i below the decimal point of the partial remainder R ^{(j + 1)} .

The addition number determination circuit 472 is a circuit that determines the _i- th digit after the decimal point d ^j _{i of} the addition number according to the value of the j-th digit after the decimal point q _j of the quotient. That is, when q _j = -1, d ^j _i , q _j = 0, d _{j i} = 0, and q _j = 1 d ^j _i ▼ = 1-d Determine the number of additions.

The intermediate sum determination circuit 473 uses the redundant binary augend ▲ r ^j _{i + 1}
This is a circuit for determining an intermediate sum by performing redundant addition of ▼ and a normal binary addition number ▲ d ^j _i ▼. That is, the intermediate sum is determined as shown in Table 1.

The intermediate carry determination circuit 474 is a circuit that determines an intermediate carry value by performing redundant addition of the augend ▲ r ^j _{i + 1} ▼ and the addition number ▲ d ^j _i ▼. That is, the intermediate carry value is determined as shown in Table 2.

The final sum determination circuit 475 obtains the sum of the intermediate sum of the i-th digit after the decimal point and the intermediate carry value of the i + 1-th digit after the decimal point, and the i-th digit after the decimal point ▲ r ^{j + 1 of the} partial remainder R ^{(j + 1).} _This is a circuit that determines _i ▼.

Next, a similar explanation will be given for the case of (II).

FIG. 4 shows (II), that is, each redundant addition cell 312, 313, ..., 329 in FIG. 2 in the case of inversion of the augend.
FIG. 3 is a block diagram showing a configuration example of a basic cell configuring

The basic cell 510 (312, 313 ...) has a positive / negative inversion circuit 511, a divisor conversion circuit 512, an intermediate sum determination circuit 513,
Intermediate carry determination circuit 514 and final sum determination circuit 515
Composed of. The input 521 is a 2-bit signal representing the value of the _{i +} 1th digit ▲ a ^j _{i + 1} ▼ below the decimal point of the partial remainder A ^(j) , and the control signal 523 is the magnitude of the jth digit q _j below the decimal point of the quotient. , And -q _j-1 and -q _j are 2-bit signals indicating whether or not there is a difference in encoding. The output 524 of the positive / negative inverting circuit 511 is a 2-bit signal representing a redundant binary augend ∑e ^j _i ∘. Further, the output 525 of the divisor conversion circuit 512
Is a 1-bit signal representing a binary addition number ▲ d ^j _i ▼.
Signals 526, 527 and 528 are the same as signals 486, 487 and 488 in FIG. 3, respectively. The output 529 is a 2-bit signal representing the value of the i-th digit ▲ a ^{j + 1} _i ▼ after the decimal point of the partial remainder A ^{(j + 1)} .

The positive / negative inverting circuit 511 determines the _{i +} 1th digit ▲ a ^j _{i + 1} ▼ below the decimal point of the partial remainder according to the difference in the signs of the jth and j−1th digits q _j and q _j−1 below the quotient of the quotient. Circuit. That is, when sign (-q _j-1 ) × sign (-q _j ) = 1, ▲ e
^j _i ▼ = ▲ a ^j _{i + 1} ▼, sign (-q _j-1 ) × sign (-q _j ) =
In the case of -1, positive and negative inversion is performed with ▲ e ^j _i ▼ = ▲ ^j _{i + 1} ▼ to determine the augend. However, if ▲ a ^j _{i + 1} ▲ = -1, The divisor conversion circuit 512 is a circuit that determines the _i- th decimal place ▲ d ^j _i ▼ of the addition number according to the j-th decimal place q _j of the quotient. That is, when q ≠ 0, ▲ d _j ⁱ = d
_{When i} and q _j = 0, the number of additions is determined by assigning 0 so that ▲ d ^j _i ▼ = 0. However, d _i represents the value of the i-th digit y _{i after} the decimal point of the divisor.

Intermediate sum decision circuit 513, intermediate carry decision circuit 514, and final sum decision circuit 515 are the same circuits as 473, 474, and 475 in FIG. 3, respectively.

The above is the partial remainder determination circuits 101 and 10 shown in FIG.
2, 103, 104, 105, ... will be described.

Further, the initial partial remainder determination circuit 100 can basically be configured as an array of cells in the case of q ₀ = 1 in the basic cell 470 or 510, similarly to the partial remainder determination circuits 101, 102, .... . 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.

Next, quotient decision cells 201, 202, 203, 204, 2
The method of configuring 05, ... Will be briefly described.

FIG. 5 shows each quotient determination cell 201, 20 in FIG.
It is a block diagram which shows the structural example of 2,203,204,205 ,.

The quotient decision cell 550 (201, 202 ...) Is composed of a quotient decision circuit 551, a positive / negative inversion circuit 552 and a control signal decision circuit 553. Inputs 560, 561 and 56
2 is the upper 3 digits of the partial remainder ▲ r ^j ₀ ▼, ▲ r ^j ₁ ▼
And ▲ r ^j ₂ ▼, or ▲ a ^j ₀ ▼, ▼ a ^j ₁ ▼ and ▲
The input 563 is a 2-bit signal representing the value of a ^j ₂ ▼, and the input 563 is a 1-bit signal determined from the j-1 th digit q _j-1 below the quotient. The signal 564 is the jth digit q _j below the decimal point of the quotient.
Is a 2-bit signal representing a temporary value having a sign difference.
The output 565 is a 2-bit signal that represents the value of the j-th digit q _j below the decimal point of the quotient, and the output 566 is a 2-bit signal that controls the partial remainder determination circuits 101, 102 ,.

The quotient decision circuit 551 uses the upper three digits 560, 56 of the partial remainder.
The values of 1 and 562 [r ₀ ^j . r ₁ ^j ₁ r ₂ ^j ] _SD2 or [a ₀ ^j . a ₁ ^j a ₂ ^j ] _SD2 is a circuit for determining a provisional value 564 of the j-th digit q _j below the decimal point of the quotient. That is, if the value of the upper 3 digits of the partial remainder is positive, the temporary value is 1, 0 if the temporary value is 0, and if negative, the temporary value is -1.

The positive / negative inverting circuit 552 can be omitted in the case of the above (I), and in the case of the above (II), the j-1th digit q _{j-1 after} the decimal point of the quotient.
It is a circuit that performs positive / negative inversion according to the value of and determines the j-th digit q _j below the decimal point of the quotient. That is, when q _j-1 = 1
Positive / negative inversion is performed by replacing 1 with -1 and -1 with 1.
When q _j-1 = -1,0, the value is output as it is.

In the case of (I), the control signal determination circuit 553 can use the j-th digit q _j of the quotient as it is as a control signal, and thus can be omitted. In the case of (II), the magnitude of q _j , and −q _j and −
This is a circuit that determines whether or not there is a difference in the sign of q _j-1 . Note that the present circuit 553 has many parts in common with the quotient determination circuit 551, and normally, in order to reduce the number of elements, these two circuits are put together and the common part is shared.

The above is the description of the configuration method of the quotient determination cell.

Next, a specific circuit realized according to the above configuration method will be described in the case of (II).

First, an example of binary coding for each signal is shown below.

Redundant binary representation of 1 digit ▲ a ^j _i ▼ or q _j is 2 bits ▲
a ^j _{i +} ▼ ▲ a ^j _i- ▼ or q _{j +} q _j- , respectively, and -1 is 11, 11 is 0, and 1 is 01. At this time, the magnitude and sign of the j-th digit q _j below the decimal point of the quotient can be represented by q _j- and q _{j +} , respectively. Also,
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 defined as t _j . That is, if there is a difference in sign _{(sign (-q j) × sign} (-q j-1) = - when 1), t
_j = 0, otherwise (sign (−q _j ) × sign (−q _j-1 ) =
1), t _j = 1. Therefore, t _j is t _j = a ₀₊ ^j +. (▲ a ^j _0- ▼ + ▲ a ^j ₁₊ ▼). (▲ a ^j _0- ▼ + ▲ a ^j _1- ▼ + ▲ a ^j ₂₊
▼). (▲ a ^j _0- ▼ + ▲ a ^j _1- ▼ + ▲ a ^j _2- ▼ + q _{j-1 +} ). Also, q _j- and q _{j +} are respectively Can be determined by the formula. However, · is the logical product (AND),
+ Is ethical sum (OR), and is exclusive OR (EX-O
R) It is an operator representing the ethical negation of ▲ a ^j _i- ▼ + ▲ a ^j _{k +} ▼ and q _j- .

Further, the addition number ▲ d ^j _i ▼ 525, the intermediate sum ▲ S ^j _i ▼ 526 and the intermediate carry ▲ C ^j _i ▼ 527 in FIG. It can be determined by the formula ^: ▲ a ^{j + 1} _i- ▼ = ▲ S ^j _i ▼ ▲ C ^j _{i + 1} ▼.

FIG. 6 shows the basic cell 5 of FIG. 4 obtained by the above binary coding.
An example of a circuit diagram in which 10 is realized by a CMOS circuit is shown. The gates 611 and 625 are EX-ORs, the gate 612 is an inverter, the gate 613 is a 2-input NOR, the gate 631 is a 2-input NAND, and the gate 632 is an EX-NOR gate. Also, the p-channel transistor 621 and the n-channel transistor 622, and the p-channel transistor 621
Transistor 623 and n-channel transistor 62
Reference numerals 4 respectively constitute transfer gates.

Further, ▲ a ^j _{i + 1 +} ▼ 601 and ▲ a ^j _{i + 1-} ▼ 602 are 2-bit inputs 521 in FIG. 4, and the logical negation y _i 603 of the i-th digit y _i below the decimal point of the divisor is This is the input 522 in FIG. q _j- 604 and t _j 605 are the fourth
A 2-bit control signal in the figure is configured. Also, ▲ d
^j _i ▼ 614 is the addition number 525 in FIG. 4, and signals 615 and 602 give information corresponding to the augend 524. Further, a signal ▲ ^j _i ▼ 626 indicating an intermediate sum or a signal ▲ C ^j _i 627, ▲ C indicating the presence or absence of an intermediate carry.
^j _{i + 1} ▼ 628 corresponds to the 1-bit signal 526 or 527, 528 in FIG. 4, respectively. Output ▲ a
^{j + 1} _{i +} ▼ 633 and ▲ a ^{j + 1} _i- ▼ 634 are 2-bit signals 52 representing the i-th digit after the decimal point of the partial remainder in FIG.
It is 9.

The divisor conversion circuit 512 in FIG. 4 is a NOR gate 613, and the positive / negative inversion circuit 511 is an EX-OR gate 6.
11 and the transfer gates 621 and 622, the kernel of the intermediate sum decision circuit 513 is EX-OR625.
The intermediate carry decision circuit 514 is composed of an inverter 612, transfer gates 621 and 622 and transfer gates 623 and 624, and the final sum decision circuit 515 is composed of a NAND gate 631 and an EX-NOR gate 632.

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

FIG. 7 is an example in which the partial circuit 700 using the transfer gate in FIG. 6 is configured by a NOR gate. Gates 701, 702 and 703 are both 2-input gates, in this case gates 701 and 612.
Represents a part of the positive / negative inverting circuit 511 in FIG. 4, and the gates 702 and 703 form an intermediate carry determining circuit 527. However, as shown in FIG. 7, since the number of stages and the number of elements of the circuit increase, a configuration using a composite gate is also possible.

Next, the implementation of the quotient decision cell 550 of FIG. 5 in a CMOS circuit will be described.

FIG. 8 shows a quotient determination cell 550 by the above-mentioned binary encoding.
FIG. 3 is a CMOS circuit diagram showing one example. In the figure, a gate 811 is an inverter, gates 813 and 823 are 2-input NORs, gates 814, 815 and 822 are 3-input NORs, and gates 812 and 821 are 4-input NOs.
The R gate 831 is an EX-NOR gate.

Further, ▲ a ^j ₀₊ ▼ 801 and ▲ a ^j _0- ▼ 802 are 2-bit inputs 560 in FIG. 5, and ▲ a ^j ₁₊ ▼ 803
And ▲ a ^j _1- 804 are 2-bit inputs 561,
▲ a ^j ₂₊ ▼ 805 and ▲ a ^j _2- ▼ 806 are 2-bit inputs 562. Input q _{j-1 +} 807 is the input signal 563 from the upper quotient decision cell in FIG. Further, the outputs q _{j +} 832 and q _j− 833 are 2-bit signals 565 representing the j-th place after the decimal point of the quotient, and the outputs q _j− 833 and t _j 834 control the basic cells 510 in the j-th stage. It is a bit signal.

Further, the quotient decision circuit 551 in FIG.
1 and NOR gates 813, 814, and 815, and a NOR gate 823 which is a positive / negative inverting circuit 552.
And an EX-NOR gate 831.
In addition, the control signal determination circuit 553 includes inverters 811 and N.
OR gates 812, 813, 814, 821, and 8
It is composed of 15. Inverters 811, N
The OR gates 813, 814, and 815 are commonly used by the quotient decision circuit 551 and the control signal decision circuit 553.

An example of implementation by the CMOS circuit in the case of (II) in this embodiment has been described above. In the above example, in the binary encoding, the partial remainders a ^j _i and the quotients q _j are assigned the same code, but different binary encodings may be performed. Further, also in the case of (II), it can be easily realized by the CMOS circuit. 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 basic cell shown in FIG. 6 is a 6-transistor EX-O.
When R and EX-NOR are used, there are 32 transistors, and the number of gates in the critical path is 3.
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.

Further, in the present embodiment, the divider is realized by the binary logic of the CMOS circuit, but the present invention is not limited to other technologies (for example,
It can be easily realized by using NMOS, ECL, TTL, etc.) or multi-valued logic. Further, the present invention can be similarly implemented for the multiplier.

According to this embodiment, the quotient 1 is obtained by the divider CMOS circuit.
Since the delay required for calculation per digit is about 5 gates, and it can be realized as a combinational circuit of a regular array structure of a basic cell composed of elements of about 30 transistors and a quotient decision cell of about 50 transistors, the carry is carried sequentially. Compared with the conventional subtraction shift type divider using an adder, the number of transistors is about half, about 1/12 in 32-bit division in calculation time (number of stages of gates), and about 1/24 in 64-bit. Furthermore, the number of transistors is about half that of the conventional subtractive shift type divider using the redundant binary adder / subtractor.

Therefore, it is effective in reducing the number of circuit elements of the divider, facilitating VLSI implementation, and speeding up.

Effects of the Invention According to the present invention, the addition or subtraction that appears in the internal operation of division is performed by the redundant addition circuit or the redundant subtraction circuit of the extended SD expression number that allows a negative value in each digit and the normal r-adic number in which each digit is nonnegative. Only one of them can be realized as a combinational circuit, and it is possible to prevent the carry or borrow of each digit of addition and subtraction from propagating at most one digit. Therefore, (1) the number of elements of the arithmetic processing unit can be reduced, 2) Since the addition and subtraction can be processed at high speed in a fixed time regardless of the number of digits, the operation processing device can be speeded up, and further, (3) the operation processing device can be easily and economically integrated into an LSI.

[Brief description of drawings]

1 is a block diagram showing the configuration of an embodiment of the present invention, FIG. 2 is a block diagram showing an example of the configuration of the partial remainder determination circuit of FIG. 1, and FIGS. 3 and 4 are of FIG. FIG. 5 is a block diagram showing the structure of the basic cell in the redundant addition cell, FIG. 5 is a block diagram showing the structure of the quotient determination cell in FIG. 1, and FIG. 6 is a CMOS circuit diagram of the basic cell in FIG. 6 is a diagram for explaining the transfer gate of FIG. 6, and FIG. 8 is a CMOS circuit diagram of the quotient determination 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 ...
Redundant addition cell, 470, 510 ... Basic cell, 472
...... Addition number determination circuit, 511 ... Positive / negative inversion circuit, 512
…… Divisor conversion circuit, 474,514 …… Intermediate carry determination circuit, 473,513 …… Intermediate sum determination circuit, 475,5
15 ... Final sum decision circuit, 551 ... Quotation decision circuit, 55
2 ... Positive / negative inverting circuit, 553 ... Control signal determining circuit.

Claims (9)

[Claims] 1. A quotient determining means for determining one digit of a quotient in division, and a partial remainder determining means for obtaining a remainder for the quotient obtained by the quotient determining means and outputting it as a partial remainder of a signed digit representation. In the arithmetic processing unit, the partial remainder determining means performs (a) intermediate carry (intermediate carry) in addition (subtraction) of the number of signed digits for each digit of the partial remainder of the signed digit representation. Intermediate carry (intermediate carry) determining means for determining, (b) intermediate sum (intermediate difference) determining means for determining intermediate sum (intermediate difference) in the addition (subtraction), and (c) intermediate sum (intermediate sum) Addition from the intermediate sum (intermediate difference) obtained by the difference determining means and the intermediate carry (intermediate borrowing) from the lower order obtained by the intermediate carry (intermediate borrowing) determining means provided in the one-digit lower digit Determine the result of (subtraction) and mark A final sum (final difference) determining means for outputting as a number of digits with a sign, and (d) a control signal and a number of digits with a sign or a binary number are input, and the number of digits with a sign or a binary number is input according to the value of the control signal. And an intermediate carry (borrow) determination means and an intermediate sum (intermediate difference) determination means that both output the sign inversion means to at least one common input. An arithmetic processing unit characterized by: 2. The method further comprises (e) a constant setting means for inputting a control signal and a divisor, and replacing the divisor with a constant according to the value of the control signal and outputting the constant, and an intermediate carry (borrow) determining means. The arithmetic processing device according to claim 1, wherein the intermediate sum (intermediate difference) determining means both use the output of the constant setting means as at least one common input. 3. An intermediate carry (intermediate borrow) determining means determines an intermediate carry (intermediate borrow) in addition (subtraction) of a signed digit number and a binary number, and an intermediate sum (intermediate difference) determining means. Determines the intermediate sum (intermediate difference) in the addition (subtraction). 4. The arithmetic processing unit according to claim 1, wherein 4. The arithmetic processing unit according to claim 3, wherein the sign inverting means sign-inverts the binary divisor according to the value of the control signal. 5. The constant setting means outputs the binary divisor inputted as it is or after replacing it with 0 according to the value of the control signal, and outputs the divisor. Processing unit. 6. A sign inversion means, as the number of signed digits representing a partial remainder, is changed by a value of a 1-bit control signal, or a number of signed digits obtained by inverting a positive / negative sign for each digit of the number of signed digits. The arithmetic processing unit according to any one of claims 1, 2, and 3, which outputs the following. 7. A quotient determining means has a sign reversing means for inputting a control signal and a number of signed digits and inverting the sign of the number of signed digits according to the value of the control signal. The arithmetic processing unit according to claim 6. 8. An intermediate carry (intermediate carry) deciding means, an intermediate sum (intermediate difference) deciding means, a final sum (final difference) deciding means, a sign inverting means and a constant setting means respectively for one digit of internal calculation. The arithmetic processing device according to claim 2, wherein the arithmetic processing device is configured by cells corresponding to the operation of (3) and has an array structure of a plurality of the cells. 9. An arithmetic processing unit according to claim 1, wherein the quotient determining means and the partial remainder determining means have an array structure composed of a plurality of stages.