JPH0370252B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a high-radix non-recovery division device, and particularly to a control circuit that predicts partial quotients at higher speed.

Conventionally, as one method of division, a non-recovery division method has been widely used in which a quotient is determined by repeatedly adding and subtracting k times the divisor.
(For example, patent application No. 59-015621, patent application No. 59-057676,
(See Japanese Patent Application No. 59-070353.) In the i-th step of this non-recovery division, the following equation is used.

pi+1=r×pi−mi×d... −d<pi+1<d... However, pi is the partial remainder, d is the divisor, r is the radix mi is the partial quotient, and if the radix is r, then -r+1≦mi≦r− 1 mi is selected so that pi+1 obtained by calculating equation 1 satisfies the condition, and m is used to calculate.

On an actual computer, mi is determined by extracting the high-order bits of pi and d (referred to as Pi and D, respectively) by the number of digits with sufficient precision to determine mi, and searching the partial quotient prediction table. , its mi
Determine the exact pi+1 from the formula using

Here, various methods are known to realize the calculation of the formula mi x d, such as a method using a multiplier, a method using a subtraction register for each multiple, a method using a carry save adder, etc. The subtraction of pi-mi×d can be realized by a known method such as a normal addition/subtraction circuit.

In addition, as a method for realizing a partial quotient prediction circuit, we focused on reducing the size of the prediction circuit by configuring it hierarchically, and that the prediction table is nearly symmetrical with respect to positive and negative Pi. Techniques for reducing the number of prediction circuits are also known.

A method for reducing the prediction circuit by focusing on the fact that the prediction table is nearly symmetrical with respect to the positive and negative Pi is disclosed in Japanese Patent Application No. 59-070353. Two types of tables should be provided depending on the sign of one sign (for example, positive sign).
The hardware amount of the partial quotient prediction circuit in a high-radix non-recovery division device is reduced to about half that of the conventional system.

However, in this method, by the Pi,
There is a problem in that it takes a long time to decode to search the prediction table, and it takes time to predict the partial quotient, so a method for speeding up the process has been desired.

[Conventional technology]

FIG. 2 is a block diagram showing a conventional example of a high radix non-recovery type division device.

First, the divisor is placed in the divisor register DSR1,
It is input to the multiple generation circuit MULT2.

The multiple generation circuit MULT2 receives the partial quotient prediction signal (hereinafter referred to as m) from the partial quotient prediction circuit QP3, and receives -15, -14, - when the base is 16.
13,...,-2,-1,0,+1,+2,...,+14,+15
This is a circuit that creates a divisor of times, such as a method of creating all multiples in advance and selecting them, a method of using a general-purpose multiplier, a method of using a subtraction register whose number is smaller than the base number mentioned above, and a multi-stage carry storage. Various methods are known, such as a method of calculating using an adder CSA (see Japanese Patent Application No. 59-015621).

In the partial remainder register PR4, after the dividend is set at the beginning of the calculation, a new partial remainder Pi is set every calculation cycle thereafter.

The first adder 1 ADDER1 51 receives the high-order bits of the partial remainder register PR4 and the multiple generation circuit.
The upper few bits of mDSR, which is the output of MULT2,
and a carry signal from the second adder 2 ADDER2 52 [output signal of the carry look ahead circuit CLA521]
Addition is performed using the complement generator COMP10
is output to the remainder register RMD6.

In the complement generator COMP10, adder 1
When the sign bit of ADDER1 51 is '1',
When the sign bit is '0', the one's complement of the input data [output of the first adder ADDER1 51] is sent to the second decoding circuit DEC.
It functions to output to 11.

The second decoding circuit DEC11 decodes the result obtained by the complement generator COMP10,
Input to partial quotient prediction circuit QP3.

In the partial quotient prediction circuit QP3, “PRi+
mDSR” [i.e., first adder 1 ADDER1 51
Using the decoding result of the upper few bits of [output] and the upper few bits of the divisor register DSR1 as input,
The control signal (partial quotient prediction signal) m for the partial quotient and multiple generation circuit MULT2 is generated.

The partial quotient generator QG8 is the partial quotient prediction circuit QP
3 and the sign bit of the partial remainder register PR4, the correct partial quotient is determined and stored in the quotient register QR9.

The second adder 2 ADDER2 52 receives the lower bits of the partial remainder register PR4 and the multiple generation circuit.
This is an adder that takes as input the lower bits of the output mDSR of MULT2 (that is, the part of the data that is not input to the first adder 1 ADDER1 51), and a carry look-ahead circuit CLA521 is added for high-speed calculation. There is.

Remainder register RMD6 is used for repetitive operation PRi+
This is a register that holds the final prediction remainder of mDSR.
The correct remainder is output through RMDC7.

The specific correction method in the remainder corrector RMDC7 is as follows.
If the output of remainder register RMD6 is negative,
"Output of remainder register RMD6 + divisor register
However, if the output of the remainder register RMD6 is positive, the output of the remainder register RMD6 is output as it is.

As is clear from this figure, in the conventional system, the output of the carry look-ahead circuit CLA521 attached to the second adder 2ADDER252 is
The output of the complement generator COMP10 is inputted to the adder 1 ADDER1 51 according to the result.
It is characterized in that it is decoded by the decoding circuit DEC11, and the partial quotient prediction signal m is generated by the partial quotient prediction circuit QP3.

[Problem that the invention seeks to solve]

In the conventional system shown in FIG. 2, the bit width of the second adder 2 ADDER2 52 is generally compared to the bit width of the first adder 1 ADDER1 51.
Because it is very large, the second adder 2 ADDER2 5
Carry signal from 2 [i.e., carry look ahead circuit
CLA521 output signal] will be generated with a considerable delay.

Therefore, a lot of time is required until the output of the first adder 1ADDER1 51 is obtained, which is a factor that increases the overall one operation cycle time of the high radix non-recovery type division device.

In view of the above-mentioned drawbacks of the conventional art, the present invention has been developed by
By modifying the configuration of the conventional system, which includes the upper few bits of MULT2mDSR, the carry signal from the carry look-ahead circuit CLA521, and the second decoding circuit DEC11,
``The upper few bits of the partial remainder register PR4, the upper several bits of the multiple generator circuit MULT2mDSR, the first decoding circuit MDEC with a modification function, the carry signal from the carry look ahead circuit CLA521, and the corresponding correction circuit.'' By configuring 1
It is an object of the present invention to provide a division device that speeds up the cycle time.

[Means for solving problems]

The purpose of this is to provide a high-radix non-recovery type division device that obtains a quotient of n bits in one cycle time, and has a partial remainder register PR, a divisor register DSR, a multiple generation circuit MULT, and a carry look-ahead circuit CLA. a first addition circuit that detects the sign of the partial remainder and outputs the upper digit of the partial remainder; When the sign detected by the circuit and the first adding circuit is negative, the complement of the upper digit of the partial remainder is outputted, and when the sign is positive, the complement of the upper digit of the partial remainder is outputted. generator
COMP, a second decoding circuit DEC that decodes the output of the complement generator COMP, a first decoding circuit MDEC with a modification that can control the decoding method depending on the sign of the partial remainder; 2, and two partial quotient predictors QP2, QP whose inputs are the outputs of the first two decoding circuits DEC and MDEC, respectively.
From the two outputs of 1, the above carry look-ahead circuit CLA
a selection circuit that selects the control signal m to the multiple generator circuit MULT, depending on the presence or absence of a carry signal from
In the first decoding circuit MDEC, when the sign of the partial remainder is '0' (positive), a decoded signal assuming +1 is generated, and the sign of the partial remainder is '1'.
(negative), it is configured to generate a decoded signal assuming -1, and when there is no carry signal from the carry look ahead circuit CLA, partial quotient prediction is performed using the output of the first decoding circuit DEC. According to the present invention, the output of the partial quotient predictor QP1 based on the output of the first decoding circuit MDEC is selected when there is a carry signal from the carry look ahead circuit CLA. This is achieved by providing a high radix non-recoverable divider.

[Effect]

That is, according to the present invention, the partial remainder register PR
and the predicted partial quotient PPQ from the value of the divisor register DSR.
When calculating the predicted partial quotient, refer to the high-order bits of the partial remainder register PR and divisor register DSR.
PPQ is required.

The propagation of the carry signal increases rapidly as the number of digits increases.

Focusing on the following two points, (1) Perform provisional addition of the partial remainders using only the upper few bits above, detect the sign of the partial remainder obtained by the provisional addition, and confirm that the detected sign is negative. a complement generator COMP which outputs the complement of the high-order digit of the partial remainder when , and when the sign is positive, outputs the high-order digit of the partial remainder;
A second decoding circuit DEC decodes the output of COMP, and depending on the sign of the partial remainder,
a first decoding circuit MDEC with a qualification that can control the decoding method;
A partial quotient predictor QP2 is provided for the outputs of the two decoding circuits DEC and MDEC in two ways: when there is no carry and when there is a carry, respectively.
In the first decoding circuit MDEC, it is necessary to perform decoding when there is the carry, so when the sign of the partial remainder is '0' (positive), Furthermore, by predicting that the partial remainder will increase by at most "1" by the carry signal, a decoded signal assuming +1 is generated, and the sign of the partial remainder is '1' (negative).
Even when ) Among the output results obtained from the respective partial quotient predictors QP1 and QP2, if there is no carry signal, select the output of the partial quotient predictor QP2, and if there is a carry, select the output of the partial quotient predictor QP2. Since the output of the partial quotient predictor QP1 is selected to create the true partial quotient prediction signal m [control signal for the multiple generation circuit (MULT)],
This has the effect of shortening the one operation cycle time of the high radix non-recovery type division device.

〔Example〕

Embodiments of the present invention will be described in detail below with reference to the drawings.
FIG. 1 shows an embodiment of the present invention in block diagram form.
1, 6, 7, 8, 9, 10, and 11 are the same as those explained in FIG.
and the partial quotient prediction circuit (QP) 3 explained in FIG.
Partial quotient prediction circuit (QP1) with the same function as 3
1 is a functional block newly added to implement the present invention.

Since the basic operation of the high radix non-recovery division device embodying the present invention is the same as that of the conventional system, only the characteristic parts of the present invention will be explained here.

First, the first decoding circuit (MDEC) 111 with a modification function detects the partial remainder when there is a carry signal from the carry look-ahead circuit of the second adder 2 (ADDER2), as described above. Since this is a decoding circuit for generating a decoded signal for the upper few bits of Sometimes the adder 1 (ADDER
Take the output of 1), that is, take the absolute value of the upper digit of the partial remainder, predict that it will increase by at most '1', create a decoded signal assuming +1, and calculate that the sign bit is When it is '1' (negative), the one's complement of the output of the first adder 1 (ADDER1) is taken, that is, it is predicted that the absolute value of the upper digit of the partial remainder will increase by at most '1'. This is a circuit that creates a decoded signal assuming -1 in the absolute value expression, and selector SEL12 is a carry look-ahead circuit.
This circuit selects one of the partial quotient prediction circuits QP1, 3, QP2, and 31 according to the output signal of the CLA 521.

Specifically, when the output of the carry look ahead circuit CLA521 is '1' (that is, there is a carry), the partial quotient prediction circuit QP1,31 is selected and the output is '1' (that is, there is a carry).
In the case of 0' (ie, no carry), it functions to select partial quotient prediction circuits QP2 and QP3.

Next, an example of the decoding function of the normal decoder DEC11 is shown in FIG.
An example of the decoding function of No. 1 is shown in FIG.

Now, we will specifically explain an example of the operation when outputting the partial quotient prediction signal m according to the present invention for two cases in which the output data of the first adder 1 ADDER1 51 [i.e., the upper digits of PRi+mDSR] is positive and negative. Explain using data.

Example 1 If the output data of the first adder 1 ADDER1 51 is '00100', the sign bit of the data is '0'.
Since it is (positive), the carry look-ahead circuit CLA52
If there is no carry from 1, decoder DEC11
The output of the normal decoding circuit [shown in Fig. 3 1,
If there is a carry, the above data will be '
00101', the first decoding circuit MDEC111 with a modification function inputs ' with a sign.
The partial quotient prediction signal obtained by inputting the output of the decoding circuit when 00100' is input (the decoding output that turns on line 5 as shown in FIG. 4 2) into the partial quotient prediction circuit QP1, 31 is , a correct partial quotient prediction signal m can be obtained by controlling the selector SEL12 to select based on the carry from the carry look ahead circuit CLA521.

Example 2 If the output data of the first adder 1 ADDER1 51 is '11011', the sign bit of the data is '1'.
(negative), so according to the logic disclosed in Japanese Patent Application No. 070353, the first adder 1ADDER1
The one's complement output of the output of 51 is the second decoding circuit.
The signal is input to the DEC11 and the first decoding circuit MDEC11, and the absolute value of the partial quotient prediction signal m is output based on the value.

Therefore, in this case, the carry look-ahead circuit CLA52
If there is no carry from 1, the 1's complement (i.e. absolute value representation) of the data '1011' without the sign is '
0100', the decoder for the complement output
Output of the normal decoder circuit of DEC11 [Decode output that turns on line 4, shown in Figure 3 1]
If there is a carry, the original data will be '11100', so the complement output will be '0011' excluding the sign. In anticipation of this, the first decoding circuit MDEC111 with a modification function is
The output of the decoding circuit when '10100' with a sign is input [the decoding output that turns on line 3 as shown in FIG.
A correct partial quotient prediction signal m can be obtained by controlling the selector SEL12 to select the partial quotient prediction signal obtained by inputting the partial quotient signal m into the signal m, based on the carry from the carry look-ahead circuit CLA521.

The above is just one example, and the first adder 1ADDER1 and the second adder 2
It is not necessary to completely separate the number of bits from ADDER2; for example, the second adder 2 ADDER2 may be configured with the entire number of bits, and the first adder 1 ADDER1 may be configured with the higher number of bits. Yes, it goes without saying. In this case, the first
Since the adder 1 ADDER1 side needs to predict the partial quotient mi at high speed, it is effective to use the minimum number of bits necessary to predict the partial quotient mi.

In this way, in the present invention, the first decoding circuit MDEC111 with the above-mentioned modification function basically sets the sign bit of the adder 1ADDER1 to '0'.
The feature is that when the sign bit is '1' (positive), a decoded signal assuming +1 is created, and when the sign bit is '1' (negative), a decoded signal is created assuming -1. .

〔Effect of the invention〕

As described above in detail, the high radix non-recovery division device of the present invention includes a partial remainder register PR,
When calculating the predicted partial quotient PPQ from the value of the divisor register DSR, the predicted partial quotient can be calculated by referring to the high-order bits of the partial remainder register PR and the divisor register DSR.
PPQ is required.

The propagation of the carry signal increases rapidly as the number of digits increases.

Focusing on the following two points, (1) Perform provisional addition of the partial remainders using only the upper few bits above, detect the sign of the partial remainder obtained by the provisional addition, and confirm that the detected sign is negative. When , the complement of the upper digit of the partial remainder is output, and when the sign is positive, the complement generator COMP outputs the upper digit of the partial remainder. input to a second decoding circuit DEC to be decoded and a first decoding circuit MDEC with a modification capable of controlling the decoding method depending on the sign of the partial remainder;
The outputs of the first two decoding circuits DEC and MDEC are
Partial quotient predictor QP is provided for two cases, one without carry and one with carry.
2. Configure it to input to QP1, and
In the decoding circuit MDEC, it is necessary to perform decoding when there is the carry, so when the sign of the partial remainder is '0' (positive), the carry signal further decodes the partial remainder. By predicting that the partial remainder will increase by at most "1", a decoded signal assuming +1 is generated, and the sign of the partial remainder is '1' (negative).
Even when , it is configured to predict that the partial remainder will increase by at most "1" due to the carry signal, and to generate a decoded signal assuming -1 in terms of absolute value, (2) From the results obtained from each partial quotient predictor and the carry signal, the true partial quotient prediction signal m
(control signal for the multiple generator MULT), it is possible to reduce the one operation cycle time of the high radix non-recovery type division device.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an embodiment of the present invention, FIG. 2 is a block diagram showing an example of the configuration of a conventional high-radix non-recovery division device, and FIG. 3 is a block diagram of a conventional decoder. FIG. 4 is a diagram showing an example of the decoding function of a decoding circuit with a modification function necessary to implement the present invention.
It is. In the drawing, 1 is a divisor register DSR, 2 is a multiple generation circuit MULT, 3 is a partial quotient prediction circuit QP,
QP2, 31 are partial quotient prediction circuits QP1, 4 are partial remainder registers PR, 51 is the first adder 1
ADDER1, 52 is the second adder 2 ADDER2, 5
21 is a carry look ahead circuit CLA, 6 is a remainder register
RMD, 7 is remainder corrector RMDC, 8 is partial quotient generator QG, 9 is quotient register QR, 10 is complement generator
COMP, 11 is the second decoding circuit DEC, 111 is the first decoding circuit MDEC with a modification function, 12 is the selector SEL, m is the partial quotient prediction signal, and mDSR is the output signal of the multiple generator circuit MULT, respectively.

Claims (1)

[Claims] 1. A high-radix non-recovery type division device that obtains a quotient of n bits in one cycle time, comprising a partial remainder register PR and a divisor register DSR.
, multiple generation circuit MULT, and carry look ahead circuit
Second adder circuit with CLA and partial quotient predictor QP
, partial quotient generator QG, and remainder correction circuit RMDC
and a first addition circuit that detects the sign of the partial remainder and outputs the upper digit of the partial remainder, and when the sign detected by the first addition circuit is negative, the upper digit of the partial remainder is output. a complement generator COMP that outputs a digit complement and, when the sign is positive, outputs the upper digit of the partial remainder; a second decoding circuit DEC that decodes the output of the complement generator COMP; a first decoding circuit MDEC with a modification capable of controlling the decoding method according to the sign of the partial remainder;
and two partial quotient predictors QP whose inputs are the outputs of the first two decoding circuits DEC and MDEC, respectively.
2. A selection circuit SEL that selects a control signal m to be sent to the multiple generation circuit MULT from the two outputs of QP1 depending on the presence or absence of a carry signal from the carry look-ahead circuit CLA; In the decoding circuit MDEC, when the sign of the partial remainder is '0' (positive), a decoded signal assuming +1 is generated, and the sign of the partial remainder is '1'.
(negative), it is configured to generate a decoded signal assuming -1, and when there is no carry signal from the carry look ahead circuit CLA, partial quotient prediction is performed using the output of the second composite circuit DEC. When there is a carry signal from the carry look ahead circuit CLA, the output of the partial quotient predictor QP1 based on the output of the first composite circuit MDEC is selected. A high-radix nonrecovery divider with