JPS638826A - Arithmetic processing unit - Google Patents

Abstract

PURPOSE:To contrive to perform the arithmetic processing at a high speed by adding an inverting circuit which inverts the sign of an internal operand in accordance with the value of a control signal or a converting circuit which substitutes the internal operand with 0 in accordance with the value of the control signal to an intermediate carry (intermediate borrow) determining circuit and an inter mediate sum (intermediate difference) determining circuit. CONSTITUTION:One of plural internal operands inputted to an intermediate carry (intermediate borrow) determining circuit 514 and an intermediate sum (difference) determining circuit 513 is inputted to an inverting circuit 511, and the circuit 511 inverts or does not invert the sign of the operand in accordance with the control signal indicating subtraction or addition. Since addition as well as subtraction is executed by only addition (subtraction), the number of elements is reduced. thus, a high-speed arithmetic circuit is constituted.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to an arithmetic processing device, and more particularly to a high-speed arithmetic processing device having a cell array structure and suitable for LSI implementation.

BACKGROUND ART Conventionally, for example, high-speed multipliers are discussed in IEICE Transactions, Voi, 166-D, A6 (1983), pages 683 to 690, and high-speed dividers are discussed in Journal of the Institute of Electronics and Communication Engineers.

Vol, 187-D, jK4 (1984) No. 4
Discussed on pages 50 to 457. These are redundant binary representations (
It is an arithmetic unit that performs multiplication or division using a combinational circuit using a type of extended SD representation. therefore,
Although it is superior to other arithmetic units in terms of calculation processing time and regular array structure, no consideration was given to practical applications such as reduction in the number of elements and area, and implementation in MO3 circuits.

Problems to be Solved by the Invention In the above-mentioned prior art, a method has been proposed for high-speed arithmetic units to realize multiplication or division as a combinational circuit by taking advantage of the feature of ECL logic elements that can perform NOR and OR at the same time. There is not much consideration given to practical aspects such as reduction of the number of elements and implementation using other circuit systems. difficult.

(2) M that cannot take NOR and OR at the same time
When implemented using an O8 circuit or the like, it is necessary to configure the OR with two stages of elements: a NOR and an inverter, which increases the number of stages of arithmetic circuits and increases the calculation delay time.

There are other problems.

The purpose of the present invention is to improve these conventional problems, realize an arithmetic processing unit as a combinational circuit with an array structure and a small number of elements, minimize the propagation of carry values, and simplify the circuit configuration. The object of the present invention is to provide a high-speed arithmetic processing device that can be easily implemented on an LSI.

Means to solve the problem The above purpose is to determine the intermediate carry (borrow) from the augend (subtraction) and addition (subtraction) for each digit in addition (subtraction) in internal operations. A circuit and a circuit for determining the intermediate phase (intermediate difference) are used as calculation means in the first step, and for each digit, the intermediate phase (intermediate difference) obtained in the first step and the intermediate phase from the lower digit are calculated. An inversion circuit or The internal operation number is set to 0 depending on the value of the control signal.
For example, in internal calculation, each digit is converted to 0. The number of internal operations is expressed using an extended S D (Signed Digit) expression expressed as an element of a positive integer and a negative integer corresponding to the positive integer. In other words, each digit is l-1, 0, 1j.

1-2. -1.0, 1.21 or I -N, ,
,−,,,.

It is represented by any element such as -1, 0, 1,..., N1, etc., and redundancy is provided so that one number can be represented in several ways. At that time, the intermediate carry (or intermediate digit borrow) determination circuit and the intermediate phase (or intermediate difference) determination circuit are as follows.
Even if there is a carry (or borrow) from a lower digit, the sum (or difference) of the midpoint (or difference) of that digit and the carry (or borrow) from a lower digit is always one digit. The intermediate carry (or intermediate digit borrow) and intermediate phase (or intermediate difference) of that digit can be determined respectively so that As a result, propagation of carries (or borrows) during addition (or subtraction) can be prevented, and parallel addition (or subtraction) by the combinational circuit can be performed in a fixed time regardless of the number of digits of the operation number. For example, each digit is (-1
, 0, 11 elements, extended SD representation C, redundant 2
In addition (or subtraction), carry (
It is possible to ensure that a -digit borrow, su) is propagated by at most one digit. Regarding this, see the Journal of the Institute of Electronics and Communication Engineers.

Vol, 167-D, 44 (1984) No. 45
Pages 0 to 467 or Journal of the Institute of Electronics and Communication Engineers, Vo.
l.

166-D, A6 (1983), pages 683 to 690.

Further, the inversion circuit inputs - of a plurality of internal operation numbers that are input to the intermediate carry (or intermediate digit borrow) determination circuit and the intermediate phase (including difference) determination circuit, and the operation is subtraction. Depending on the control signal whether it is addition or addition, the sign of the operation number may or may not be inverted. As a result, any addition or subtraction can be performed by only addition (or subtraction), and the number of elements can be reduced.

Further, the conversion circuit can set one of the internal operation numbers to 0 according to the value of the control signal such as 0 or 1. As a result, operations such as shifting the digits of an arithmetic number and multiplying by 0 can be performed using addition (or subtraction), which eliminates the need for a circuit that allocates addition/subtraction and digit shifting in internal arithmetic processing, and the gate of the arithmetic circuit. The number of stages can be reduced.

Therefore, the number of elements and stages of the circuit that determines each digit of each internal operation can be reduced, and a high-speed arithmetic circuit can be constructed as a regular arrangement structure of these circuits, making it possible to implement a high-speed arithmetic processing device on an LSI. .

Implementation - Examples 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. In particular, in this embodiment, a divider for an n-digit unsigned r-adic decimal number will be described. In addition, in FIG. 2, n=8,
It is a block diagram in the case of T=2. In the figure, the dividend 2o is the value x1 of the first digit, second digit, ... nth digit of the decimal point.
．． ! 2. . . . are input to the initial partial remainder determination circuit 100 in the form of signals corresponding to In. Divisor 4
Similarly, 0 is the first decimal place.

2nd digit,..., nth digit value 71, 72+...
..., the initial partial remainder determination circuit 100 and the partial remainder determination circuits 101, 102, 103 in the form of a signal representing yn.
゜104, 106. It is input to... Quotient 6
0 is 1st digit of integer 2 1st digit of decimal point 2 2nd digit of decimal point Z 2 +0a 1p
. . . is output from the r-base conversion circuit 1o as an r-base number with the first digit of the decimal point 2. Initial partial remainder determination circuit 100, dividend [0, xl, x2...In]
, 20 and divisor [o, yl, y2...yn)
This circuit inputs r40 and outputs the partial remainder after determining the first integer digit of the quotient or the partial remainder with its sign inverted. In particular, when the dividend and divisor are normalized, x = 7 = 1, which can easily be determined as zo = 1. Below, normalized dividends and divisors will be explained.

Also, partial remainder determination circuits 101, 102, 103゜10
4, 105, . . . are the upper partial remainder determination circuits (or initial partial remainder determination circuits 1oO
) and the divisor 40 and the quotient determination cells 201, 202, 203, 204, 20 corresponding to the same stage, respectively.
Control signals 251°252.
253, 254, 255, . . . as inputs, and outputs a partial remainder or a partial remainder whose sign is inverted, which is input to the next stage (that is, lower stage) partial remainder determining circuit.

Quotient determination cells 201, 202, 203, 204.

205 ------- are respectively upper stage (for example, j-1
The partial remainder that is the output of the partial remainder determination circuit in the first stage) or the partial remainder with its sign inverted is expressed in the extended SD expression already determined by the upper three digits and the quotient determination cell in the upper stage (that is, the j-1 stage). The value at the 5th to 1st decimal point of the quotient is input, and the value at the 1st decimal point of the quotient and the control signals 251 and 252 for the partial remainder determination circuits at the same stage (that is, 5 stages) are respectively input. 253.254,255.・・・・・・
・This is a circuit that outputs.

The r-adic conversion circuit 1o includes quotient determination cells 201 and 202.
．． 203, 204, 205. ......, each digit of the quotient expressed in the decided extended SD representation is input, and each digit is a non-negative normal r-adic quotient (z o p
This is a circuit that outputs z 1p Z 2...zn]r6o.

Next, a division method using these blocks will be briefly explained.

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

R(j+1)=rxR(j)-9jxD where j is the exponent of the recurrence formula, T is the base number, and D is the divisor.

q. is the jth digit after the decimal point of the quotient. rxR(j) is the partial dividend before determining qJ. H(j+1) is the partial remainder after determining q. Therefore, for each index 1 of the recurrence formula, a quotient determination cell is provided to determine the quotient q, and a partial remainder determination circuit is provided to subtract D from rXR(j) or not (according to the value of Ij). The divider can be realized as a combinational circuit.

A high-speed divider can be realized by using extended SD representation for internal operations such as those described above.

At that time, for example, if an unsigned binary number X with 1 bit for the integer part and n bits for the decimal part is expressed as represents the value Σ z%2-i, i=
.

vinegar. However, each digit xi is an element of 1-1, 0.11. In this case, in the above recurrence formula, if the divisor and each partial remainder H(j) are expressed in base-2 extended SD representation, q,
Depending on the value of q, when = -1, H(j)]
] After shifting 1 digit to the left,
It is necessary to add D, shift R('') one digit to the left when q = O, shift R(j) one digit to the left when q = 1, and then subtract D. There is.

In the present invention, in particular, q, The partial remainder H(j+1) after determining is HN+1)=1)(p(D(, xH(i)) +D(i
)), it can be determined only by addition of extended SD expressions. Here, p(j) is a function that performs positive/negative inversion.

Now, consider a value A(1) for the partial remainder H(i) that differs from the partial remainder H(i) by a sign. Hereinafter, this value will also be referred to as a partial remainder. A(j”1) is A(j+1)=p(t)(rxH(j))+7j)
It is defined as However, PO) is a function that performs positive/negative inversion depending on the value of q.

First, in the initial partial remainder determination circuit 10o, A(1)
= [o”1 “2””””n] S D2 + [01y
, l72""" yn)S Calculate D2 and determine the partial remainder A(1).However, i=1.
.For n, i is a number with the sign of X inverted. Furthermore, i=1. Since y is always non-negative with respect to n, the initial partial remainder circuit 100 is redundant 2
This can be realized using an adder circuit for redundant binary numbers in which the base numbers and each digit are non-negative. Also,! 1p! 2.

・・・・・・p ”n+ 71 * V2 p・・・・
...Since t7B is non-negative, the initial partial remainder determination circuit 1
00 can be realized by a subtraction circuit between redundant binary numbers (that is, binary numbers) in which each digit is non-negative, that is, a normal subtraction circuit. In addition,
Since x1=1°y1=1, the first integer digit of the quotient in redundant binary representation is q0=1.

Next, partial remainder A(D=(,Δ,a4.at,,0..
．． ai]2 n Sn2 and the 5th digit of the decimal point qj and the partial remainder A(i” when Ii-1 has already been determined)
The decision in 1) will be explained.

The fifth decimal place q5 of the quotient is the quotient determination cell 201 in the first row.
．． In 202, 203, 204, 205, old...
Upper 3 digits of partial remainder A(j) '@'``1,'' 2]S
D2 (1') value and quotient decimal point cylinder j-1 digit qj-1
determined by If the upper three digits of A(j) are positive, then q, = siqn(-q j, ), O
If q,=O, if negative] q-=-siqn(-q3,) is determined. However, 5iqn(-q5, ) is defined as follows.

Also, partial remainder determination circuits 101, 102, 103゜10
4.106. In the first stage circuit, A(j+1)=p(j)(2XP Cj-1)(A(
i)) )+D(i)H+1) to determine the partial remainder A. Dashi,
The first term in the above equation is: (i) sign(-q, -1)Xsign(-q,
)=1, P(j)(2XP (” ” (A”)
) = (aL, aj, a, knee a, :Q] SD2 (4
) siqn(-qH-1)Xsign(-q,)=-
1, and the second term is: (i) When qHHO2, D(D=[0,y #3'=-”・yn)sD2(4
) When q, = o, mj) = (o, o, o...-o] SD2, and each digit is a non-negative redundant binary number. Therefore, partial remainder determination circuits 101, 102, 103, 104゜105
, . . . can be realized by an addition circuit for a redundant binary number, a redundant binary number in which each digit is non-negative, an inversion circuit for the redundant binary number, and a circuit for determining the number to be added. In this case, each control signal 261° 252, 263, 254 to the partial remainder determination circuit
, 255... are the corresponding digits q of the quotient, respectively.
and −q, and −((j−.

J It consists of whether or not there is a difference in sign.

Finally, each digit q of the quotient is determined as above from j=1 to n, and the quotient Q=Cq, q, q...qn)
sD2] 0 1
2 is found, the conversion circuit 1o to r-adic converts the extended S
The quotient Q represented by D is expressed as the normal r (that is, binary) representation Z=[
Convert to zO"1.z2"..."zn)r 6o.

The conversion circuit 1o to r-adic converts an unsigned binary number Q+, in which only the digits that are 1 in the quotient Q of the redundant binary representation are set to 1, to 1 only for the digits that are -1 in the quotient Q. It performs ordinary subtraction Q+-Q- of an unsigned binary number Q-, and can be realized by a sequential carry-addition circuit or a carry-look-ahead addition circuit.

The above is an explanation of the division method using the individual blocks constituting the divider shown in FIG.・
Input signal line 2 from the upper quotient determination cell to...
71.272,273,274. . . . may be omitted if not used.

Next, partial remainder determination circuits 101, 102, 103°10
4.105. ...... will be explained.

FIG. 3 shows each partial remainder determining circuit 101 in FIG.
102, 103, 104, 105. It is a block diagram showing an example of the configuration of -. Partial remainder determination circuit 30
0(101,102,103,...) is n+
1 redundant addition cell 310, 311, 312, 313
, 329, 330 arrays. now,
If the partial remainder determination circuit 300 is the first stage partial remainder determination circuit in FIG. 2, the input 3 corresponding to the augend
40.341.342,343 , 35
9 is the input 361, 362, 363, . ..., 379
, 380, each digit of the divisor is 71.72 y...
...represents yyn. Control signal 390 is similar to control signals 251, 252, . . . in FIG. ......, and in the quotient determination cell of the same stage (that is, the j stage),
This is a signal determined from the already determined digit q or q51 of the quotient. Inputs 441, 442, 443 from the lower redundant addition cell to the upper redundant addition cell.・・・・・・
.

450 each represents an intermediate carry from the lower digit. In addition, each redundant addition cell 310, 311, 312°...
..., 33o output 410, 411.412.・・・・・・
-1430 is each digit rj+1 of the partial remainder.
rj+1°r2.・・・・・・”n' or・
54-1・a! +1・j+1 j+1 , =+1. ......, represents the value of j+1. Note that in the case of r=2°, that is, in binary representation, the first digit of the decimal point of the divisor is fixed as y1=1, so the input 361 may be omitted. It is also possible to omit the carry 450 of the last digit.

Redundant addition cells 310, 311, 312, 313°...
..., 329, 330 determine the first digit of the integer, the first digit of the decimal point, the second digit of the decimal point, and the first digit of the decimal point of the partial remainder \HN+1) or A(j+j), respectively. This is the cell that does this. Among these redundant addition cells, in order to reduce the number of elements, redundant addition cells 312, 313, .

329 may be made up of basic cells, and the redundant addition cells 310 and 311 of the upper two digits and the redundant addition cell 330 of the lowest digit (that is, the first decimal point) may be made into exceptional cells. Furthermore, it is also possible to combine the redundant addition cells 310 and 311 of the upper two digits with the quotient determination cells of the same stage (that is, the j stage) into a single cell, or to It is also possible to reduce the number of elements by combining the redundant addition cell 330 and the n-1 decimal point redundant addition cell 329 of the j+j stage into one cell. Also, n/2<i≦n-
For an integer j in the range of 1, the redundant addition cells after 2x(n-j+1) digits of the decimal point may be omitted in the first stage partial remainder determination circuit. FIG. 2 particularly shows an example in which this part is omitted.

FIG. 1 shows each redundant addition cell 312.3 in FIG.
13. ..., constitutes 329. FIG. 2 is a block diagram showing an example of the configuration of a basic cell.

The basic cell 510 (312, 313, . . . ) includes a positive/negative inversion circuit 511, a divisor conversion circuit 612, an intermediate phase determination circuit 513, an intermediate carry determination circuit 514, and a final sum determination circuit 515. Input 521 is partial remainder A
(This is a 2-bit signal that confirms the value 1+1 of the decimal point cylinder 1-1-1 digit a! of D, and the control signal 523 is the size of the first decimal point q1 of the quotient, and -93-1 and -C4j
This is a 2-bit signal indicating whether or not there is a difference in sign from the .

The output 524 of the positive/negative inversion circuit 511 is the redundant binary augend e! This is a 2-pit signal representing . Further, the output 525 of the divisor conversion circuit 512 is a 1-pit signal representing the binary addition number dl. The signal 526 is the intermediate phase S of the first decimal place.
The signal 527 is a 1-bit signal representing the presence or absence of an intermediate carry of the first digit of the decimal point.
The signal 528 is a 1-bit signal indicating the presence or absence of an intermediate carry from the i+1 digit of the decimal point cylinder. Output 529 is partial remainder AH
+1), the first decimal place, is a 2-bit signal representing the value of j+1.

The positive/negative inversion circuit 511 converts the partial remainder decimal point i+1 digit a! according to the difference in sign of the quotient decimal point i, i-1 digit qj r qj-1. This is a circuit that determines the

1+1 In other words, sign(-q, , )Xsign(-q
, )=1, -j e, -al, 1. sign(-q, )xsign(
−q, )= −1] −1+, perform the positive/negative inversion as ・j=5, and add the addend 1
1+1 Determine the number. However, if ai=-1, ai=1
゜l+1 t+1j
] If a, = 0, then a, = O, aj = 1, then l
+1 1+1
1 +1・! =-1.

The 1+1 divisor conversion circuit 512 is a circuit that determines the first decimal point dl of the addition number according to the size of the first decimal point digit (Ij) of the quotient. In other words, when (J":O, dl=d −, q,
= C1) when d! = 0 so that Ol 1
] Determine the number of additions by assigning 1. However, di represents the value of the first decimal place y0 of the divisor.

The intermediate phase determination circuit 513 is a circuit that determines the intermediate phase of the redundant binary augend. That is, the intermediate phase is determined as shown in Table 1.

Table 1 Intermediate carry determination circuit 514, augend a! This circuit determines an intermediate carry value by redundant addition of l+1 and the number of additions dl. That is, the intermediate carry value is determined as shown in Table 2.

Table 2 The final sum determination circuit 615 calculates the sum of the intermediate phase of the first decimal place and the intermediate carry value of the decimal point cylinder i+1 digit, and calculates the partial remainder A(
This is a circuit that determines the first decimal place j+1 of 1+1).

The above is the partial remainder determination circuit 101 and 102 shown in FIG.
．． 103, 104, 105. This is an explanation of the construction method of .

Further, the initial partial remainder determination circuit 100 basically consists of partial remainder determination circuits 101, 102 . ·····alike,
q in basic cell 510. =1 can be configured as an array of cells. The initial partial remainder determination circuit 100 performs normal redundant subtraction between binary numbers or
Since it is a redundant addition of a normal binary number and a redundant binary number where each digit is uncompressed, the intermediate carry of each digit can always be 0,
It is possible to simplify each cell.

Next, quotient determination cells 201, 202, 203, 204゜2
o6. The construction method of ... will be briefly explained.

FIG. 4 shows each quotient determination cell 201゜20 in FIG.
2. It is a block diagram showing an example of the configuration of 203, 204, 206, . . . .

The quotient determining cell 650 (201, 202, . . . ) includes a quotient determining circuit 661, a positive/negative inverting circuit 562, and a control signal determining circuit 653. Input 660°561
and 662 are the first three digits rj, j and rj of the partial remainder, or aj, j and ajol, respectively.
2 01
The input signal 563 is a 2-bit signal representing a value of 2, and the input 563 is a 1-bit signal determined from the decimal point j-1 digit q5-1 of the quotient. The signal 564 is a 2-bit signal representing a provisional value whose sign is different from the first decimal place of the quotient (Ij).
The output 56I5 is a 2-pinto signal representing the value of the first decimal point CJ of the quotient, and the output 566 is the partial remainder determination circuit 101,
102. This is a 2-bit signal that controls...

The quotient determination circuit 551 calculates the first three digits of the partial remainder 560゜j
j j 661 and 562 values Cr , r , r )
This circuit determines the provisional value 664 of the quotient decimal point 12SD2 j-th digit qj by A12SD2''jj or Ca+''r'').

In other words, if the upper three digits of the partial remainder are positive, the temporary value is 1.
If it is 0, the temporary value is 0, and if it is negative, the temporary value is -1.

The positive/negative inversion circuit 552 performs positive/negative inversion according to the value of the quotient decimal point Wj - 1st digit q11, and converts the quotient decimal point 1st digit (ij
This is a circuit that determines the That is, when q, , = 1, the positive/negative inversion is performed to replace 1 with -1 and -1 with 1, and when qi 1''' r O, the value is output as is.

The control signal determination circuit 553 determines (the magnitude of Ij and -
This is a circuit that determines whether there is a difference in sign between q., -q, and -1. Note that this circuit 553 is the quotient determination circuit 55
These two circuits have many parts in common with 1, and in order to reduce the number of elements, these two circuits are usually combined to share the common parts.

The above is an explanation of the method for configuring the quotient determination cell.

Next, a specific circuit realized according to the above configuration method will be explained.

First, an example of binary encoding for each signal will be shown below.

1 digit a in redundant binary representation! In other words, q, 2 bottles l
] To, ] eel, or q, q, respectively, and 1+
Binary code l-3+3--1 as 11, 0 as 10, and 1 as 01. At this time, the size and sign of the first decimal point qj of the quotient are:
Represented by q and 'J+, respectively]-. Also, the first decimal place of the quotient (Tj and j -1 digit C
! Let 13 be the signal indicating the presence or absence of a difference in sign from j.

In other words, if there is a difference in sign, then (sign(-q,)Xs
i helmet'(il-1)"-1), if tj=o1, then (sign(-q,)X+ign(-q,-1)=1
, (ai + a' + a' ) - (a' + a' +
a' +q,) -c 0- 1- 2+
O-1-2-1-1+ can be determined. Also, qj−, qH+
can be determined by the following equations: j j j q , -=a, , +shadow-+a2-, respectively. However, ・represents logical product (AND),
+ represents a logical sum (OR), and ■ represents an exclusive logical sum a! +Δ!
and q, is an operator representing the logical negation of 1-1+]-.

Furthermore, the number of additions d in FIG. 1: s2s, the intermediate phase si
526 and intermediate carry ci 627 are respectively d1=a1. q.

l 1 ]-t g,=a, ■dj 1 1+1- 1 o3=<a7 ■t,)-a: +d', aa'
.

1 1+1+ ] l+1- 1 1+1-
It can be determined by the formula. Also, the output of the basic cell 510!
is 1+1 j+1 j j a, =6, +(.

l+ 1 1+1 ai+1=s! ■of 1- 1 1+1 It can be determined by the formula.

Figure 5 shows the basic cell 5 in Figure 1 after the above binary encoding.
An example of a circuit diagram realizing 10 with a 0M05 circuit is shown. Gates 611, 62 sHE, -OR.

Gate 612 is inverter, gate 613 is 2-person NO
R.

Gate 631 is a two-man NAND gate, and gate 632 is an E-knee NOR gate. Further, the p-channel transistor 621 and the n-channel φ transistor 622, and the p-channel transistor 623 and the n-channel transistor 624 each constitute a transfer gate.

j Also, a, 601 and a, 602 are the first
1+1+t+1 - 2-bit input 521 in the diagram, the first decimal point of the divisor
Logical negation y of digit y, 603 is input 52 in FIG.
It is 2. q, 604 and tj 606 constitute a 2-bit control signal in FIG. Also, d! 614
is the addend number 626 in FIG. 1, and signals 615 and 602 provide information corresponding to the addend number 524. Furthermore, the signal 626 representing the intermediate phase or the signals c, 627, c', and 628 representing the presence or absence of intermediate carry are
The 1-bit signal 526 or a'' 634 in FIG. 1, respectively, is a 2-bit signal 529 representing the first digit of the 5-decimal point of the partial remainder in FIG.

Further, the divisor conversion circuit 512 in FIG. 1 is a NOR gate 613, and the positive/negative inversion circuit 511 is an E-OR gate 61.
1 and transfer 1-fist game) 621.622, the core of the intermediate phase determination circuit 513 is Ex-Ole25,
The intermediate carry determination circuit 514 is connected to the final phase determination circuit 51 by an inverter 612, transfer gates 821, 822, and transfer gates 623, 624.
5 is a NAND gate 631 and an Ex-NOR gate 6
32, respectively.

Note that although a transfer gate is used in this example, it is also possible to implement it using a normal gate.

FIG. 6 is an example in which the partial circuit 700 using the transfer gate in FIG. 5 is configured by a NOR gate. Gates 701, 702, and 703 are both two-person gates, and in this case, gates 701 and 612
constitutes a part of the positive/negative inversion circuit 511 in FIG. 1, and gates 702 and 703 constitute an intermediate carry determination circuit 527.

However, since the configuration shown in FIG. 8 increases the number of circuit stages and elements, a configuration using composite gates is also possible.

Next, implementation of the quotient determination cell 550 in FIG. 4 in the 0M03 circuit will be described.

FIG. 7 shows a cell 550 for determining the quotient by the above-mentioned binary encoding.
It is a CMO3 circuit diagram showing an example of implementation.

In the figure, gate 811 is an inverter, gates 813 and 823 are two-man powered NOR gates, gates 814, 815 and 822 are three-man powered NOR gates, gates 812 and 821 are four-man powered NOR gate, and gate 831 is an Ex-NOR gate.

Furthermore, a801 and a'802 are the 2-bit inputs 560 in Figure 4010, and a'803 and a'8
04 is 2 bit human power 561 1, a 805 and a
806 is a 2-bit input 2+2-562. Input q-807 is the input signal 563 from the upper quotient determination cell J-1+ in FIG. Also, the outputs qj+832 and -833 are 2-bit signals 565 representing the first decimal place of the quotient, and the outputs q, 833
and t, 834 are 2-bit signals that control each basic cell 510 in the j stage.

Further, the quotient determination circuit 561 in FIG.
11. NOR gates 813, 814. and 816, and the positive/negative inverting circuit 552 is composed of a NOR gate 82
3 and E knee NOR gate 831. Further, the control signal determination circuit 653 includes an inverter 811,
It is composed of NOR gates 812, 813, 814, 821, and 815. Note that the inverter 811
, NOR gates 813, 814, and 815 are commonly used by the quotient determining circuit 561 and the control signal determining circuit 553.

An example of implementation of the arithmetic processing device in this embodiment using a CMOS circuit has been described above. In the above example, in the binary encoding, the partial remainder 7 and the quotient q are given the same code side, but they may be subjected to different binary encoding.

In this embodiment, only the addition of a redundant binary number and a normal binary number has been explained, but it is possible to create an embodiment for subtraction in the same manner.

The basic cell in FIG. 5 is a 6-transistor E-
When OR and E-NOR are used, the number of transistors is 32, and the number of critical bus gates is three.

In addition, in the quotient determination cell shown in FIG. 8, the number of transistors is 5.
There are 0 transistors, and the number of critical path gates is 2.

Further, in this embodiment, the divider is particularly implemented using binary logic of the 0M05 circuit, but the present invention is also applicable to other technologies (for example,
This can be easily realized using NMO3, ECL, TTL, etc.) or multi-value logic. Furthermore, the present invention can be implemented in the same manner for multipliers.

According to this embodiment, the divider is formed by a 0M05 circuit, so that the delay required for calculation per one digit of the quotient is about 5 gates, and the basic cell is composed of elements about 3Q transistors and about 50) transistors. Since it can be realized as a combinational circuit with a regular array structure of quotient determination cells, it is
The number of transistors is about half, and the calculation time (number of gate stages) is about 1/24 when dividing by 32 bits, which is about 1.64 bits. Compared to a subtraction-shift type divider, the number of transistors is approximately half that of the Q divider. Therefore, it is effective in reducing the number of circuit elements in the divider, making it easier to integrate into an LSI, and increasing the speed.

Effects of the Invention According to the present invention, additions and subtractions that occur in internal operations such as division and multiplication can be performed using either a redundant addition circuit using an extended SD representation number that allows negative values in each digit, or a redundant subtraction circuit. This can be realized as a combinational circuit, and the carry or borrow of each digit in addition and subtraction can be made to propagate only one digit at most. (1) The number of elements in the arithmetic processing unit can be halved, and Since high-speed processing can be performed in a fixed time regardless of the number of digits, the speed of the arithmetic processing device can be increased, and (3) the arithmetic processing device can be easily and economically implemented as an LSI.

There are other effects.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the structure of a basic cell in the redundant addition cell in FIG. 3, FIG. 2 is a block diagram showing the configuration of an arithmetic processing device according to an embodiment of the present invention, and FIG. FIG. 4 is a block diagram showing an example of the configuration of a partial remainder determining circuit, and FIG. 4 is a block diagram showing the structure of the quotient determining cell in FIG.
Figure 5 is a CMO3 circuit diagram of the basic cell in Figure 1, Figure 6 is a diagram for explaining the transfer gate in Figure 5, and Figure 7 is a CMO3 circuit diagram of the quotient determination cell in Figure 4. A certain 0 100... Initial partial remainder determination circuit, 101°1
02.103,104,105...Partial remainder determination circuit, 201.202,203,204,205...
... Quotient determination cell, 10... Conversion circuit to r-base, 20... Dividend, 4o... Divisor, 60... Quotient, 310,311°312.31
3... Redundant addition cell, 510... Basic cell, 612... Divisor conversion circuit, 511...
. . . Positive/negative inversion circuit, 514 . . . Intermediate carry determination circuit, 513 . . . Intermediate phase determination circuit, 516.
...Final sum determining circuit, 551... Quotient determining circuit, 552... Positive/negative inverting circuit, 663...
...Control signal determination circuit. Name of agent: Patent attorney Toshio Nakao and 1 other person
1 Figure 2 Figure n ゝ゛' Figure 4 Figure 5 Figure 6

Claims (4)

[Claims] (1) For each digit of addition (subtraction), the first means and intermediate phase (intermediate The calculation of the first step has a second means for calculating the difference), and the intermediate phase (intermediate difference) obtained by the second means of the first step for each digit and the above-mentioned value provided in the lower digit. An internal operation consisting of two steps, a second step operation having a third means for obtaining the result of addition (subtraction) of each digit from the intermediate carry (borrow) obtained by the first means. a fourth processor for inverting the sign of the operation number according to the value of the control signal in the accompanying arithmetic processing unit;
By adding this fourth means to the first means and the second means, internal calculations by the first means, the second means, and the third means can be performed. What is claimed is: 1. An arithmetic processing device characterized in that it executes only one of addition and subtraction, and executes addition and subtraction. (2) The number of internal operations is reduced to 0 using the fourth means and the value of the control signal.
and a fifth means for replacing and outputting the second means, and by adding the fourth means and the fifth means to the first means and the second means, the first means and the fifth means are added. Said second
The internal calculations by the means and the third means can be performed only by addition or subtraction, and the calculation delay time (
The arithmetic processing device according to claim 1, characterized in that the number of stages of elements is reduced. (3) a sixth means in which the fourth means is added to the first means; and a seventh means in which the fourth means is added to the second means; The operation according to claim 1, wherein each of the means and the third means is constituted by a cell corresponding to an operation of one digit of the internal operation number, and has an array structure of the cells. Processing equipment. (4) An eighth means in which the fourth means and the fifth means are added to the first means, and a ninth means in which the fourth means and the fifth means are added to the second means. and the eighth means, the ninth means, and the third means are constituted by cells corresponding to an operation for one digit of the internal operation number,
3. The arithmetic processing device according to claim 2, having an array structure of the cells.