JPS60201435A - Dividing device - Google Patents

Abstract

PURPOSE:To curtail the quantity of hardware for retrieving forecasting partial quotient from a table by constituting hierarchically a table for retrieving the forecasting partial quotient from a divisor register, as a result of addtion and subtraction. CONSTITUTION:A divisor is stored in a divisor register 1, inputted to a multiple generating circuit 2, and the multiple generating circuit 2 receives a partial quotient forecasting signal (m) from a partial quotient forecasting circuit 3, and generates divisors of -15, -14,...0, +1, +2,...+15 times, in case when a radix is 16. The partial quotient forecasting circuit 3 calculates a value of (m) of (m)X DSR to be added and subtracted in the next time, from an output of a carry propagation adder (CPA)5 and an output of the divisor register (DSR)1. In a non- recovery type division when the radix is 16, when determining high-order 4 bits, in (m) of 5 bits containing an essential code, it is sufficient by high-order 5 bits of the CPA and high-order 6 bits (essential 9 bits) of the DSR. The CPA and (m) prepare a table of 5 bits and 4 bits, respectively, as a rough forecasting, (m) is derived from the CPA (5 bits) and the DSR (6 bits), and in case of a precise forecasting for correcting (m), a correcting table of the CPA 6 bits and (m) is prepared, and the least significant bit of (m) is derived.

Description

DETAILED DESCRIPTION OF THE INVENTION +al Technical Field of the Invention The present invention relates to a high radix non-recovery division device, and more particularly to a circuit configuration for realizing a partial quotient prediction circuit with a smaller amount of hardware.

(bl Technological background) Conventionally, one method of division is the non-recovery division method. In this method, the set of quotients used to create each digit of the quotient is Noting that there is a quotient set, control is performed to select each digit of the quotient from the quotient set.

The above signed quotient set is generally expressed as follows, where r is the base number.

(-(r-1),-(r-2),--,-1,+1.
---, r-2, r-1) Many arithmetic units perform operations not in units of l bits, but in units of "multiple bits," which is considered to be using a base greater than 2. be able to.

For example, in units of 2 bits, the base number is 4, and in units of 3 bits, the base number is 8.

Generally, an l-bit operation unit is the same as an m-digit number with r as the base, and is usually given as r-2 to the //m power.

The feature of non-recovery division is that, apart from the sign reversal of the dividend that occurs when determining each digit of the operation result, negative numbers are allowed for the digits of the operation result, and depending on the sign of the dividend, it can be added to the divisor or a multiple of the divisor. It is a so-called release method that adds or subtracts .

To give a specific example, for example, multiply the divisor [i.e. -(r-
1), −(r−2), −−, −1, +L−, r−2
．． r-1 times] in the subtraction register, select the subtraction register according to the prediction signal output from the partial quotient predictor, and repeat adding and subtracting times the divisor to calculate the quotient. It is something that will continue to grow.

In the above division method, using the plurality of bits as a unit,
There is a method for performing calculations, which is known as a high radix non-recovery type division device.

In this case, as mentioned above, as the number of bits n serving as the unit of operation increases, the base number increases by 2n, so the number of repetitions of the operation decreases, but it also increases the complexity of the divisor multiple circuit and the complexity of the quotient prediction logic. There is a problem in that the number of circuits increases significantly due to refinement.

However, for divisor multiple circuits, for example, methods are known in which calculations are performed using subtraction registers with a smaller number than the base number and multistage carry-save adders, but there are no effective partial quotient prediction logics. Currently, a method for configuring a partial quotient prediction circuit is awaited.

tc+ Prior Art and Problems As mentioned above, as a method of division, a non-recovery division method is often used in which the quotient is calculated by repeatedly adding and subtracting times of the divisor. A division method that performs calculations in units of is known as a high-radix non-recovery division device, and by increasing the radix, the number of repetitions of calculations is reduced, and high-speed calculations can be expected.

However, as the arithmetic unit becomes larger, the partial quotient prediction logic needs to be made more precise, resulting in a significant increase in the number of circuits.

fdl Object of the Invention In view of the shortcomings of the prior art, the present invention provides a circuit configuration that reduces the amount of hardware required for the partial quotient prediction logic by configuring the partial quotient prediction logic in a hierarchical manner. This is the purpose.

te+ Structure and object of the invention According to the present invention, there is provided a high radix non-recovery type division device that generates an n-bit quotient in one operation cycle time, which comprises a partial remainder register, a divisor register, and a multiple generation circuit. In a division device comprising a carry propagation adder, a partial quotient predictor, a partial quotient generator, and a remainder correction circuit, the partial quotient predictor is connected to the upper bit of the output of the carry propagation adder, and The upper bits of the divisor register
a first partial quotient prediction circuit that predicts the upper bits of the partial quotient; and a second part that predicts the lower bits of the partial quotient by using the output of the carry propagation adder and the lower bits of the divisor register as inputs. The present invention is achieved by providing a method of configuring a partial quotient prediction circuit, and has the advantage that a partial quotient prediction circuit can be achieved with a smaller amount of hardware than before.

ff) Embodiments of the Invention First, to summarize the gist of the present invention.
IL −(r−2L−+−1,+1+−+r−2.r−
1 times)) and the result of addition/subtraction (CPA) and the divisor register (
When calculating the predicted partial quotient (PP) from the value of DSR),
The upper bits of the predicted partial quotient (PPQ) are the upper bits of the above addition/subtraction result (CPA) and the divisor register (DSR).
), and by hierarchically configuring a table that searches the prediction partial quotient (PPQ) from the above addition/subtraction result (CPA) and the divisor register (DSR), prediction from the table is performed. Partial quotient (PP
This has achieved a reduction in the amount of hardware needed to search for

Embodiments of the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a block diagram showing the general configuration of a high radix non-recovery type division device (radix: 16) related to the present invention, and FIG. 2 is a schematic diagram of a partial quotient prediction table according to the conventional method. FIG. 3 is a diagram schematically showing a partial quotient prediction table constructed by implementing the present invention, and FIG. 4 is a block diagram of another embodiment to which the present invention is applied. 5 is a diagram showing the signal output from the coarse direction predictor and the signal output from the corrector in the application example explained in FIG. 4, and FIG.
It is a figure showing correspondence with a multiple.

In FIG. 1, l is a divisor register (DSR) in which a divisor is stored and inputted to a multiple generator (MDG) 2.

Multiple generator circuit (MDG) 2 is partial quotient prediction circuit ([lP
) Receiving the partial quotient prediction signal (m) from 3, if the above base is 16, -15, -14, -13, -, -2,
-1, 0, +1. +2. '--.

+14. This is a circuit that creates a divisor of +15 times, for example, a method of creating and selecting all the multiples in advance, a method of using a general-purpose multiplier, a method of using a subtraction register with a smaller number than the base number mentioned above, and a multi-stage carry. Various configuration methods are known, such as a method of calculating with a storage adder (C5A).

4 is a partial remainder register (PR) in which, after the dividend is set at the beginning of the operation, a new partial remainder is set every double operation cycle. 5 is a carry propagation adder (CPA)
Then, the partial remainder register (PR) is 4 and the divisor of m times (-1
5≦m≦+15; m is an integer) and register partial remainder register (PR) 4. Partial quotient prediction circuit (Kano) 3. Output to remainder register (RMD) 6, etc.

Remainder register (RMD) 6 is a register that holds the final predicted remainder of repeated operations. After completion of the repeated addition/subtraction operations, the correct remainder is outputted through remainder corrector (RMDC) 7. The specific correction method for the remainder corrector (RMDC) 7 is that when the sign bit of the remainder register (RFIO) 6 indicates a negative number, the two's complement is taken to obtain the remainder, and when the sign bit is a positive number, the remainder is obtained. operates in such a way that the value of that side is the remainder.

Partial quotient generator (QG) 8 is partial quotient prediction circuit (QP)
Referring to the output of 3 and the sign bit of partial remainder register (PR) 4, the correct partial quotient is determined and stored in quotient register (R) 9.

The partial quotient prediction circuit (QP) 3, which is the object of the present invention, consists of the output of a carry propagation adder (CPA) 5 (hereinafter referred to as cp^) and the output of a divisor register (DSR) 1 (hereinafter referred to as l).
mXDsR to be added and subtracted next from
This is a circuit that calculates the value of m, and logically it is CPA and DSR.
This corresponds to searching a table with m as an entry and m as its value.

However, if CPA and DSR are used as entries, the table will become huge. For example, in base-16 non-recovery division, CPA: 6 bits (6
4 entries) DSR: 9 bits (256 entries) However, it is assumed that the most significant bit is normalized to 1 as described later.

You need to configure the table.

Therefore, in reality, CPA1m is used as an entry for 111
A method is used in which a table with SR as its value is created and the table is reversely searched. The size of the table in this case is 64 x 32 as described later.
It becomes an entry and can be reduced to about 178. The present invention makes this table a hierarchical structure to further reduce the table.

The method for creating it will be explained in detail below.

First, when subtracting m from the aforementioned CPA and DSR,
If you want to measure only the upper few bits of m, use CPA
, just refer to the upper few bits of DSR.

For example, in the above-mentioned non-recovery division in the case of radix 16, the above 4 bits (
In order to determine the value (including the sign), the upper 5 bits (ordinarily 6 bits) of the CP and the upper 6 bits (original 9 bits) of the DSR are sufficient. That is,
The relationship between the precision of m and the required number of bits for CPA and DSH is shown in the table below.

Using the above property to create a chill pull that searches m from cp^, DSR, and considering that the table is divided into two stages, coarse and fine, and configured hierarchically, the coarse prediction is based on CPI Prepare a table of : 5 bits (32 entries) m : 4 bits (16 entries), and write the corresponding CPA (5 bits) and DSR.
For fine prediction to calculate m from (6 bits) and correct the m, prepare a table of CPA: 6 bits (64 entries) and correction of m (whether or not to set the lowest focus of m to "l"). and the CPA (6 bits).

Focus on the lowest point of m from DSR (9 bits).

By configuring the table in two stages in this way, the total table size is (32 x 16 entries) + (64 x 1 entries), which is considerably reduced compared to the 64 x 32 entry table described above. I understand.

Figure 2 shows the above-mentioned CPA, with m as the entry,
This is a schematic diagram of a detailed table when DSR is used as that value, and is a table of 64 x 32 entries.

In this figure, CPAO is the upper 6 bits (including the sign) of CPA extracted and expressed in decimal notation, and m is the signal of partial quotient prediction circuit (ΩP) 3 (partial quotient prediction signal).
It shows the value expressed in decimal notation.

This partial quotient prediction table (QPT (CPAO, II+)
), enter the upper 9 bits of DSR (hereinafter referred to as DSRO) and set the value to "1" or "0".
A logical function that takes rLcpaO,m ([1SRO)
JT: I will express it.

Here, to simplify the explanation, it is assumed that DSR is a positive number and is normalized so that the most significant bit is 1.

First, to explain the principles of high-radix non-recovery division, the divisor is divided by 21, the dividend is 21, the partial remainder is Pn, and the partial quotient δ is
When the 1-signal is m, high-radix non-recovery type division can be expressed by the following recurrence formula.

I'n+1=Pn + m X D And the n+1st quotient On+1 is the partial remainder Pn+1
should satisfy the following conditions. That is, −D<Pn+XD<D, the above logical function r LcpaO,m (DSRO
) J Ha, ■DSRO≦D <DSRO+δ (however, δ-1/2 to the 8th power) CPAO≦P <CPAO+ε
(However, ε21) is not satisfied and the value is "1" when the above division condition -D<Pn+mxD<I) is satisfied for all the numbers and P, and "0" otherwise.

■For different m and m', LcpaO,m (DSRO)=LcpaO,m'(D
SRO)-1, one is set to "1" and the other is set to "O".

The conditions for the partial quotient prediction table created in the above procedure to function are as follows: 1) All CPAOs and DSROs exist for a certain m months, and for that m, LcpaO,m (DSRO) = 1 is satisfied ( This can be called "condition I").

The partial quotient prediction table created based on the above method is
In Figure 2 above, when a 9-bit DSRO is input, only one input is sent to all CP8 (64).
There are three m, and the corresponding logical function: LcpaO,m
(DSRO)=1.

If DSRO is 8 bits, only one m exists for all CPAOs, and the condition 2 LcpaO,m (DSRO) = 1 is no longer satisfied, and the created table is It will no longer function as a partial quotient prediction table.

Conversely, if the SRO is an IO bit, all CPA
Since it becomes redundant for the condition that only one m exists for each O, the above 9 bits are used as partial quotient prediction to search for m in a high radix non-recoverable divider with radix -16. It can be said that the number of SRO bits is optimal for creating a table.

As mentioned above, the CPAO at this time is 6 bits (64 entries), and the obtained m is 5 bits (including the sign) (
32 entries), and functions as m necessary for a high radix non-recovery type division device with a radix of 16.

On the other hand, let m be 4 bits including the sign (represented by A1), and tabulate by inputting δ = 172 to the 5th power [that is, the upper 6 bits of DSR (represented by DSRI)] ], ε-2 [i.e., cp^ is 5 bits including the sign (C
(expressed in PAI)], the same procedure can be used to create a table that satisfies the above-mentioned [condition (2)].

This table is the coarse image prediction table shown in FIG. 3(a).

Comparing this table with the fine partial quotient prediction table in FIG. 2, it is found that in the fine partial quotient prediction table in FIG.
In the coarse fraction prediction table of FIG.

Therefore, in order to correct the error between the two, if "1'" exists at a location corresponding to an odd number m in the table of FIG. 2, that information is registered as a separate correction table, and the correction table is A more detailed m can be found by referring to . The table in FIG. 3 (ri) schematically shows this correction table.

A specific example of the correction method will be described below.

First, in the coarse partial prediction table, one CPA1
-30 column, for example, L'-30. −14=1, and in the correction table, the corresponding column (i.e.
CPA2=-30), L''-30=1 is corrected to L''-30,-13=1 corresponding to an odd number m (that is, m=-13).

If the correction value in the same column is L''-30=0, then C
For PAO=-30, it shows that "1" did not exist anywhere for odd number m, so
For example, L'-30. -1
4-1 is used as a detailed partial quotient prediction table.

Also, in the coarse partial picture prediction table, one CPAI=
-30 column, for example L'-30. -14-1, and in the correction table, in the column of CPA2-29, if L'' -29=1 5 , CPAO=-29, odd number m (that is, m=
-13), which is corrected to L''-29,-13=1.

That is, if L''-ao=i in the correction table, CPAO=- in the fine partial quotient prediction table of FIG.
In the column corresponding to 30, it is shown that one 1'' was present at any position of odd number m, and this was searched from the coarse fraction prediction table in Figure 3 (a). , as mentioned above, the main focus of the present invention is to set L'-30.-13=1 when L'-30,-14=1.

Therefore, if L'-30. If -12=1, L'
-30, -11=1. The operation will be as follows.

Since the above correction table is generated under the above conditions, each element of the table is expressed by the following formula. That is, L'' cpa2+m2 (DSR2) = ΣLc
pa2,2i+l (DSR2)=1 However, Σ is 1=-
Represents the logical sum from 8 to +7.

1, cpa2 is the upper 6 bits including the sign of the carry propagation adder output, and DSR2 is the upper 9 bits of the divisor.

The correction table created using the above conditional expression is
This is the table in Figure (b).

According to the present invention, the same function as the fine partial prediction table shown in FIG. 2 can be realized by the coarse partial prediction table in (a) and the correction table in (b) in FIG. It can be understood that the reduction of

In the explanation so far, two entries, CPA tm, have been used as entries in the partial quotient prediction table, but among these two entries, for m, -16 to +15
By replacing it with a coded code using a desired number of signals between the two, it is possible to create a signal that is effective for subsequent processing.

For example, Fig. 4 shows a subtraction register (
SRI~5R3) and a carry save adder (C5AI.

C3A2) is shown.

In FIG. 4, 1.4 to 9 are the same as those explained in FIG. 1, and 21 to 23 are multipliers (±1×) l(
±2×, ±4X), (±8×, ±16X), 210~
230 is the subtraction register (SRI), (SR2), (SR
3) , 51゜52 is a carry save adder (C5^1)
, (C5^2) , 31 is the coarse directional predictor (RQP)
, 32 is a corrector (DQP).

Now, when the divisor is set in the divisor register (DSR) 1 and the dividend is set in the partial remainder register (PR) 4, the dividend is transferred to the three manual carry save adder (C5A2) 52 and the carry propagation adder ( CPA) 5, it is input to a coarse directional predictor (RQP) 31 and a corrector (DQP) 32.

Coarse inter-prediction signals M3S, X161, X8. and M2S, X4
．． The approximate value of m above is calculated by X2, and the corrector (DQ
P) Correction signal output from 32? The correction value of m is calculated by lIS and XI, and the details of m are corrected.

Above, coarse inter-part prediction signal H3S, x 16. x L
and elbow S, X4. FIG. 5 shows the correspondence between X2, the correction signal Mis, X 1 and the multiple.

After performing such decoding, a multiplier (±8×.

±16X)23, (±2×, ±4×)22, and (±
1x) 21 to select one of a plurality of multiplication routes and store the result in the subtraction register (SR3) 230. (SR2
) 220 and (SRI) 210.

Next, the above three subtraction registers and the partial remainder register (
pH) 4 is a 2-stage 3-man carry save adder (C5^
1)51. (CSA2) 52 and a carry propagation adder (
CPA) 5 and the result is input again to the partial remainder register (PR) 4.

The output of the carry propagation adder (CPA) 5 is input to a coarse directional predictor (R(IP) 31. and a corrector (D[IP) 32.
3) 230. (SR2>220, and (SR1)2
1(operates to determine the input to l).

Above, coarse directional predictor (RGP) 31. and corrector (D
[ ] Coded signal M3S from PP32, x
16. x8. M2S, X4. X2 and Mis,
X1 corresponds to the partial quotient prediction signal m explained in FIG. 1, and the subtraction register (SR3) 230. (SR2)2
20 and (SRI) 210 is a non-recoverable division operation using the partial quotient prediction signal m.

9. Using the decoded signal shown in FIG. 5, for example, in order to obtain a partial quotient prediction signal m=-15, it can be obtained by combining -16 times, +2 times, and -1 times.

Of course, the above combination is just one example, and it goes without saying that the combination is not limited to this.

In this way, the subtraction register (
SRI~5R3) and carry save adder (to cs8).

It can be seen that the present invention can also be applied to a divider using CSA2).

fgl Effects of the Invention As explained in detail above, the division device of the present invention is capable of multiplying the value of the partial remainder register (PR) by the divisor (for example, −
(r4), −(r−2), −−, −1, +1. ---
-, r-2, r-1 times)) and the predicted partial quotient (PP) from the value of the divisor register (DSR).
When calculating the predicted partial quotient (PP(1)), pay attention to the fact that the upper bits of the predicted partial quotient (PP(1)) are determined by the upper bits of the above addition/subtraction result (CPA) and the upper bits of the divisor register (DSR). , the above addition/subtraction result (CPA), 0 By hierarchically configuring a table for searching the predicted partial quotient (PPQ) from the divisor register (DSR), the predicted partial quotient (PPQ) is retrieved from the table.
), it is possible to achieve the partial quotient prediction circuit in a high-radix non-recovery division device with a smaller amount of hardware than before.

[Brief explanation of drawings]

Fig. 1 is a block diagram showing the general configuration of a high radix non-recovery type division device (radix: 16) related to the present invention, and Fig. 2 schematically shows a partial quotient prediction table according to the conventional method. FIG. 3 is a diagram schematically showing a partial quotient prediction table constructed by implementing the present invention, FIG. 4 is a block diagram showing another embodiment to which the present invention is applied, and FIG. The figure is a diagram showing the correspondence between the signal output from the coarse directional predictor, the signal output from the corrector, and the multiple in the application example explained in FIG. 4. In the drawing, 1 is the divisor register (DSR), 2 is the multiple generator circuit (MDG), 3 is the partial quotient prediction circuit (Kano),
4 is partial remainder register (PR), 5 is carry propagation adder (CPA), 6 is remainder register (RMD), 7
is the remainder corrector (RMDC), and 8 is the partial quotient generator (ΩG
), 9 is a partial quotient register (OR), 21 to 23 are multipliers (±lx), (±2×, ±4X), (±8×, ±16
X), 210 to 230 are subtraction registers (SRI to 5R
3), 51.52 is a carry save adder (C3A1,
C3A2), 31 is a coarse direction predictor (R[lP),
32 indicates a corrector (DQP), respectively.

Claims (1)

[Claims] A high-radix non-recovery division device that generates an n-bit quotient in l operation cycle time, the device comprising: a partial remainder register, a divisor register, a multiple generation circuit, a carry propagation adder, a partial quotient predictor; In a division device comprising a partial quotient generator and a remainder correction circuit, the partial quotient predictor predicts the upper bits of the partial quotient using the upper bits of the output of the carry propagation adder and the upper bits of the divisor register. A first partial quotient prediction circuit and a second partial quotient prediction circuit predicting the lower focus of the partial quotient by inputting the output of the carry propagation adder and the lower bit conversion of the divisor register. A distinctive dividing device.