JPH0667853A - Divider - Google Patents

Abstract

(57) [Abstract] [Purpose] There is no carry propagation in the partial remainder calculation {-1,
In a divider using a redundant binary adder of 0, + 1}, the range of the normalized divisor X is 12/8 ≦ X <1.
Provide an efficient divider that performs scaling conversion to 3/8 and determines the quotient with the upper 4 digits of the partial remainder value. [Configuration] The divider has a range of divisor X of 12/8 ≦ X <1.
A redundant binary adder for scaling conversion to 3/8 and an adder with carry look ahead are provided, a redundant binary adder is provided for partial remainder calculation, and addition is performed by determining the quotient with the upper four digits of the partial remainder value. A circuit for controlling is provided, and a circuit for converting the binary quotient into binary to binary is provided. [Effect] Conventionally, in determining a quotient per digit, 10 logical steps were required, but it can be realized with 5.5 steps, and redundant binary → binary conversion is efficient. The effect is that performance improvement of about 50% can be provided.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an arithmetic operation control system for a computer system, and more particularly to a divider suitable for realizing high speed division.

[0002]

2. Description of the Related Art Generally, in division, a quotient is determined in units of one digit, a partial remainder is calculated based on the quotient determination, and in the next operation step, the partial remainder value is shifted by one digit.
Based on that, the quotient of the next digit is determined, and so on, and the iterative operation is executed. This method of determining the quotient in units of one digit is called a radix-2 division method. As a method for achieving this at high speed, redundancy is added to the partial remainder calculation.
A method has been devised in which a redundant binary adder that uses the expression of {+1, 0, -1} called a decimal number is provided to perform addition without carry propagation (Takashi Taniguchi, Toichi Edamatsu, Yasushi Nishiyama, Kunio). Nobushigero, Takagi Naofumi: High-speed multiplier / divider using redundant binary representation, IEICE Technical Report ICD88-39,
1-6, 1988).

[0003]

SUMMARY OF THE INVENTION In this conventional method, 1
Since it is necessary to determine the quotient for each digit, in order to determine the quotient one digit and calculate the partial remainder, the number of logic stages (2
The input AND, OR, or EOR equivalent is counted as one stage), 4 stages and 6 stages are required for a total of 10 stages, and there is a problem that the number of logic stages of the multiplier is large.
Therefore, the object of the present invention is to determine the quotient in two-digit units, reduce the partial remainder calculation for one digit per two digits (6 logical steps), and determine the quotient per digit. It is to provide a high-speed radix-4 divider by reducing the total number of logical stages required for partial remainder calculation to less than 10.

[0004]

As a result of obtaining a condition for determining a quotient in units of two digits in a redundant binary number expression, the range of the divisor X is 12/8 ≦ X <13/8 (notation Is written as [12/8, 13/8) = 1.100 ...), and it has been clarified that it is a 4-digit reference. Therefore, the divisor X is converted by multiplying it by a certain number M so that it falls within this range. That is, the normalized divisor X = 1.・
From ..., refer to the result from the first digit to the fourth digit after the decimal point, and use the redundant binary adder and the carry-lookahead adder to convert to the form MX = 1.100 ... . At this time, if the same conversion M is applied to the dividend Y at the same time, the value of the quotient does not change, so that the quotient is correctly obtained.

[0005]

According to the present invention, the range of the divisor is [12/8, 1
(3/8) extra conversion is required, but in normal division, in order to prevent division by zero, the zero operand is detected and the divisor and dividend are aligned. Since the processing is required, the range conversion of the divisor can be executed in parallel with this preprocessing, and a high-speed divider can be realized because there is not much overhead.

[0006]

FIG. 1 shows an embodiment of the basic configuration of a radix-4 divider according to the present invention. Generally, in the floating-point arithmetic, the exponent part, the sign part, and the mantissa part are divided, but in this embodiment, the process is the heaviest and only the essential mantissa part process will be described. The other parts are not essential as the processing is not so heavy. In addition, digit alignment processing is required for application to fixed-point arithmetic or integer arithmetic, but this is not essential because it may be considered separately.

In the embodiment shown in FIG. 1, the dividend is Y and the divisor is X.
And The storage registers for the dividend Y and the divisor X are set to 10 and 20, respectively. These are subjected to a scaling operation, which will be described later, by the circuit 3, and Y ′,
It is converted into X ′ and stored in the storage registers 11 and 12. Based on the values of Y'and X ', the quotient decision circuit calculates 2
The quotient is determined for each digit (circuit 30), and the partial remainder calculation is performed without carry propagation using the redundant binary adder (circuit 40). Then, the partial remainder calculation result is shifted by two digits, and the quotient of each digit is determined in the same manner. These arithmetic circuits 30, 31, ... 40, 41 ,.
Are arranged in an array as shown in FIG. Finally,
The determined quotient of each digit q (-1), q (0), ..., q
Since (n / 2-1) is represented by a redundant binary number, it is converted into a normal binary number by the redundant binary → binary converter 50 to obtain a final quotient.

The operation of the circuit of FIG. 1 will be described below in more detail.

First, the dividend Y and the divisor X are both normalized, and ... is assumed to be in the shape of.
As shown in Table 1, the range of the divisor X is [12 /
(8,13 / 8) = 1.100 ... Scaling conversion M is performed to convert into Y′11 and X′21, respectively.

[0010]

[Table 1]

That is, as shown in Table 1, conversion is performed by referring to the values from the first digit to the fourth digit after the decimal point of the divisor X, and the value is converted into MX = 1.0. In order to specifically execute the scaling conversion M shown in Table 1, the scaling conversion circuit 3 shown in FIG. 2 is provided. The scaling conversion circuit 3 shifts and selects the values of the operands 10 and 20 in accordance with the values of the first to fourth digits after the decimal point of the divisor, and inverts the values of different signs of the +1 expression and the -1 expression by +1. Converting circuits 12, 13, 22,
23, circuits 14 and 24 for canceling values of different signs, redundant binary adders 15 and 25, and carry-look-ahead adder 1
It is composed of 6, 26. The shift / select circuit 2 is realized as shown in FIG. However, the control follows the control logic map shown in Table 2.

[0012]

[Table 2]

In the function value f (x) of Table 2, the sign represents addition (+) / subtraction (-), and the absolute value represents the power of scaling. For example, if the current digit of the divisor X is j, then f (1
011) = − 3, +5, -3 on the left side is input to the inverters 12 and 22 in which the (j−3) th digit value is + sign, and + on the right side
In the case of 5, the value of the (j-5) th digit is input to the minus-sign inverters 13 and 23, respectively, and since they have different signs, an inverted signal is output. The outputs of the shift / select circuit 2 are gates 12, 22, 13, 23 that invert the values of the different sign representation.
Are input to the gates 14 and 24 for canceling the values of different signs, and the outputs thereof are input to the redundant binary adders 15 and 25. With such a circuit configuration, the scaling conversion M
Is realized. If the circuit 3 is realized in parallel with the process 1 of detecting the zero operand and the process of adjusting the digit of the dividend Y and the divisor X (the process corresponding to the carry look-ahead adder is required) 1, the overhead does not occur much. By the way, X '= MX, Y' = M
If Y and the quotient are Q, Q = Y / X = (MY) / (MX) = Y ′ / X ′ (Equation 1), so that the quotient can be correctly obtained by the scaling operation M. I understand.

The radix-4 division is repeatedly executed by the recurrence formula R (i + 1) = 4 (R (i) -q (i) X ') (Equation 2). Here, i represents the number of repeated steps of the operation, and indicates that it is related to the operation of determining the quotient at the 2i−1 and 2ith digits after the decimal point. R
(I) is the partial remainder value before the partial remainder calculation at the i-th step, and based on this value, 2i−1 below the decimal point,
The quotient at the 2i-th digit is determined. In particular, R (0) = Y '. Then, the partial remainder is obtained using the redundant binary adder without carry propagation. The partial remainder result is multiplied by four (shifted by two digits) to become the partial remainder value R (i + 1) used in the next calculation step i + 1.

Next, the upper 4 digits (r) of the partial remainder value R (i)
(-1), r (0), r (1), r (2): r (j) represents the partial remainder value at the jth digit after the decimal point) to quotients q (2i-1), q (2i) Table 3 shows the allocation of signal outputs for controlling the addition of the redundant binary adder 80 shown in FIG.

[0016]

[Table 3]

This is a scaling conversion of the divisor X to X '.
Is obtained by fitting the value in the range [12/8, 13/8). The output of the addition control signal is qc
And q (v2) and q (v1), and so to speak, qc is a code signal of the absolute value signals q (v2) and q (v1). The actual quotient value is q (2i−1) = − q (v
2), q (2i) =-q (v1), and when qc is 1, q
(2i-1) = + q (v2), q (2i) = + q (v
1). Thus, the two-digit quotient q (2i-1), q (2i) represented by the redundant binary number can be represented by three binary signals. According to Table 3, even if the value of the quotient q is zero, the output value of the addition control signal qc may be 1,
It is shown that 1 may be input to the redundant binary adder 80. The reason is that when adding a zero value, there are two methods in the two's complement representation, and the present invention uses them properly. That is, the most significant digit is a digit of 2 squared and serves as a sign bit for the 2's complement representation. And if there is a decimal point between the 3rd and 4th most significant digit, the zero value is
Can express streets.

(1) 0 = 000.0 ... 00 or (2) 0 = 111.1 ... 11 + 000.0 ...
01 (that is, inversion of zero + 1 is also zero) This kind of usage simplifies the control logic,
As shown in FIG. 4, the quotient determination circuit 60 is composed of five logical stages. In the past, four rounds were required to determine a one-digit quotient, so when converted to two digits, 4 × 2 = 8 rounds, which is 62.5% of the conventional rate. The upper 4 digits of the partial remainder value R (i) are input to the quotient determination circuit 60 of FIG.
(-1)-, r (-1) + are the second highest digit (first power of 2)
The values of the −1 expression component and the +1 expression component of are input. Similarly, the symbols r (j)-and r1 (j) + indicate that the values of the −1 expression component and the +1 expression component at the jth digit after the decimal point are input to the redundant binary adder 80. The partial remainder calculation result of the redundant binary adder 80 at the jth digit after the decimal point is represented by the symbols r '(j)-, r' (j) +. Redundant binary adder 8
Carry 0 to the digit after the decimal point (j + 1) c-in (j + 1)
Is input, but carry propagation to the upper digits than the j-th digit has not occurred. Similarly, the carry c-out (j) at the jth digit after the decimal point is output. The symbols x ′ (j + 1) and x ′ (j) indicate that the values of the j + 1th and jth digits below the decimal point of the scaled divisor X ′ are input, respectively. From FIG. 4, the total number of logical stages is 11 for the one-step calculation of quotient determination and partial remainder calculation.
It takes 5.5 rounds for each digit of quotient decision because it requires rounds.

Finally, the determined quotient q (-1) q
(0). Since q (1) ... q (n-1) is a redundant binary number expression, it is converted into a normal binary number by the redundant binary-to-binary converter 50 to obtain the final quotient Q. 4-digit redundant binary number, (q (2j-1)-, q (2j-1) +), (q (2j)-, q (2j) +), (q
(2j + 1)-, q (2j + 1) +), (7q (2j + 2)-, q (2j + 2) +) are normal binary numbers q (2j-1), q (2j), An example of conversion into q (2j + 1), q (2j + 2) is shown in FIG. The rightmost symbols + and-are the -1 expression components,
It is shown that it is related to the value of the +1 expression component. The principle of this converter is to simplify the logic by utilizing the property that the value of the -1 expression component and the value of the +1 expression component appear only once in each two-digit unit and are mutually exclusive. ing. Then, if the value of the +1 expression component from a certain digit to the higher digit is zero, the logic is constructed by utilizing the property that the value of the −1 expression component from the lower digit propagates. That is, when a digit has a value of the -1 expression component of 1,
This is output as a borrow generation signal g. Also, a certain digit +
When the value of one expression component is zero, it is output as a borrow propagation signal p. In the case of radix-4 division, as described above, the quotient is sequentially determined in units of two digits from the upper digit to the lower digit. Here, as shown in FIG. 6, if the logic circuit of the circuit 50 is configured by the basic logic circuit 90 using the pass transistor, the A input (the higher order in the circuit 50, which functions as a gate switching circuit) Assuming that the input B (corresponding to the side input) operates first, even if the operation of the input B (corresponding to the lower side input in the circuit 50) is determined thereafter, the input signal of B is instantaneously gated. Therefore, the circuit 50 operates at a high speed because it only passes through the. Therefore, carry propagation does not occur unlike in the normal case only when the quotient is converted from redundant binary to binary.

[0020]

According to the present invention, in the past, in determining the quotient per digit, 10 logical stages were required, but it can be realized with 5.5 stages, and redundant binary → binary conversion is possible. The efficiency is improved and the performance can be improved by about 50%.

[0021]

[Brief description of drawings]

FIG. 1 is a block diagram of a radix-4 divider of the present invention.

FIG. 2 is an explanatory diagram of a method of executing scaling conversion in parallel with a zero detection circuit to eliminate overhead of scaling conversion.

FIG. 3 is a selector circuit that controls scaling conversion.

FIG. 4 is a circuit for calculating a quotient at an arbitrary step and calculating a partial remainder of a certain digit.

FIG. 5 is a redundant binary conversion circuit.

FIG. 6 is a basic circuit for forming a logic circuit using pass transistors.

[Explanation of symbols]

1 ... Zero division detection, 2 ... Scaling conversion selector circuit, 3 ... Scaling conversion circuit, 10 ... Dividend Y storage register, 20 ... Divisor X storage register, 11 ... Scaling conversion Dividend Y ′ storage register, 12, 1
3, 22, 23 ... Inversion + 1 circuit, 14, 24 ... Cancellation circuit, 15, 25 ... Redundant binary adder, 16, 26 ... Carry lookahead adder, 21 ... Scale-converted divisor X'storage register, 30, 31, 32, 33 ... Quotient determination circuit, 40, 41, 42 ... Partial remainder calculation circuit, 50 ...
..Redundant binary-to-binary conversion circuit, 60 ... Quotient decision circuit, 80 ...
..Arbitrary digit partial remainder calculation circuit, 90 ... Basic logic circuit configured by using pass transistors, ∨ ・ ・ ・ OR, ∧ ・
..Logical product, logical negation

Claims (5)

[Claims] 1. A division processing device of a computer system,
Redundant binary number {+ 1,0,-for partial remainder calculation
1} is provided with a redundant binary adder, and the divisor X is scaled and converted to a range of 12/8 ≦ X <13/8,
A radix-4 divider that simplifies quotient determination by referencing only the upper four digits of the partial remainder value. 2. A radix-4 divider according to claim 1, wherein the scaling transform is executed in parallel with a preprocessing part such as zero division detection. 3. When a zero value is added to the partial remainder, (1) all 0 pattern and (2) all 1 pattern + 1, that is, inversion of all 0 pattern + 1 are used properly by the two's complement representation of the addend. The radix-4 divider of claim 1, wherein the quotient decision logic is simplified. 4. A redundant binary number representation of a radix-4 two-digit quotient is:
Redundant binary using the property of being selected from {(-1,0), (0, -1), (0,0), (0, + 1), (+ 1,0)} The radix-4 divider according to claim 1, wherein a binary converter is provided to efficiently convert the quotient represented by the redundant binary number into a normal binary number. 5. The circuit of the redundant binary-to-binary converter according to claim 4, wherein a logic circuit is constructed by using a pass transistor, and is executed at high speed without propagation delay of gate operation. The radix-4 divider according to claim 1.