JP3028165B2 - High radix division control method and high radix divider - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a high radix division control method and a high radix divider, and more particularly to a method for dividing a quotient of a binary number by n bits from an upper digit based on a dividend and a divisor represented by a binary number. The present invention relates to a division control method and a divider for performing high-speed iterative high-radix division to be calculated.

[0002]

2. Description of the Related Art First, a high radix division algorithm will be described. Note that the high radix operation refers to an operation performed in units of a plurality of bits.

The dividend N, the divisor D, and the radix r are N <r ·
When the condition of D is satisfied, the first calculation is as follows. The first quotient digit q1 is And the first quotient Q1 and partial remainder P1 are as follows.

[0004]

(Equation 1)

[0005] The second and subsequent calculations are as follows. The j + 1-th quotient digit qj + 1 is And the j + 1-th quotient Qj + 1 and the partial remainder Pj + 1 are as follows.

[0006]

(Equation 2)

When the above calculation is repeated n times until the required accuracy is obtained, the final quotient Q and remainder R are obtained as follows.

[0008]

(Equation 3)

As an improvement of the speeding up of the present algorithm, a high radix SRT division algorithm is known. This algorithm can reduce the calculation time by utilizing the redundancy of the data, because the quotient digit calculation can be performed with coarse precision of each higher-order bit, regardless of the exact values of the partial remainder and the divisor. Hereinafter, a calculation method using the quaternary SRT division algorithm will be described.

When N is the dividend and D is the divisor, N <(8/3)
・ The condition of D shall be satisfied. The first calculation is as follows. The first quotient digit q1 can be obtained from the relational expression of q1 = 0 if 0.5 ≦ N <0.5D, q1 = 0 if 0.5D ≦ N <1.5D, q1 = 11.5D ≦ N, and q1 = 2. The first quotient Q1 and partial remainder P1 are as follows.

[0011]

(Equation 4)

The second and subsequent calculations are as follows. The quotient digit qj + 1 of the (j + 1) th time is 4j <-1.5D, qj + 1 = −2−1.5D ≦ 4Pj <−0.5D, qj + 1 = −1−0.5D ≦ 4Pj < If 0.5D, qj + 1 = 0 if 0.5D ≦ 4Pj <1.5D, if qj + 1 = + 1 1.5D ≦ 4Pj, it is obtained from the relational expression of qj + 1 = + 2, and the j + 1-th quotient Qj +1 and the partial remainder Pj + 1 are as follows.

[0013]

(Equation 5)

When the above calculation is repeated n times until the required accuracy is obtained, the final quotient Q and remainder R are obtained as follows.

[0015]

(Equation 6)

Since the high radix SRT division algorithm can obtain an accurate result at a relatively high speed, it is used in an LSI for floating-point arithmetic or a microprocessor having a floating-point arithmetic unit.

On page 57 of the IEEE MICRO June 1988 issue, the division scheme of the floating point arithmetic coprocessor R3010 of MIPS is discussed. In this method, a quaternary SRT method is employed, the upper 9 bits of the partial remainder in the carry storage format are carry-propagated and added, and then input to the quotient digit calculation circuit together with the upper 9 bits of the divisor to obtain the quotient 2
In this method, bits are obtained.

1989 IEEE DIGEST OF TECHNICAL P
The floating-point arithmetic coprocessor discussed on page 52 of APERS uses a similar arithmetic scheme.

[0019]

In the above prior art, one iteration of the calculation is performed by sequential processing of the calculation of the quotient digit and the calculation of the partial remainder. Of the quotient digit partial remainders, the partial remainder can be calculated at high speed by carry save addition, but the quotient digit performs a process of calculating by the quotient digit determination circuit together with the divisor after carrying the partial remainder by carry propagation addition, High speed was difficult. As a result, it has been difficult to speed up the division as a whole.

An object of the present invention is to provide a high radix division control method for shortening the processing time per iteration and speeding up division, and a high radix divider to which this control method is applied.

[0021]

SUMMARY OF THE INVENTION In order to achieve the above object, the present invention provides an iterative type of calculating a quotient of a binary number by n bits from an upper digit based on a dividend and a divisor represented by a binary number. In the high radix division control method, in parallel with the procedure of calculating the n-bit quotient digit and the procedure of calculating the quotient digit, a procedure of pre-calculating the partial remainder for all possible values of the quotient digit, In parallel with the calculation procedure, a procedure of pre-calculating the next quotient digit from the pre-calculated partial remainder and divisor, and, when the n-bit quotient digit is calculated, the quotient digit is calculated from the pre-calculated partial remainder. And selecting the value corresponding to the quotient digit from the preceding calculated values of the next quotient digit, storing the selected partial remainder and the quotient digit, and Suggest high radix division control method comprising the steps for migrating to the minute remainder preceding calculation and the next of the quotient digit calculation.

According to another aspect of the present invention, there is provided an iterative high radix divider for calculating a quotient of a binary number by n bits from an upper digit based on a dividend and a divisor represented by a binary number. Means for calculating an n-bit quotient digit, means for calculating the partial remainder for all possible quotient digit values that can be taken as the quotient digit in parallel with the quotient digit calculation, and means for calculating the quotient digit in parallel Means for pre-calculating the next quotient digit from the pre-calculated value of the partial remainder and the divisor, means for selecting the pre-calculated value of the partial remainder corresponding to the calculated quotient digit, and corresponding to the calculated quotient digit. Means for selecting the preceding calculated value of the next quotient digit, means for storing the selected partial remainder and the quotient digit, and converting the selected partial remainder and the quotient digit for the next n-bit operation. Suggest high radix divider and means convolving the calculation means.

In order to achieve the above object, the present invention further provides a divisor and a divisor based on a binary number.
Means for calculating an n-bit quotient digit in a repetitive high radix divider that calculates a quotient of a base number n bits at a time from an upper digit and inputting a partial remainder and a divisor in parallel with the calculation of the quotient digit A partial remainder precedence calculation circuit that pre-calculates the partial remainder for all possible values of the digit, and a quotient precedence that pre-calculates the next quotient digit from the pre-calculated partial remainder and the divisor in parallel with the calculation of the quotient digit When the calculation circuit, the n-bit quotient digit is calculated, a partial remainder selector for selecting a value corresponding to the calculated quotient digit from the previously calculated partial remainder, and when the n-bit quotient digit is calculated, A quotient leading calculation value selector for selecting a value corresponding to the calculated quotient digit from the leading calculation quotient digits; and an input data for selecting one of the selected partial remainder and dividend. And Taserekuta, proposes a high-radix divider having a quotient digit calculation circuit for calculating the next quotient digit according to the preceding calculated values of the selected quotient.

Further, the output of the partial remainder selector is connected to all of the partial remainder preceding calculation circuit, the input data selector selects one of the output and the dividend assumed partial remainder preceding calculation circuit 0 as the quotient digit , The output of the input data selector is connected to a quotient precedence calculation circuit assuming 0 as a quotient digit, and the partial remainder selector selects the output of the input selector from the output of the partial remainder precedence calculation circuit assuming a quotient other than 0. Select the correct value, before calculating the quotient digit, the input data selector selects the dividend, and before calculating the quotient digit, the partial remainder selector and the quotient leading value selector were calculated assuming 0 as the quotient digit, respectively. When the value is selected and the quotient digit is calculated, the input data selector selects the partial dividend, and during the quotient digit calculation, the partial remainder selector and the quotient A value selector selects a value calculated assuming the calculated quotient digit, and inputs from a calculation using another partial remainder precedence calculation circuit which requires more time for calculation than a partial remainder precedence calculation circuit assuming 0 as a quotient. It is also possible to eliminate the data select process, shorten the calculation time of the partial remainder, and realize high-speed calculation.

In the case of using a high radix SRT division algorithm capable of calculating a quotient digit by using a partial remainder and each higher-order bit of a divisor, the partial remainder preceding calculation circuit calculates only bits necessary for the quotient digit calculation. A low-order partial remainder calculation circuit that calculates the low-order partial remainder after calculating the quotient digit to supply the low-order data of the partial remainder preceding calculation value that disappears by n bits each time the calculation is performed. Perform quotient calculation at high speed while suppressing.

Further, the partial remainder look-ahead circuit comprises a carry-preserving adder, and the partial remainder selector comprises a sum selector and a carry signal selector output by the partial remainder preceding calculation circuit. Consists of a partial remainder selector output for sum and a selector for selecting a dividend, and a partial remainder selector output for a carry signal and a selector for selecting zero. And a circuit for executing the calculation, and the partial remainder preceding calculation can be executed at high speed.

The partial remainder leading calculation circuit comprises a carry-preserving adder, and the partial remainder selector comprises a selector for selecting the sum output from the partial remainder preceding calculation circuit and a selector for selecting the carry signal. The selector comprises a partial remainder selector output for sum and a selector for selecting a dividend, and a selector for a carry signal and a selector for selecting zero. This is a circuit that executes the calculation by using the divisor, and a method that executes the partial remainder preceding calculation at a high speed can also be adopted.

The partial remainder leading calculation circuit comprises a carry-preserving adder, and the input data selector includes a selector for selecting a sum and a selector for selecting a dividend output by the partial remainder preceding calculation circuit assuming 0 as a quotient digit. And a selector for selecting a carry and a zero output by the partial remainder preceding calculation circuit assuming 0 as the quotient digit, and the partial remainder selector is connected to the selector for the selection selector of the output of the input data selector and 0 as the quotient digit. And a selector for selecting the sum and a selector for selecting the carry signal output by the partial remainder preceding calculation circuit assuming that
The quotient precedence calculation circuit is a circuit that executes the calculation using the partial remainder and the divisor in the carry preservation format, and may use a method that performs the partial remainder precedence calculation at high speed.

The partial remainder preceding calculation circuit and the lower partial remainder calculating circuit are each composed of a carry-save type adder, and the partial remainder selector includes a selector for selecting a sum output from the partial remainder preceding calculation circuit and a selector for selecting a carry signal. A selector for selecting the output of the partial remainder selector for the sum and the dividend, and a selector for selecting and selecting the output of the partial remainder for the carry signal and zero. Is a circuit that executes calculation using a partial remainder and a divisor in the carry-preserving format, and it is also possible to adopt a method of executing partial remainder preceding calculation at high speed.

Further, the partial remainder precedence calculation circuit comprises a circuit for outputting a value obtained by half-adding the sum and the carry signal. The partial remainder precedence calculation circuit does not increase the calculation time of the partial remainder precedence calculation circuit. If the addition process of the remainder leading calculation value and the divisor is changed from full addition to half addition, the quotient leading calculation can be executed at high speed.

[0031]

In the present invention, the preceding calculation of the partial remainder and the preceding calculation of the next quotient digit are executed in parallel with the quotient digit calculation which takes the longest time in the high radix operation. It can be reduced to nearly half compared to the conventional one. In other words, the partial remainder calculation and the quotient digit calculation are divided into two, and the current quotient digit calculation and the pre-processing for the next quotient digit calculation are executed in parallel, reducing the quotient digit calculation time by about half. it can.

Therefore, if the present invention is applied to a floating-point arithmetic LSI or a microprocessor, iterative calculations can be performed a plurality of times in one cycle at the same clock frequency as in the prior art. Also, if the number of cycles is the same as in the conventional case, iterative calculation can be performed at almost twice the clock frequency. As a result, an arithmetic unit having greatly improved division performance can be obtained.

[0033]

Next, an embodiment of a division control method and a divider according to the present invention will be described with reference to FIGS.

FIG. 1 is a block diagram showing a configuration of an embodiment of a divider to which the present invention is applied to a quaternary SRT division algorithm. This divider has a dividend Ni0.N01N of 0 or more and less than 2.
································································································· D52
Outputs S and RM. Upper partial remainder preceding calculation circuit 10, 1
1, 12, 13, and 14 are the upper 11 of the partial remainder when the quotient digit is 0, +1, +2, -1, -2 before the quotient digit is calculated.
A carry save adder that calculates bits. The lower partial remainder calculation circuit 16 is a carry save adder that calculates the lower 43 bits of the partial remainder after the quotient digit is calculated. The input data selector 20 selects one of a value obtained by shifting the upper 8 bits of the dividend to the lower 2 bits and an output value of the upper partial remainder preceding calculation circuit 10. The input data selector 21 selects either the value obtained by shifting the lower 45 bits of the dividend to the lower 2 bits or the lower 41 bits of the partial remainder.

Before the quotient digit is obtained, the precedence comparison circuits 30, 31, 32, 33, and 34 determine whether the quotient digit is 0, +1, +2,-.
In the case of 1 and -2, a comparison calculation is performed between a value obtained by shifting the upper 8 bits of the partial remainder by 2 bits to the upper side and the upper 8 bits of a multiple of the divisor. The divisor / multiple generation circuit 40 includes a preceding comparison circuit 30,
Calculate 1.5 times the divisor required for 31, 32, 33, 34. After the quotient digit is calculated, the upper partial remainder selector 15 selects a correct value from the preceding calculated values of the upper partial remainder. After the quotient digit is calculated, the comparison value selector 35 selects a correct value from the preceding comparison values. The quotient digit calculation circuit 50 calculates a quotient digit using the selected preceding comparison value, and outputs a select signal corresponding to the quotient digit. The quotient register 60 stores the calculated quotient digit. The final remainder checker 70 detects the presence or absence of the partial remainder RM and the sign RS after all the bits of the quotient have been calculated.

Next, the operation of each circuit when calculating the quotient digit will be described. The input data selector 20 selects a value obtained by shifting the upper eight bits Ni0.N01N02,. This value is input to the upper partial remainder selector 15, and shifted by 2 bits to the upper part, and the leading comparison circuit 30
Is input to The leading comparison circuit 30 calculates the dividend Ni0.N01N02N0
Calculate the preceding comparison value of -1.5 multiple, -0.5 multiple, +0.5 multiple and +1.5 multiple of 3N04 and divisor 1.D01D02D03D04, respectively. The input data selector 21 outputs the lower 45 bits of the dividend N08N09 ...
A value obtained by shifting N52 by 2 bits to the lower side is selected and output to the lower partial remainder calculation circuit 16. Here, the quotient digit calculation circuit 50 controls to output a select signal corresponding to a quotient digit of zero. In accordance with this control, the higher-order partial remainder selector 15 selects the value of the input data selector 20, and the comparison value selector 35 selects the value of the preceding comparison circuit 30. Further, the lower partial remainder calculation circuit 16 is provided with an input data selector 21.
And the value of 0 are added. When the value of the upper partial remainder selector 15 and the value of the lower partial remainder calculation circuit 16 are combined, the dividend Ni
0.N01N02... N52 is shifted downward by 2 bits.

The comparison circuit 50 receives the preceding comparison values of the dividend and the divisor, and calculates the first quotient digit. The upper partial remainder precedence calculation circuits 10, 11, 12, 13, and 14 input the value obtained by shifting the 11 bits below the decimal point of the partial remainder by 2 bits to the upper side and the upper bits of the divisor, and the quotient digits are 0 and +, respectively.
Assuming the case of 1, +2, -1, -2, calculate the upper 11 bits of the partial remainder. The input data selector 20 selects a value of the upper partial remainder preceding calculation circuit 10. Input data selector 21
Selects a value in which the lower 41 bits of the partial remainder are shifted upward by 2 bits. The preceding comparison circuits 30, 31, 32, 33, 34
Upper partial remainder precedence calculation circuits 10, 11, 12, 13, 14 respectively
Calculates the value obtained by shifting the upper 8 bits by 2 bits to the higher order and the preceding comparison value of the divisor. The quotient digit calculation circuit 50 calculates a quotient digit and outputs a select signal corresponding to the quotient digit. In response to this select signal, the upper partial remainder selector 15 causes the upper partial remainder precedence calculation circuits 10, 11, 12, 1
Select the value corresponding to the quotient digit from 3 and 14. In response to the select signal, the comparison value selector 35 selects a value corresponding to the quotient digit from the values of the preceding comparison circuits 30, 31, 32, 33, and 34. The lower partial remainder calculation circuit 16 performs a subtraction between the value of the input data selector 21 and the value obtained by multiplying the divisor by the quotient digit, and calculates the lower 43 bits of the partial remainder. Since the quotient digit calculated by the comparison circuit 50 is signed, the quotient register 60 stores the positive quotient digit and the negative quotient digit separately.

When the above calculation is repeated 27 times, the quotient register
60 has a positive quotient Pi0.P01P02 ... P54 and a negative quotient Mi0.M01M02
... and M54 are obtained. Also, from the output of the upper partial remainder selector 15 and the calculation result of the lower partial remainder calculation circuit 16, the final remainder PSi1PSi0.PS01PS02 ... PS52, P
Ri1PRi0.PR01PR02 ... PR51 is required. The final remainder checker 70 detects the presence / absence RM of the final remainder and the sign RS.

Next, an embodiment of each circuit constituting the divider of FIG. 1 will be described in more detail. FIG. 2 is a logic diagram of the upper partial remainder preceding calculation circuit 10 and the input data selector 20. The upper partial remainder precedence calculation circuit 10 performs partial remainder PSi1PSi0.PS01PS02... PS11 and PRi1PRi in the carry storage format.
0.PR01PR02 ・ ・ ・ ・ PR11 is shifted by 2 bits to the high order, carry save addition is performed, and partial remainder PISi1 when the quotient digit is 0
PISi0.PIS01... PIS09 and PIRi1PIRi0.PIR01. Input data selector 20 is PISi1PISi0.PIS
01 ・ ・ ・ ・ 00.0Ni with the dividend shifted by 2 bits to the lower order of PIS09
... N07 ... N07 and select PIRi1PIRi0.PIR01
... Select either PIR08 or 0.

FIG. 3 is a logic diagram of the upper partial remainder preceding calculation circuit 11. Partial remainder Psi1PSi0.PS0 in carry storage format
1PS02 ... PS12 and PRi1PRi0.PR01PR02 ... PR11
Shift by 2 bits and carry-add the value obtained by inverting the divisor 1.D01D02 ... D10 with the inverter, and carry the partial remainder when the quotient digit is +1 P1Si1P1Si0.P1S01 ... P1S09 and P1Ri1P1Ri
0.P1R01 ... P1R08 is calculated.

FIG. 4 is a logic diagram of the upper partial remainder preceding calculation circuit 12. Partial remainder Psi1PSi0.PS0 in carry storage format
1PS02 ... PS12 and PRi1PRi0.PR01PR02 ... PR11
Shifts 2 bits, divisor 1.D01D02 ... D11 shifts 1 bit to the high order and carries save addition with the value inverted by inverter, and partial remainder P2Si1P2Si0.P when quotient digit is +2
.. P2S09 and P2Ri1P2Ri0.P2R01... P2R08 are calculated.

FIG. 5 is a logic diagram of the upper partial remainder preceding calculation circuit 13. Partial remainder Psi1PSi0.PS0 in carry storage format
1PS02 ... PS12 and PRi1PRi0.PR01PR02 ... PR11
Shift by 2 bits, carry divisor 1.D01D02 ... D10 and carry save addition, and partial remainder P3Si1P3Si when quotient digit is -1
.. P3S09 and P3Ri1P3Ri0.P3R01... P3R08 are calculated.

FIG. 6 is a logic diagram of the upper partial remainder preceding calculation circuit 14. Partial remainder Psi1PSi0.PS0 in carry storage format
1PS02 ... PS12 and PRi1PRi0.PR01PR02 ... PR11
The divisor 1.D01D02 ... ・ D10 is shifted by 1 bit to the upper bit and carry-save-added, and the quotient digit is shifted.
P4Si1P4Si0.P4S01 in case of -2 P4S09 and P4Ri1
P4Ri0.P4R01 ... P4R08 are calculated.

FIG. 7 is a logic diagram of the input data selector 21 and the lower partial remainder calculation circuit 16. Input data selector 21
Is either a value obtained by adding the outputs PS53 and PS54 of the input data selector 21 to the partial remainder PS12... PS52 and shifted upward by 2 bits, or a value obtained by shifting the dividend N08. ., And PR51, which is a value obtained by shifting the partial remainders PR12,.

The lower partial remainder calculation circuit 16 includes a quotient-divisor multiplication circuit 160 and a carry save adder 161. The quotient-divisor multiplication circuit 160 includes a five-input selector and an inverter. Input 0 to the input 0 of the selector, input 3 and 1
Input the divisor of the same bit and its inverted value, and input 4
For 1 and 2, the divisor of one bit lower and its inverted value are input.
5 Input selectors are select signals SEL0, SEL1, SEL2, SEL
3. Select one of the five input data according to SEL4. Carry save adder 161 is connected to input data selector 2
The value of 1 and the value of the multiplication circuit 160 are added, and the partial remainder PS10 is used.
Calculate PS52 and PR09 ... PR51. If SEL0 is 1,
The value of the input data selector 21 and 0 are added. SEL1 is 1
In the case of, the value of the input data selector 21 is added to the inverted value of the divisor. At this time, the least significant bit of the adder is
Adds 1 as the complement for subtraction. When SEL2 is 1, the value of the input data selector 21 is added to the value obtained by shifting the divisor by one bit to the higher order and inverting it. At this time, the least significant bit of the adder adds 1 as a complement for subtraction. If SEL3 is 1,
This is an addition of the value of the input data selector 21 and the divisor. SEL4
Is 1, the value of the input data selector 21 is added to the value obtained by shifting the divisor by one bit to the higher order.

FIG. 8 is a logic diagram of the preceding comparator 30. The leading comparator 30 is a comparator 300 with a -1.5 multiple of the divisor,
Comparator 301 with 0.5 multiple, Comparator 30 with +0.5 multiple of divisor
2. Consists of a comparator 303 with a +1.5 multiple of the divisor. Each comparator adds three inverted values of a multiple of the divisor to be compared with the partial remainder, and outputs intermediate data for determining the magnitude based on the sign of the most significant digit.

The comparator 300 has a value P0Si1P0Si0P0S01P0S02.P0S03P0S04P0S05P0S0 obtained by shifting the partial remainder by 2 bits to the higher order.
6, P0Ri1P0Ri0P0R01P0R02.P0R03P0R04P0R05 and divisor +1.
5 times DXi1DXi0.DX01DX02DX03DX04 are added to the three inputs, and the sum of the most significant digit C00Si3, the carry calculation bit C0 to the most significant digit
0Gi2, C00Pi2, C00Pi1, C00Gi0, C00P01, and C00G02 are output.

The comparator 301 adds three inputs of the value obtained by shifting the partial remainder by 2 bits higher and the divisor +0.5 times value 0.1D01D02D03, and adds the most significant digit sum C01Si3 and the most significant digit to the most significant digit. C01Gi2, C01Pi2, C01Pi1, C01Gi0, C01P01, C01G02
Is output.

The comparator 302 calculates the value obtained by shifting the partial remainder by 2 bits higher and the inverted value of the divisor +0.5 times 0.1D01D02D03 by 3
Input addition, sum C02Si3 of the most significant digit, bits C02Gi2, C02Pi2, C02Pi1, C02Gi0, C02P0 for carry calculation to the most significant digit
1, C02G02 is output. The comparator 303 calculates the value obtained by shifting the partial remainder by 2 bits upward and the divisor +1.5 times the value DXi1DXi0.DX01DX0
Add 3 inputs to the inverted value of 2DX03DX04 and add the most significant digit C04S
i3, bits C04Gi2, C04Pi2, for carry calculation to the most significant digit
C04Pi1, C04Gi0, C04P01, and C04G02 are output.

The preceding comparators 31, 32, 33, and 34 have the same logical configuration as the preceding comparator 30 in FIG. 8, except that the signal name of the partial remainder and the output signal name are different. The leading comparator 31 determines that the first two characters of the partial remainder and the output signal in FIG.
Turns into 1. The leading comparator 32 changes the partial remainder and the first two characters of the output signal in FIG. 8 to P2 and C2, respectively. The leading comparator 33 changes the partial remainder and the first two characters of the output signal in FIG. 8 to P3 and C3, respectively. The leading comparator 34 is shown in FIG.
, And the first two characters of the output signal are P4
And change to C4.

FIG. 9 is a logic diagram of the divisor multiple generation circuit 40 that generates 1.5 multiples of the divisor. Upper decimal point of divisor
Input 4 bits and output the sum value DXi1DXi0.DX01DX02DX03DX04 of 1.D01D02D03D04 and 0.0D01D02D03.

FIG. 10 is a logic diagram of the higher-order partial remainder selector 15. One of the five partial remainder preceding calculation values input to the five-input selector is selected by a select signal. SEL
When 0 is 1, P0Si1P0Si0.P0S01 ... P0S09 and P0Ri1P0Ri
0.P0R01 ... P0R08 is selected. If SEL1 is 1, P1S
i1P1Si0.P1S01 ... P1S09 and P1Ri1P1Ri0.P1R01 ... P1R08
And select. If SEL2 is 1, P2Si1P2Si0.P2S01 ...
P2S09 and P2Ri1P2Ri0.P2R01 ... P2R08 are selected. SEL
When 3 is 1, P3Si1P3Si0.P3S01 ... P3S09 and P3Ri1P3Ri
0.P3R01 ... P3R08 is selected. If SEL4 is 1, P4S
i1P4Si0.P4S01 ・ ・ ・ ・ P4S09 and P4Ri1P4Ri0.P4R01 ・ ・ ・ ・ P4R08
And select.

FIG. 11 is a logic diagram of the comparison value selector 35. The selector 350 calculates the preceding calculated value of the partial remainder and the divisor of -1.
Select data in the middle of comparison with 5-fold value. The selector 351 is
Select data in the middle of comparison between the preceding calculated value of the partial remainder and -0.5 times the divisor. The selector 352 selects data in the middle of comparison between the preceding calculated value of the partial remainder and the + 0.5-times value of the divisor. The selector 353 selects data in the middle of comparison between the preceding calculated value of the partial remainder and +1.5 times the divisor. When the select signals that become 1 are SEL0, SEL1, SEL2, SEL3, and SEL4, the data in the middle of comparison with the initials C0, C1, C2, C3, and C4 are selected.

FIG. 12 is a logic diagram of the quotient digit calculation circuit 50. The quotient digit calculation circuit 50 includes the magnitude judgment circuits 500 and 5
01, 502, and 503 and a select signal generation circuit 504.
The magnitude determination circuits 500, 501, 502, and 503 assign the partial remainder to the top two
Bit-shifted value and divisor -1.5 times value, -0.5 times value, +0.5
Data during comparison with the double value and the +1.5 value are input, and signals PRGE0, PRGE1, PRGE2, and PRGE3 that become 1 when the value obtained by shifting the partial remainder by the upper 2 bits is greater or equal are output. During the execution of the quotient calculation, the select signal generation circuit 504
A select signal is generated by 0, PRGE1, PRGE2, and PRGE3. When PRGE0 = 0 and PRGE1 = 0, the quotient digit is obtained as -2, and only SEL4 is set to 1. When PRGE0 = 1 and PRGE1 = 0, the quotient digit is obtained as −1, and only SEL3 is set to 1. P
When RGE1 = 1 and PRGE2 = 0, the quotient digit is calculated as 0,
Only SEL0 is set to 1. When PRGE2 = 1 and PRGE3 = 0, the quotient digit is obtained as +1 and only SEL1 is set to 1. PRGE2 = 1,
When PRGE3 = 1, the quotient digit is obtained as +2, and only SEL2 is set to 1. When the quotient calculation is not being executed, only SEL0 is set to 1. At the beginning of the quotient calculation, the partial remainder selector 15 and the comparison value selector 35 select the dividend and the data in the middle of the comparison between the dividend and the divisor, and the lower partial remainder calculation circuit 16 calculates the value obtained by shifting the dividend by the lower 2 bits. I do.

FIG. 13 is a block diagram showing an example of the configuration of the quotient register 60. The quotient digit is -2, -1, 0, +1, +2
Therefore, the absolute value of each of the positive value and the negative value is stored in a separate register. Register 600
Inputs the select signals SEL2 and SEL1 and shifts the previously stored data by two bits upward. Quotient digit-
Inputs for 2, -1, 0, +1, +2 are 00, 00, 0 respectively
0, 01, and 10. Positive quotients Pi0.P01P02 ... P54 are obtained by 28 quotient digit calculations. The register 601 receives the select signals SEL4 and SEL3, and shifts the previously stored data by 2 bits at a time. The quotient digit is -2, -1, 0, +
The inputs in the case of 1, +2 are 10, 01, 00, 00, 00, respectively. Negative quotient Mi0.M01M02 by 28 quotient digit calculations
.... M54 is obtained. Dividend is 0 or more and less than 2, divisor is 1 or more
Since there are conditions less than 2, the quotient is greater than or equal to 0 and less than 2. Therefore, the integer part of the quotient may be one bit.

FIG. 14 is a logic diagram of the final remainder checker 70. The final residue checker 70 is a circuit for detecting the presence or absence of a residue.
It comprises 700 to 707 and code detection circuits 710 to 717. The upper 6 bits of the partial remainder are input to detection circuits 700 and 710, and the following bits are input to detection circuits 701 to 706 and 711 to 71 in 8-bit units.
Enter 6 The detection circuits 701 to 705 have the same logic as the detection circuit 706, and the detection circuits 711 to 715 have the same logic as the detection circuit 716. The detection circuits 700 to 706 detect the presence or absence of a remainder for each field without performing carry propagation addition on the partial remainder in the carry storage format. The input detection circuit 707 is
The sum RM of the detection signals of 00 to 706 is obtained. If there is a remainder, R
M = 1. The detection circuit 710 detects a signal PG indicating that the sign is positive when there is no carry from the lower order, and a signal PP that indicates that the sign is positive when there is a carry from the lower order. 711 to 716 detect a carry G to the upper part when there is no carry from the lower part and a carry P to the upper part when there is a carry from the lower part every 8 bits. The detection circuit 717
Using the detection signals of the detection circuits 710 to 716, a signal RS whose final remainder means positive is obtained.

FIG. 15 is a block diagram showing an example of the configuration of a floating-point arithmetic unit having a divider according to the present invention. The floating-point division is performed by the divider 1. Digitizer 2 is
The floating point addition is used, and the partial product adder 3 is used for floating point multiplication. The selectors 5 and 6 select data to be input to the adder 7. The adder 7 adds the intermediate values of the calculations, the calculator 8 normalizes them, and performs rounding. The sign and the exponent are calculated by the arithmetic unit 4, and normalization and rounding correction are performed. In the floating-point division, first, the divider 1 calculates a positive quotient and a negative quotient, the presence or absence of a remainder, and a sign. When the remainder is 0 or positive, the adder 7 adds the two's complement of the positive quotient and the negative quotient. If the remainder is negative, the adder 7 adds the one's complement of the positive quotient and the negative quotient. As a result of the addition, a quotient and a remainder of 1 bit having an integer part of 1 bit and a decimal part of 54 bits are obtained, and the division processing is completed by normalization and rounding processing.

[0058]

According to the present invention, it is possible to reduce the processing time for one iteration of the quotient repetitive calculation which takes the longest time in floating point division. In other words, the quotient calculation and the partial remainder calculation, which have been conventionally sequentially processed, are almost parallelized, and the iterative calculation of the quotient can be speeded up to almost twice. Therefore, the performance of division is improved.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of an embodiment of a divider to which the present invention is applied to a quaternary SRT division algorithm.

FIG. 2 is a logic diagram of an upper partial remainder preceding calculation circuit 10 and an input data selector 20;

FIG. 3 is a logic diagram of the upper partial remainder preceding calculation circuit 11;

FIG. 4 is a logic diagram of an upper partial remainder preceding calculation circuit 12;

FIG. 5 is a logic diagram of an upper partial remainder preceding calculation circuit 13;

FIG. 6 is a logic diagram of the upper partial remainder preceding calculation circuit 14;

FIG. 7 shows an input data selector 21 and a lower partial remainder calculation circuit.
It is a 16 logic diagram.

FIG. 8 is a logic diagram of the preceding comparator 30.

9 is a logic diagram of a divisor multiple generation circuit 40. FIG.

FIG. 10 is a logic diagram of an upper partial remainder selector 15;

11 is a logic diagram of the comparison value selector 35. FIG.

12 is a logic diagram of the quotient digit calculation circuit 50. FIG.

FIG. 13 is a block diagram illustrating an example of a configuration of a quotient register 60.

FIG. 14 is a logic diagram of the final remainder checker 70.

FIG. 15 is a block diagram illustrating an example of a configuration of a floating-point arithmetic device including a divider according to the present invention.

[Explanation of symbols]

1 Divider 2 Digit aligner 3 Partial product adder 4 Sign and exponent calculator 5 Intermediate data selector 6 Intermediate data selector 7 Adder 8 Normalizer, rounder 9 Exponent corrector 10 Upper partial remainder when quotient digit is 0 Leading calculation circuit 11 Leading partial remainder leading calculation circuit when quotient digit is +1 12 Leading partial remainder leading calculation circuit when quotient digit is +13 13 Leading partial remainder leading calculation circuit when quotient digit is -1 14 High-order partial remainder preceding calculation circuit when the digit is -2 15 High-order partial remainder selector 16 Low-order partial remainder calculation circuit 20 Input data selector 21 Input data selector 30 When the quotient digit is 0, the preceding comparison circuit between the high-order partial remainder and the divisor 31 Preliminary comparison circuit between upper partial remainder and divisor when quotient digit is +1 32 Preliminary comparison circuit between higher partial remainder and divisor when quotient digit is +2 33 Upper partial remainder when quotient digit is -1 And elimination Preliminary comparison circuit with number 34 Preliminary comparison circuit with upper partial remainder and divisor when quotient digit is -2 35 Comparison value selector 40 Divider multiple generation circuit 50 quotient digit calculation circuit 60 quotient register 70 Final remainder checker 160 quotient and divisor Multiplication circuit 161 Carry save adder 300 Preliminary comparison circuit of partial remainder and -1.5 times divisor when quotient digit is 0 301 Preceding partial remainder and -0.5 times value of divisor when quotient digit is 0 Comparison circuit 302 Preliminary comparison circuit of partial remainder when quotient digit is 0 and +0.5 times divisor 303 Preliminary comparison circuit of partial remainder when quotient digit is 0 and +1.5 times divisor 350 Selector for data in the middle of comparison with -1.5 times the divisor 351 Selector for data in the middle of comparison between the partial remainder and -0.5 times the divisor 352 Selector for data in the middle of comparison between the partial remainder and +0.5 times the divisor 353 Partial remainder Of the data in the middle of comparison with +1.5 times the divisor Selector 500 A magnitude comparison circuit between partial remainder and -1.5 times divisor 501 A magnitude comparison circuit between partial remainder and -0.5 times divisor 502 A magnitude comparison circuit between partial remainder and +0.5 times divisor 503 Circuit for comparing magnitude with +1.5 times divisor 504 Select signal generator 600 Positive quotient register 601 Negative quotient register 700 to 707 Final remainder presence / absence detection circuit 710 to 717 Final remainder sign detection circuit

Claims (5)

(57) [Claims] 1. A method for calculating an n-bit quotient digit in an iterative high radix division control method for calculating a quotient of a binary number n bits at a time from an upper digit based on a dividend and a divisor represented by a binary number. In parallel with the step of calculating the quotient digit, a step of pre-calculating the partial remainder for all possible values as the quotient digit, and a step of pre-calculating the part in parallel with the step of calculating the quotient digit A step of pre-calculating the next quotient digit from the remainder and the divisor, and when the n-bit quotient digit is calculated, select a value corresponding to the quotient digit from the pre-calculated partial remainder, A step of selecting a value corresponding to the quotient digit from the preceding calculation value of the next quotient digit, and storing the selected partial remainder and the quotient digit;
A high radix division control method, comprising: proceeding to the next preceding calculation of the partial remainder and the next quotient digit calculation. 2. An iterative high radix divider for calculating a quotient of a binary number n bits at a time from an upper digit based on a dividend and a divisor represented by a binary number, and means for calculating an n-bit quotient digit. Means for pre-calculating partial remainders for all quotient digit values that can be taken as the quotient digit, in parallel with the calculation of the quotient digit, and, in parallel with the calculation of the quotient digit, Means for pre-calculating the next quotient digit from the divisor, means for selecting the pre-calculated value of the partial remainder corresponding to the calculated quotient digit, and pre-calculated value for the next quotient digit corresponding to the calculated quotient digit Means for storing the selected partial remainder and the quotient digit; and selecting the selected partial remainder and the quotient digit for the next n-bit operation. High-Radix divider, characterized in that a means for convolving the calculation means. 3. An iterative high-radix divider for calculating a quotient of a binary number n bits at a time from a high-order digit based on a dividend and a divisor represented by a binary number, and means for calculating an n-bit quotient digit. In parallel with the calculation of the quotient digit, a partial remainder precedence calculation circuit for inputting a partial remainder and a divisor and precalculating a partial remainder for all values that can be taken as a quotient digit, and in parallel with the calculation of the quotient digit A quotient precedence calculation circuit that pre-calculates the next quotient digit from the pre-calculated partial remainder and the divisor, and when the n-bit quotient digit is calculated, the quotient is calculated from the pre-calculated partial remainder. A partial remainder selector for selecting a value corresponding to the quotient digit; and, when the n-bit quotient digit is calculated, a partial remainder selector for selecting the value from the previously calculated quotient digit. Quotient leading value selector for selecting the value to be input, input data selector for selecting one of the selected partial remainder and dividend, and quotient digit for calculating the next quotient digit according to the preceding calculated value of the selected quotient A high radix divider comprising a calculation circuit. 4. The high radix divider according to claim 3, wherein an output of said partial remainder selector is connected to all partial remainder preceding calculation circuits, and said input data selector assumes a quotient digit of 0. One of the output of the remainder leading calculation circuit and the dividend is selected, the output of the input data selector is connected to the quotient leading calculation circuit that assumes 0 as the quotient digit, and the partial remainder selector is used as the quotient with the output of the input selector. A correct value is selected from the outputs of the partial remainder leading calculation circuit assuming a value other than 0, and before the quotient digit calculation, the input data selector selects the dividend, and before the quotient digit calculation, the partial remainder selector and the quotient leading The calculated value selector selects a value calculated assuming 0 as a quotient digit, and the input data selector selects a partial dividend during the quotient digit calculation. A high radix divider, wherein during the quotient digit calculation, the partial remainder selector and the quotient leading value selector select the value calculated assuming the calculated quotient digit. 5. The high radix divider according to claim 3, wherein said partial remainder preceding calculation circuit is capable of calculating a quotient digit using a partial remainder and a high-order several bits of a divisor.
When the RT division algorithm is used, only the bits necessary for the quotient digit calculation are calculated, and the lower part after the quotient digit calculation is supplied to supply the lower data of the partial remainder preceding calculation value which disappears by n bits at each calculation. A high radix divider comprising a lower partial remainder calculation circuit for calculating a remainder.