JPH0619704B2 - Divider - Google Patents

Description

TECHNICAL FIELD The present invention relates to a high speed division device.

[Conventional technology]

Conventionally, as a divider for performing division processing, a divisor is subtracted from a dividend or a partial dividend, and if the subtraction result is positive, the quotient of that digit is set to "1", the partial remainder is moved to a partial dividend, and Also, when the subtraction result is negative, the most basic recovery type divider is known in which the quotient of the digit is set to "0", the divisor is added again, and the operation of returning the original is repeated to obtain the quotient. In this divider, in n-bit division, n times of subtraction and addition of the number of bits whose quotient is "0" are performed.

In addition, as a speed-up of the recovery type divider, the sign of the partial remainder is checked, and if it is positive, the quotient is set to "1". For the calculation of the next digit, the divisor is subtracted. 0 ",
There is known a non-recovery type divider that omits addition for recovery by adding a divisor for the operation of the next digit.

On the other hand, unlike the above-mentioned divider that repeats addition and subtraction and shift, by considering division as a fraction, selecting a sequence in which the divisor of the denominator approaches "1", and repeating multiplication in the numerator dividend as well. There is also known a multiplication / convergence type divider that performs division by bringing the numerator closer to the quotient.

[Problems to be solved by the invention]

Among the conventional dividers described above, in the case of recovery-type dividers that repeat addition and subtraction and shift and non-recovery-type dividers, when the last digit of the multiplicand is not divisible, at least the same number of additions and subtractions as the bit length of the multiplicand Since it is necessary, the circuit configuration is simpler than other dividers, but it has the drawback of requiring a long processing time. On the other hand, a multiplication-convergence divider that finds a quotient by repeating multiplication can find the quotient by several multiplications if a dedicated multiplier is used. Will be shorter. However, in the case of this divider, the quotient is obtained by approximation, so
Since the processing time is determined regardless of the values of the dividend and divisor,
A recovery type divider or a non-recovery type divider has a short processing time compared to other divisions, and a division that can be easily divided has a drawback that it takes the same processing time as other divisions.

[Means for solving problems]

The division device of the present invention subtracts a divisor from a dividend or a positive partial dividend, adds a divisor to a negative partial dividend, and shifts the digits of the partial remainder obtained by the addition / subtraction to perform a partial dividend. And the quotient of the digit is determined by the sign of the addition / subtraction result, and a non-restoring divider that can omit addition of restoration; consider division as a fraction, and divide a sequence of numbers whose denominator approaches "1". A multiplication-convergence-type divider that performs division to find a quotient by repeating multiplication with respect to a divisor and a dividend; monitoring the presence or absence of a partial remainder of the non-restoration type divider, and performing the non-restoration type division during division When the partial remainder of the multiplier is exhausted, the division processing of the multiplication-convergence type divider is stopped, the quotient of the non-restoration type divider is used as the quotient of division, and the multiplication-convergence type divider ends the division as it is. If you do The division process of recovery-type divider is stopped,
Means for making the quotient of the multiplication / convergence type divider the division quotient.

〔Example〕

 Next, the present invention will be described with reference to the drawings.

In FIG. 1, a reference numeral 1 surrounded by a one-dot chain line is a non-recovery type divider, and 2 is a multiplication / convergence type divider.

Reference numeral 10 inside the non-restoring type divider 1 is a dividend register for holding a dividend M or a partial dividend, and 11 is a divisor N.
, 12 is an adder / subtractor that performs addition and subtraction between the output 100 of the dividend register 10 and the output 101 of the divisor register 11, and 13 is the output 102 of the adder / subtractor 12.
Is a remainder register holding 14; 14 is a digit shift circuit for shifting the digit of the output 102 of the adder / subtractor 12 ';
Reference numeral 05 is an output signal of the code register 15, and 16 is an adder / subtractor 1.
A quotient register for making and holding a quotient from the sign signal 108 of the operation result of 2, 17 is an all-zero detection circuit for detecting whether or not the output 103 of the remainder register 13 is all zero, 1
Reference numeral 07 is an output signal of the all-zero detection circuit 17.

On the other hand, reference numeral 20 in the multiplication / convergence type divider 2 is a dividend register for holding an approximate value of the dividend M or the quotient, 21
Is a divisor register holding the divisor N or an approximate value of “1”, 22 is a multiplier register holding the dividend M as a quotient, and a multiplier for approximating the divisor to “1”, and 23 is an output 200 of the dividend register 20 And the output 20 of the divisor register 21
1 is a multiplier for multiplying the output 202 of the multiplier register 22 by one, and 24 is the output 201 of the divisor register 21.
Alternatively, the output 201 of the divisor register and the multiplier register 22
2 is an output of the multiplier 202 and an output signal 203 of the multiplication result, and a multiplier generating circuit for generating a multiplier, and 204 are outputs of the multiplier generating circuit 24.

Further, reference numeral 30 is a division control circuit for performing various control of division, S is a division start instruction from a host device, E is a division end report to the host device, 40 is an output circuit of a quotient, and Q is an output circuit 4.
It is a quotient output from 0.

When the division start instruction S is sent from the host device together with the dividend M and the divisor N, the division control circuit 30 which has received the instruction, the dividend register 10 and the divisor register 11 in the non-recovery type divider 1, the multiplication convergence type Dividend register 2 inside divider 2
After controlling the 0 and the divisor register 21 to hold the dividend M and the divisor N, respectively, the operation of each divider is started.

Inside the non-restoring divider 1, first the dividend register 10
In order to know the magnitudes of the dividend M held in 1 and the divisor N held in the divisor register 11, subtraction is performed by the adder / subtractor 12, and the sign signal 108 confirms whether the subtraction result is positive or negative. When the result of the subtraction is positive, the dividend M is larger than the divisor N. Therefore, the top of the quotient register 16 is set to "1". When the subtraction result is negative, the divisor N cannot be subtracted larger than the dividend M. The top of is set to "0". At the same time, the partial remainder on the output 102 of the adder / subtractor 12 is shifted to the left by one digit in the digit shift circuit 14 and then stored in the dividend register 10 as a new partial dividend. The code signal 108 of the adder / subtractor 12 is also stored in the code register 15. The quotient register 16 is cleared to zero at the start of division processing.

Then, move on to the calculation of the quotient of the next digit. The sign register 15 holds the sign of the partial remainder of the previous digit. When this sign is positive, the partial remainder is valid until the previous time, so subtraction is performed.
When it is negative, addition is performed using the adder / subtractor 12 between the partial dividend held in the dividend register 10 and the divisor M held in the divisor register 11. Then, the quotient of the corresponding digit to be stored in the quotient register 16 is calculated from the code of the new partial remainder.

Then, in order to calculate the quotient of the next digit, the partial dividend and the sign thereof created by shifting the new partial remainder by a digit are stored in the dividend register 10 and the sign register 15, respectively.

This operation is repeated until an end instruction is received from the division control circuit 30. The output 103 of the remainder register 13 is constantly checked by the all-zero detection circuit 17, and when all zeros are stored in the remainder register 13, that is, when the dividend M is divisible by the divisor N, the all-zero detection circuit 1 is detected.
The division control circuit 30 receiving the all-zero detection signal 107 from 7 causes the output 106 of the quotient register 16 to be output as the quotient Q from the output circuit 40 using the control signal 300, and transmits the division end report E to the higher-level device. Then, the operations of the non-restoration type divider 1 and the multiplication convergence type divider 2 are stopped.

On the other hand, inside the multiplication / convergence type divider 2, first, a multiplier for approximating the divisor N to “1” from the divisor N held in the divisor register 21 is created by the multiplier creating circuit 24 and then stored in the multiplier register 22. To do.

Then, the dividend M held in the dividend register 20
After being multiplied by the approximation multiplier held in the multiplier register 22 by the multiplier 23, the dividend approximated to the quotient is stored in the dividend register 20.

Next, a first approximation divisor obtained by multiplying the divisor N held in the divisor register 21 and the first approximation multiplier held in the multiplier register 22 by the multiplier 23 is sent to the multiplier generation circuit 24. The second approximation multiplier is created and stored in the multiplier register 22. At this time, the output 203 of the multiplier 23
The first approximate divisor above is stored in the divisor register 21.

This operation is repeated until an end instruction is received from the division control circuit. The division control circuit 30 outputs the output 20 of the divisor register 21.
1 is monitored, and when the output 201 becomes "1", the division process is stopped, and the approximate value of the quotient held in the dividend register 20 at this time is used as the quotient Q to use the control signal 300 from the output circuit 40. And the division end report E is transmitted to the host device. Then, the operations of the non-restoration type divider 1 and the multiplication convergence type divider 2 are stopped.

In general, a non-restoring divider has n bits for n-bit division.
Although addition and subtraction are performed twice, when the division is completed in the middle of the division, the partial quotient at that stage becomes the formal quotient.

Also, in the case of a multiplication-convergence type divider, when the divisor becomes “1”, the quotient is the quotient of the dividend,
The processing time is faster than that of the non-restoring divider, but the value of the dividend does not affect the processing time. In addition, since the processing time required to approximate the divisor is almost the same, the processing time does not depend on the data when using the multiplication / convergence type divider. For this reason, a division that is easily divisible has a shorter processing time in a non-recovery type divider, so the quotient is calculated by a multiplication-convergence type divider in the case of normal division, but a non-recoverable type in the case of division that is easily divisible By using a divider,
The quotient can be calculated quickly.

〔The invention's effect〕

As described above, according to the present invention, the non-restoration type divider and the multiplication-convergence type divider are simultaneously operated, the multiplication-convergence type divider is in charge of normal division, and the non-restoration type divider performs division that can be divided in a short time. By being in charge, it is possible to take advantage of the features of each divider, to adopt the optimum divider that suits each division data, and to shorten the division processing time.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of a divider according to an embodiment of the present invention. 1 ... Non-recovery type divider, 2 ... Multiply-convergence type divider, 1
0, 20 ... dividend register, 11, 21 ... divisor register, 12 ... adder / subtractor, 13 ... remainder register, 14
...... Digit shift circuit, 15 …… Sign register, 16 …… quotient register, 17 …… All zero detection circuit, 22 …… Multiplier register, 23 …… Multiplier, 24 …… Multiplier creation circuit, 30 ・ ・ ・
… Division control circuit, 40 …… Output circuit.

Claims (1)

[Claims] 1. A dividing device for obtaining a quotient from a dividend and a divisor, which is obtained by subtracting a divisor from a dividend or a positive partial dividend, adding a divisor to a negative partial dividend, and obtaining the addition and subtraction. A non-restoring divider that can omit the addition of recovery is performed by repeatedly shifting the partial remainder and setting it as the partial dividend, and the quotient of that digit is determined by the sign of the addition / subtraction result; A multiplicative convergence type divider that performs division to obtain a quotient by selecting a sequence whose divisor approaches "1" and repeating multiplication with respect to the divisor and dividend; monitoring the presence or absence of partial remainder of the non-restoring type divider However, when the partial remainder of the non-restoration type divider is exhausted during the division, the division processing of the multiplication-convergence type divider is stopped and the quotient of the non-restoration type divider is used as the quotient of division. Multiplication convergence type Vessels is when it ends the division, the stops division processing of a non-restoring divider, divider unit and means for the quotient of dividing the quotient of the multiplication convergent divider.