JP2551037B2 - Inverse arithmetic circuit - Google Patents

Description

The present invention relates to an inverse arithmetic circuit.

[Outline of Invention]

According to the present invention, in the reciprocal arithmetic circuit, the overflow of the two's complement arithmetic is positively incorporated into the error correction arithmetic to perform the minimum necessary arithmetic, thereby reducing the entire circuit scale.

[Conventional technology]

If the reciprocal number Y = 1 / X of the value X is obtained and the reciprocal number Y is multiplied by the value Z, the division Z / X can be performed.

When obtaining the reciprocal number Y, the reciprocal number Y can be obtained at high speed by the NR method (Newton-Raphson method). However, the iterative calculation of the NR method for obtaining the reciprocal number Y is given by the following equation. To be

Y ^{(n + 1)} = Y ⁽ⁿ⁾ (2-X · Y ⁽ⁿ⁾ ) (i) Then, using the relative error ε ⁽ⁿ⁾ at the n-th iteration, Y ⁽ⁿ⁾ = 1 / X · (1 + ε ⁽ⁿ⁾ ) (ii), the equation (i) becomes Y ^{( n) n + 1)} = Y ⁽ⁿ⁾ (2-X · Y ⁽ⁿ⁾ · · (i) = {1 / X · (1 + ε ⁽ⁿ⁾ )} [2-X {1 / X · (1+
ε ⁽ⁿ⁾ }] = 1 / X · (1 + ε ⁽ⁿ⁾ ) {2- (1 + ε ⁽ⁿ⁾ } = 1 / X · (1 + ε ⁽ⁿ⁾ ) (1-ε ⁽ⁿ⁾ ) = 1 / X · {1- (ε ⁽ⁿ⁾ ) ² } = 1 / X (1 + ε ^{(n + 1)} ) ε ^{(n + 1)} =-(ε ⁽ⁿ⁾ ) ² and the error ε ⁽ⁿ⁾ is squared at each iteration. As a result, the value Y ^{(n + 1)} rapidly converges to the true value.

FIG. 6 shows a digital operation circuit for obtaining the reciprocal Y (= 1 / X) by the NR method.

That is, the digital value X is converted into the initial value Y ⁽⁰⁾ corresponding to the value X in the ROM (1), and this value Y ⁽⁰⁾ is supplied to the multiplication circuit (3) through the multiplexer (2) to obtain the value. The product X · Y ⁽ⁿ⁾ (n = 0 in this case) is calculated, and this product is supplied to the subtraction circuit (4) to calculate the difference (2-X) from the constant “2”.・ Y ⁽ⁿ⁾ ) is calculated.

Then, this difference is supplied to the multiplication circuit (5) and the ROM
The product with the value Y ⁽⁰ ) from (1), that is, Y ⁽ⁿ⁾ (2-X · Y ⁽ⁿ⁾ ) = Y ^{(n + 1)} However, in this case, n = 0 is calculated, This product Y ^{(n + 1)} is supplied to the register (6) and held until the next iterative calculation.

Then, after that, the multiplexer (2) is switched to a state opposite to that shown in the figure, and during the (n + 1) th iteration calculation, the value Y ⁽ⁿ⁾ from the register (6 ⁾ is passed through the multiplexer (2) to the multiplication circuit (3). , (5).

Therefore, when the value Y ^{(n + 1)} is taken out from the multiplication circuit (3) and the number of repetitions n reaches a certain value,
The value Y ^{(n + 1)} is the reciprocal Y of the required precision.

[Problems to be solved by the invention]

However, since this arithmetic circuit requires two multiplication circuits (3) and (5), the overall circuit scale becomes large.

That is, assuming that the value X is i bits and the value Y ⁽ⁿ⁾ is j bits, the multiplication circuit (3) multiplies i bits and j bits, resulting in a word length of (i + j) bits. Since (5) performs multiplication with (i + j) bits and j bits, it requires a word length of (i + 2j) bits.

Then, for example, in floating point arithmetic, i = 24
Since it is about bits, the word lengths of the multiplication circuits (3) and (5) become very long, and as a result, the multiplication circuits (3) and (5)
As (5) becomes very large in scale, power consumption or heat generation also becomes considerably large.

The present invention is intended to solve such a problem.

[Means for solving problems]

 Now, when the equation (i) is transformed, it becomes as follows.

Y ^{(n + 1)} = Y ⁽ⁿ⁾ (2-X · Y ⁽ⁿ⁾ ) ··· (i) = 2Y ⁽ⁿ⁾ −X · (Y ⁽ⁿ⁾ ) ² = Y ⁽ⁿ⁾ −Y ^{(n )} (Y ⁽ⁿ⁾ · X−1) ··· (iii) Here, in the equation (iii), the first term on the right side is
The previous calculation result is shown, and the second term is the calculation result of this time,
Indicates the error from the previous calculation result or its correction amount.

On the other hand, since the equation (ii) is Y ⁽ⁿ⁾ = 1 / X · (1 + ε ⁽ⁿ⁾ ) (ii), the following equation holds.

Y ⁽ⁿ⁾ · X = 1 + ε ⁽ⁿ⁾ (iv) Then, in this equation (iv), if | ε ⁽ⁿ⁾ | <2- ^k , the left side of the equation (iv) is ε ^{( n) When} 0, And when ε ⁽ⁿ⁾ <0, Becomes That is, Therefore, it is understood that it is not necessary to obtain k bits from the high order, and the low order can be obtained from the kth place after the decimal point.

Further, when the equation (iv) is modified, Y ⁽ⁿ⁾ · X−1 = ε ⁽ⁿ⁾ ... (vi), which is also in the parentheses of the second term on the right side of the equation (iii), This equation (vi) is expressed as follows when ε ⁽ⁿ⁾ 0 And when ε ⁽ⁿ⁾ <0, Becomes That is, when expressed by a two's complement, Y ⁽ⁿ⁾ .X-1 = -S.2- ^k + P- _k- ^1.2-k-1 + P- _k-2.2
^-k-2 + ... (vii), so again there is no need to find k bits from the higher order,
It is only necessary to obtain the lower order from the kth place after the decimal point.

The present invention focuses on the above points and simplifies the multiplication circuit.

[Action]

 The word length of the multiplication circuit becomes short.

〔Example〕

In FIG. 1, an i-bit digital value X is supplied to a multiplication circuit (3) and is also supplied to a ROM (1) to be converted into a j-bit initial value Y ⁽⁰⁾ corresponding to the value X, This value Y ⁽⁰⁾ is supplied to the multiplication circuit (3) through the multiplexer (2), and the product of both input values is supplied from the multiplication circuit (3).
The lower (i + j−) of Y ⁽ⁿ⁾ · X (n = 0 in this case)
k) bits are taken out, this product is supplied to the adder circuit (7) and the constant “−1” is added, and the sum (Y ⁽ⁿ⁾ · X−1) of both input values is added from the adder circuit (7). Lower (i + j-
k) Bits are taken.

In this case, the multiplication circuit (3) will be described as an example later.
And the adder circuit (7) can be integrated into a sum-of-products circuit.

Then, the output value of the (i + j−k) bits of the adder circuit (7) is supplied to the multiplier circuit (5) and the ROM
The value Y ⁽⁰ ) from (1) is supplied to the multiplication circuit (5) through the multiplexer (2), and from the multiplication circuit (5) the product Y ⁽ⁿ⁾ (of less than (i + 2j−k) bits of both input values is obtained. Y ⁽ⁿ⁾ / X-
1) (n = 0 in this case) is taken out.

Then, this product is supplied to the subtraction circuit (4), and the j-bit initial value Y ⁽⁰⁾ from the ROM (1) is supplied to the subtraction circuit (4) through the multiplexer (2). ), The difference between both input values i bits, Y ^{(n + 1)} = Y ⁽ⁿ⁾ (2-Y ⁽ⁿ⁾ · X) ∵ (iii) Equation, However, in this case, n = 0 is extracted, This value Y ^{(n + 1)} is supplied to the register (6) and held until the next iterative calculation.

After that, the multiplexer (2) is switched to a state opposite to that shown in the figure, and the value Y ⁽ⁿ⁾ from the register (6 ⁾ is passed through the multiplexer (2) to the circuits (3) to It is supplied to (5).

Therefore, when the value Y ^{(n + 1)} is taken out from the subtraction circuit (4) and the number of repetitions n reaches a certain value,
The value Y ^{(n + 1)} is the reciprocal Y of the required precision.

Thus, the reciprocal Y of the value X is calculated. In this case,
In particular, according to the present invention, the reciprocal Y is obtained based on the equation (iii), and at this time, the second term on the right side of the equation (iii) is a decimal point as shown in the equations (v) and (vii). The k th
Since it is only necessary to obtain the lower bits from the order and it is not necessary to obtain the upper k bits, the multiplication circuit (3) needs to output only (i + j−k) bits for the number of input bits i, j. Therefore, the scale of the multiplication circuit (3) can be reduced, and power consumption and heat generation can be reduced.

Further, when carrying out multiplication in the multiplication circuit (3), it is possible to save the propagation time of the carry bit to the upper bits,
The processing speed of multiplication can be increased, and as a result, the operation speed of the entire reciprocal circuit can be increased.

Furthermore, the output word length of the multiplication circuit (3) is (i + j−k)
Since it becomes bits, the output word length of the multiplication circuit (5) is also reduced by k bits to (i + 2j-k) bits. Moreover, in this case, since the input value X is i bits, the number of effective bits of the output value Y ^{(n + 1)} is also i bits. Therefore, in practice, the multiplication of the lower bits of the multiplication circuit (5) is to some extent. Can be omitted,
That is, the output word length of the multiplication circuit (5) is (i + 2j-k)
The number of bits can be smaller than the number of bits. Therefore, the multiplication circuit (5) can also be downsized, power consumption and heat generation can be reduced, and the overall calculation speed can be improved.

FIG. 2 shows an example of the case where the NR method converges in one time, that is, the required accuracy is obtained when n = 0, when obtaining the reciprocal of the floating point.

However, in this example, the input value is 1 bit for the sign S, 7 bits for the exponent part EXP in 2's complement representation, 24 bits for the mantissa part MANT (i = 24), and is normalized to 1MANT <2. Its MSB shall be "1". The initial value Y ⁽⁰ ) by the ROM (1) is 13 bits (j = 13), its MSB is "1", and | ε ⁽⁰⁾ | <2 ^-12 (k = 12).

First, since the code S does not change even if the reciprocal operation is performed, it is taken out as it is.

Further, since the exponent part EXP is an operation based on 2's complement, it is sufficient to add -1 part to the input value EXP, and all bits of the input value EXP are inverted and “1” is added to LSB. .
However, when normalizing the mantissa part MANT, it is necessary to subtract “1” from the exponent part EXP, so the input value EXP is
All bits are inverted and taken out by the inverter (9).

Further, the process of obtaining the reciprocal of the mantissa MANT (= X) will be described with reference to FIG. In the figure, a horizontally long frame indicates a value in the middle of calculation or a calculation result of each circuit, and blanks are “0” or “1” according to the calculation.

That is, the input value X is 24 bits (i = 24), and 1
Normalized to X <2, the MSB is "1" (A in the figure).
Then, the upper 13 bits of this value X are taken out (B in the same figure), and these 13 bits are supplied to the ROM (1) to generate the initial value Y.
It is converted to ⁽⁰⁾ (C in the same figure).

In this case, since 1X <2, the MSB of the value Y ⁽⁰⁾ is "0", and the first decimal place is "1", so ROM (1)
MSB of the 13 bits input (= "1") is directly used as the first decimal place of the value Y ^(0), the value Y ⁽⁰⁾
MSB is set to “0”. In addition, this allows ROM (1)
Needs to input 12 bits and output 12 bits,
The capacity of ROM (1) is 12 bits x 2 ¹² addresses, and the value Y ⁽⁰⁾
Has a length of 13 bits (j = 13 below the decimal point).

And, since the required accuracy is obtained with n = 0,
The value Y ⁽⁰⁾ is supplied to the multiplication circuit (3), and the value X is supplied to the multiplication circuit (3) to extract the product Y ⁽⁰⁾ · X thereof.

FIG. 3D shows the state of this multiplication. In this figure, Ym (m = 1 to 13) is the number m after the decimal point of the value Y ⁽⁰⁾ .
The position bit is shown, and X · Ym shows the product of the bit Ym and the value X. Therefore, as the value Y ⁽⁰⁾ is multiplied by the lower bits, the value X · Ym shifts downward by one bit. Then, the products of the respective bits Y _{1 to} Y _{13 of} the value Y ⁽⁰⁾ and the value X are added to obtain the product Y ⁽⁰⁾ · X of the value Y ⁽⁰⁾ and X (E in the figure). .

However, in this case, as described in equation (v), the product Y ⁽⁰⁾
The upper k bits of X do not need to be calculated, and the kth to the lower bits below the decimal point, in this example, the 25th bits from the 12th to the lower bits (= i + j-k), which are shaded, are multiplied and output. It is taken out as U (E in the figure).

Then, this value U is supplied to the adder circuit (7), and a constant “−1” is supplied to the adder circuit (7) to calculate the sum of both inputs, that is, the value V represented by the equation (vii). (FIG. F). Note that this difference is also in this example,
Although the length is 25 bits, the multiplication circuit (3) omits the calculation of the upper k bits, so that the output of the addition circuit (7) has a decimal point position of k bits, that is, 12 bits.

Then, the added value V is supplied to the multiplication circuit (5) and the value Y ⁽⁰⁾ (Fig. C) is supplied to the multiplication circuit (5) to extract the product Y ⁽⁰⁾ · V. Be done.

FIG. 3G shows the state of the multiplication, and the values Y _{1 to} Y
₁₃ is the same as D in the same figure, and V · Ym represents the product of the bit Ym and the value V. Then, the products of these bits Y _{1 to} Y ₁₃ and the value V are added to obtain the product Y ⁽⁰⁾ · V (H in the same figure).

In this case, the value Y ⁽⁰⁾ is 13 bits, so the product Y ⁽⁰⁾ · V
Up to the upper 13 bits are valid, so the product Y
^{For (0)} · V, for example, the upper 17 bits are calculated and 14
The upper 13 bits rounded at the bit and shaded are taken out as the multiplication output W (= Y ⁽⁰⁾ · V) (H in the figure).

Then, the value W ⁽⁰⁾ is supplied to the subtraction circuit (4) while the value W is supplied to the subtraction circuit (4), and the difference between the two,
That is, the reciprocal Y is extracted with a length of 24 bits (I in the same figure).

FIG. 4 shows an example of the multiplication circuit (3). The AND circuit group (31) multiplies X.Ym, and the multiplication result is added by the addition circuit (32) to obtain the product U.

FIG. 5 shows an example of the multiplication circuit (5) and the addition circuit (4). Again, the AND circuit group (51) multiplies Ym · V, and the multiplication result and Ym are added to the addition circuit ( 52) is added and the reciprocal Y is taken out.

In the above description, when the division Z / X is performed, the output value Y ^{(n + 1)} of the subtraction circuit (4) may be multiplied by the value Z.

〔The invention's effect〕

According to the present invention, the reciprocal number Y is obtained based on the equation (iii), and at this time, the second term on the right side of the equation (iii) is calculated as shown in the equations (v) and (vii). k
Since it is only necessary to obtain the lower bits from the order and it is not necessary to obtain the upper k bits, the multiplication circuit (3) needs to output only (i + j−k) bits for the number of input bits i, J. Therefore, the scale of the multiplication circuit (3) can be reduced, and power consumption and heat generation can be reduced.

Further, when carrying out multiplication in the multiplication circuit (3), it is possible to save the propagation time of the carry bit to the upper bits,
The processing speed of multiplication can be increased, and as a result, the operation speed of the entire reciprocal circuit can be increased.

Furthermore, the output word length of the multiplication circuit (3) is (i + j−k)
Since it becomes bits, the output word length of the multiplication circuit (5) is also reduced by k bits to (i + 2j-k) bits. Moreover, in this case, since the input value X is i bits, the number of effective bits of the output value Y ^{(n + 1)} is also i bits. Therefore, in practice, the multiplication of the lower bits of the multiplication circuit (5) is to some extent. Can be omitted,
That is, the output word length of the multiplication circuit (5) is (i + 2j-k)
The number of bits can be smaller than the number of bits. Therefore, the multiplication circuit (5) can be reduced in scale, consumption power and heat generation can be reduced, and the overall calculation speed can be improved.

[Brief description of drawings]

1 and 2 are system diagrams of an example of the present invention, and FIGS. 3 to 6 are diagrams for explaining the same. (1) is a ROM, and (3) and (5) are multiplication circuits.

Claims (1)

(57) [Claims] 1. A reciprocal arithmetic circuit for calculating the reciprocal Y (= 1 / X) of an input value X by the Newton-Raphson method, wherein the i-bit input value X is converted into a j-bit initial value Y ⁽⁰⁾ . The ROM is multiplied by the i-bit input value X and the j-bit value Y ^(n), and the lower (i + j−k) -bit multiplication value is output.
A product-sum circuit that adds the (i + j-k) -bit multiplication value and -1 and outputs the (i + j-k) -bit addition value, and the (i + j-k) -bit addition value and the j-bit value. The value of the
A multiplication circuit that multiplies Y ⁽ⁿ⁾ and outputs a multiplication value of (i + 2j-k) bits or less, and a multiplication value of (i + 2j-k) bits or less and the j-bit value Y ⁽ⁿ⁾ And a subtraction circuit for performing subtraction and outputting the above-mentioned reciprocal Y of i bits.