JPH11126157A - Multiplication method and multiplication circuit - Google Patents

Abstract

(57) Abstract: A multiplication method and a multiplication circuit capable of shortening an operation time and omitting a selector are provided. A multiplication circuit using the Booth algorithm, wherein when multiplying a negative maximum value and a negative maximum value, a 2's complement correction bit or a least significant bit of the most significant partial product is set to 0, The result of adding the least significant bit of the other partial product and the 2's complement correction bit is set to 11 so as to suppress the value to a positive maximum value.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a multiplication method and a multiplication circuit using a Booth algorithm in a semiconductor integrated circuit.

[0002]

2. Description of the Related Art In a binary multiplication represented by a two's complement representation, a multiplier is i bits, a multiplicand is j bits,
When the product output is i + j-1 bits and both the multiplier and the multiplicand are negative maximum values, an overflow occurs in the product output. In order to avoid this, when both the multiplier and the multiplicand have the negative maximum values, it is necessary to round the product output to the positive maximum value. For example, in a fixed-point multiplier having a decimal point on the right side of the most significant bit, when the multiplier and multiplicand are both 8 bits and the product output is 15 bits, 1.000 0000 × 1.000 00
00 = 1.00 0000 0000 0000 ｛(-1) × (-1) =-
1｝, which indicates that overflow has occurred.

FIG. 14 is a block diagram of a conventional 8-bit × 8-bit multiplier with a limiter function. In FIG. 14, xs and xi (i is 6 to 0) are multiplicands X, ys and yj.
(J is 6 to 0) is a multiplier Y, pmn (m is 1 to 4, n is s)
Or 7 to 0) are partial products, cs, c13 to c00, s
s and s14 to s00 are intermediate sums, zs and z13 to z00 are product outputs, and a symbol with a line over it means inversion. Reference numeral 200 denotes a booth recorder for creating a Booth algorithm, 201 denotes a partial product block, 202 denotes a partial product addition process, 203 denotes an adder, 204 denotes an overflow detection circuit, and 205 denotes a selector.

In a multiplier using the Booth recorder 200, a partial product can take five values of 0, ± X, ± 2X. In the case of a binary number in a two's complement representation, 2X (twice the multiplicand X) may be obtained by shifting the multiplicand X one bit to the left. Further, in the case of negative multiples of -X and -2X, it is necessary to invert each bit and add 1 to the least significant bit (in the case of -2X, a shift operation is also required).

[0005] When performing addition in the partial product generation, the operation time of the partial product generation increases. Therefore, the operation of adding 1 when the partial product is a negative value is usually performed by a partial product addition process (W
Alliance Tree) 202. In this partial product generation stage, the partial product is divided into a partial product pmn and a two's complement correction bit ph. Since only a shift operation and an inversion operation are required in the partial product generation, a partial product can be obtained at high speed.

FIG. 9 shows the circuit of the booth recorder 200 in FIG. 14, FIG. 10 shows the partial product generation circuit of the partial product block 201, and FIG. 11 shows the lowest partial product generation circuit. FIG. 12 shows the complementation correction bits.
In FIG. 9 showing a booth recorder circuit, y2j-1,
y2j and y2j + 1 indicate three adjacent bits of the multiplier Y. 28 and 31 are inverter circuits, 29 is ExNO
R circuit, 32 is an ExOR circuit, 33 is a NAND circuit, 3
Reference numerals 0, 34, 35 and 36 are inverter circuits. nr
s, r2, and r1 are signals generated by the booth recorder circuit. When a partial product is generated using the booth recorder 200, it has been described that there are five possible values of the partial product, 0, ± X, ± 2X, where nrs is a positive / negative sign. 1 indicates that the partial product is positive, and 0 indicates that the partial product is negative. r2 indicates that the generated partial product takes twice (a value of ± 2X). r1 indicates that the generated partial product takes one time (any value of ± X).

In FIG. 10 showing a partial product generation circuit, x
i is one bit of the multiplicand X. 37 is an ExNOR circuit, 38 and 39 are AND circuits, and 40 is an OR circuit.
xh is used to perform a shift operation when the generated partial product takes ± 2X, and xh of the partial product generation circuit one higher order
l input. pmn represents one bit excluding the least significant part of the generated partial product.

In FIG. 11 showing the least significant generation circuit of the partial product, x0 is the least significant bit. 41 is an ExNOR circuit, 42 is an inverter circuit, 43 and 44 are AND circuits,
45 is an OR circuit. pm0 is the least significant bit of the partial product. In FIG. 12 showing the 2's complementation correction bit generation circuit of the partial product, phm is a 2's complementation correction bit of the partial product. 46 is an inverter circuit.

The number of partial products of each digit in FIG. 14 is 2, 1, 3, 2,... From the least significant digit. Therefore, the intermediate sum (addition result in Wallace Tree)
Cannot be obtained in order from the lowest order, so the adder (ADDE
R) 203 becomes inefficient. Therefore, FIG.
, The least significant bit (pm0, m is 1 to 4) and the correction bit (phm, m are 1) of the partial product
4) are added to generate pcm and plm (pcm is a carry bit, plm is the same bit, and m is 1 to 4). FIG. 13 shows the least significant partial product generation circuit (the circuit that adds the least significant part of the partial product and the 2's complement correction bit to obtain a partial product) in FIG. 15, that is, the LSB addition / partial product generation circuit of the partial product. 47 is an inverter circuit, 48 is Ex
NOR circuit, 49 is AND circuit, 50, 51, 53 are A
An ND circuit 52 is an OR circuit. The generated plm is p
l = x0 · r1, and pcm is pc = / nrs · / x
0 · r1 + / nrs · r2. In the formula, / means inversion. In the multiplier of FIG. 15, other circuits such as the booth recorder 200 and the partial product selector 205 are the same as those of the multiplier of FIG. FIG. 16 is a conceptual diagram showing a block diagram of the multiplier of FIG. 15 in another form so that multiplication can be easily understood.

[0010]

SUMMARY OF THE INVENTION In a conventional multiplication circuit,
The occurrence of overflow (when both the multiplier and the multiplicand are negative maximum values) is determined by the overflow detection circuit 204, and when an overflow occurs, the value is set to the positive maximum value by the selector 205 before the product output. The output was multiplied and output when the overflow did not occur.

However, there is a disadvantage that the operation time and the number of elements of the multiplication circuit are increased by the amount of the selector. SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to provide a multiplication method and a multiplication circuit that can shorten the operation time and omit the selector.

[0012]

A multiplication method according to claim 1 is a multiplication method using the Booth algorithm, wherein when multiplying a negative maximum value by a negative maximum value, the highest partial product is calculated. The 2's complement correction bit or the least significant bit is set to 0, and the result of adding the 2's complement correction bit to the least significant bit of the other partial product and the 2's complement correction bit is set to 11, so that the maximum value is suppressed to a positive maximum value. It is characterized by the following.

According to the first aspect of the present invention, when an overflow occurs, in the partial product generation of the multiplier using the Booth algorithm, all the highest partial products are output as "1". Here, only when an overflow occurs, the result of adding the 2's complementation correction bit of the most significant partial product to the 0's and the least significant bit of the partial product of the other digits to the 2's complementation correction bit, that is, plm, pcm (where m =
1, 2, 3,. . . Is set to 11, it is possible to provide a multiplier that outputs a positive maximum value without using a selector in the output section of the product and reducing the calculation time.

According to a second aspect of the present invention, there is provided a multiplication method using the Booth algorithm, wherein when a negative maximum value is multiplied by a negative maximum value, a 2's complement correction bit of a generated partial product is multiplied. Alternatively, the least significant bit is set to 0, and the (lowest +1) bit of the partial product is set to 1, thereby suppressing the maximum value to a positive value.

According to the multiplying method of the second aspect, the same effect as that of the first aspect is obtained. A multiplication circuit according to claim 3 is an LSB addition / partial product generation circuit of a partial product of the multiplication circuit using the Booth algorithm, wherein when multiplying a negative maximum value by a negative maximum value, the partial product An LSB addition / partial product generation circuit for a partial product configured so that the result of adding the lower-order bit and the two's complement correction bit is set to 11, and means for setting the two's complement correction bit to 0 are provided. is there.

According to the multiplying circuit of the third aspect, the same effect as that of the first aspect is obtained. The multiplying circuit according to claim 4 is a partial product generating circuit of the multiplying circuit using the Booth algorithm, and when multiplying a negative maximum value by a negative maximum value, the (lowest +1) bits of the partial product are added. It has a partial product generation circuit configured to be 1 and has means for setting the 2's complementation correction bit of the partial product to 0.

According to the multiplying circuit of the fourth aspect, the same effect as that of the first aspect is obtained.

[0018]

BEST MODE FOR CARRYING OUT THE INVENTION

(First Embodiment) A first embodiment of the present invention will be described with reference to FIGS. That is, the first embodiment is a multiplication method using the Booth algorithm. When multiplying a negative maximum value by a negative maximum value, the 2's complement correction bit of the highest partial product is set to 0. The result obtained by adding the least significant bit of the other partial product and the 2's complement correction bit is set to 11 so as to suppress the result to a positive maximum value.

FIG. 1 shows a partial product SB addition / partial product generation circuit, that is, a least significant bit generation circuit of a partial product (a circuit corresponding to FIG. 13 of a conventional example). In FIG. 1, nrs,
r2 and r1 are values output from the booth recorder circuit shown in FIG. When a partial product is generated using a booth recorder, the possible values of the partial product are 5 of 0, ± X, ± 2X.
It is on the street. Here, nrs represents a positive / negative sign. If 1, the partial product is positive, and if 0, the partial product is negative.
r2 indicates that the generated partial product takes twice (a value of ± 2X). r1 indicates that the generated partial product takes one time (any value of ± X). x
0 is the least significant bit of the multiplicand X. nflg is shown in FIG.
Is output from the overflow detection circuit 204, and indicates whether or not overflow occurs. In this example, it is normally 1 and becomes 0 when an overflow occurs. pl and pc are generated partial products, and add up the least significant bit of the partial product and the correction bit of 2's complement. That is, pl = x0 · r1 + / n
flg pc = (/ nrs + / nflg) ./ x0. (r1 + /
nflg) + / nrs · r2 / represents inversion. Further, xh is a partial product generated ± 2.
When X is taken, a shift operation is required. For this purpose, it leads to a partial product generation circuit for one upper bit, for example, the xl input in FIG.

1, 2 and 4 are ExNOR circuits and 3 is a NOR circuit.
Circuit, 5 is an inverter circuit, 6, 7, and 9 are AND circuits,
8 and 10 are OR circuits. The basic operation is equivalent to the least significant bit generation circuit of the partial product shown in FIG. The difference from the least significant bit generation circuit of the partial product in FIG. 13 is that when an overflow occurs, both the outputs pc and pl of the least significant bit generation circuit of the partial product become 1.

Here, reference is made to FIG. The way of assigning the symbols in FIG. 8 is the same as that in FIGS. 14 and 15 described in the section of the related art, so the explanation of the symbols will be omitted. FIG. 8 is a block diagram showing (negative maximum value) × (negative maximum value), that is, a state in which overflow occurs in an 8-bit multiplier for both the multiplicand x and the multiplier y. However, the intermediate sum S,
Since the value of C changes depending on the connection method of the Wallace tree, it is described as a symbol. When this overflow occurs, pl1 to p14 and pc1 to pc
With a circuit configuration in which 3 is set to 1 and pc4 is set to 0, the product has a positive maximum value.

Therefore, consider a multiplier as shown in FIG. FIG. 5 is a block diagram of a multiplier using the least significant bit addition / partial product generation circuit of the partial product shown in FIG. That is, the booth recorder 200, the partial product addition process 202, and the adder 203 have the same functions as those of the conventional example shown in FIG. The overflow detection circuit is shown in FIG. In FIG. 4, 23 to 27 are 4-input NOR circuits, of which N
One input of the OR circuits 23 and 26 is an inverted input. 27 is a 4-input NAND circuit.

In the partial product block 201 ', FIG.
, The least significant bit of the partial product and the two's complement correction bit are added simultaneously with the generation of the partial product, and p
lm (m is 1 to 3) and pcm (m is 1 to 3) are output. However, p40, p
h4 is output. In other words, regarding the uppermost partial product, unlike the multiplier shown in FIG. 14, the addition of the least significant bit of the partial product and the 2's complement correction bit is not performed simultaneously with the generation of the partial product.

The least significant bit p40 of the most significant partial product is shown in FIG.
FIG. 3 shows a circuit for generating the 2's complement correction bit ph4 of the uppermost partial product. The manner of assigning the symbols is the same as in FIG. Here, 11 is an ExNOR circuit, 16 is an ExOR circuit, 12 is an inverter circuit, 1
3 and 14 are AND circuits, and 15 is an OR circuit. The least significant bit generation circuit of the most significant partial product in FIG. 2 is the same as the conventional least significant bit generation circuit. 2 of the uppermost partial product in FIG.
The output ph4 of the complemented correction bit generation circuit is output 0 when an overflow occurs.

FIG. 6 shows the state of the partial product when the multiplier shown in FIG. 5 performs (negative maximum value) × (negative maximum value). From FIG. 6, it can be seen that the value is suppressed to the positive maximum value and no overflow occurs. According to the first embodiment, when an overflow occurs, in the partial product generation of the multiplier using the Booth algorithm, all the digits of the uppermost partial product become 1. Here, only when an overflow occurs, as a result of adding the 2's complement correction bit of the most significant partial product to 0 and the least significant bit of the partial product of other digits and the 2's complement correction bit, plm, By setting pcm (where m = 1, 2, 3,...) to 11, it is possible to provide a multiplier that outputs a positive maximum value without using a selector in the product output unit and shortening the operation time. .

Therefore, a selector at the output unit is not required to avoid overflow. The number of elements can be reduced. Further, by obtaining the value of the overflow determination flag at high speed, it is possible to provide a multiplier with a limiter function that does not increase the delay as compared with a multiplier in which overflow does not occur (there is no selector). (Second Embodiment) A second embodiment of the present invention will be described with reference to FIG. That is, the second embodiment is a multiplication method using the Booth algorithm, and when multiplying a negative maximum value and a negative maximum value, a two's complement correction bit or a minimum value of a generated partial product is used. The lower bit is set to 0 and the (lowest +1) bit of the partial product is set to 1 so as to suppress the value to a positive maximum value.

FIG. 7 shows a multiplier of the type shown in FIG. 14, that is, the least significant bit of the partial product and 2
Is a partial product (least significant +1) bit generation circuit used for generating a partial product of the (least significant +1) bit of the partial product in which the complemented correction bits of the partial product are not added. In FIG.
x1 is the (least significant +1) bit of the multiplicand X, pm1 (m =
1, 2,. . ) Is (the least significant + 1) bit of the generated partial product is 1. 17 and 19 are ExNOR circuits, 18 is an inverter circuit, 20 and 21 are AND circuits, and 22 is an OR circuit.
Circuit. Other symbols are the same as those in FIG.

In the second embodiment, the partial product generation circuit shown in FIG.
The two-complement correction bit generation circuit of FIG. 3 is used for ph1, ph2, ph3, and ph4 for 11, p21, and p31. As a result, the same effect as in the first embodiment can be obtained, so that a selector before the product output is not required.

(Other Embodiments) As an explanation of the above-described embodiment, an 8-bit × 8-bit multiplier is used to set the 2's complement correction bit of the uppermost partial product to 0 when overflow occurs. As described above, the occurrence of overflow can be suppressed. However, when an overflow occurs, either the most significant two's complement correction bit or the least significant bit of the most significant partial product may be set to “0”, so that the least significant bit of the most significant partial product is set to “0”. The same effect can be obtained by setting it to 0. The same can be said for the multipliers of other bits.

Further, the present invention can be applied to an arithmetic unit which performs multiplication and other operations simultaneously, such as a product-sum arithmetic unit.

[0031]

According to the multiplication method of the present invention, when an overflow occurs, the partial product generation of the multiplier using the Booth algorithm outputs all ones at the highest order. Here, only when an overflow occurs, the result of adding the 2's complement correction bit of the most significant partial product to 0 and the least significant bit of the partial product of another digit and the 2's complement correction bit is used. Accordingly, it is possible to provide a multiplier that outputs a positive maximum value without using a selector in the output section of the product and reducing the calculation time.

According to the multiplying method of the second aspect, the same effect as that of the first aspect is obtained. According to the multiplying circuit of the third aspect, the same effect as that of the first aspect is obtained. According to the multiplying circuit of the fourth aspect, the same effect as that of the first aspect is obtained.

[Brief description of the drawings]

FIG. 1 is an LSB (least significant bit) addition / partial product generation circuit diagram of a partial product according to a first embodiment of the present invention;

FIG. 2 shows the LS of the uppermost partial product in the first embodiment.
FIG. 3 is a circuit diagram of a B (least significant bit) generation circuit.

FIG. 3 is a circuit diagram of a 2's complement correction bit generation circuit of the most significant partial product in the first embodiment.

FIG. 4 is an overflow detection circuit diagram.

FIG. 5 is a multiplier block diagram according to the first embodiment.

FIG. 6 shows (negative maximum value) × in the first embodiment.
It is a multiplier block diagram in the case of (negative maximum value).

FIG. 7 shows LSB + 1 of a partial product in the second embodiment.
FIG. 9 is a diagram of a generation circuit of (lowest +1 bit).

FIG. 8 is a block diagram when an overflow of a conventional multiplier occurs.

FIG. 9 is a booth recorder circuit diagram.

FIG. 10 is a partial product generation circuit diagram.

FIG. 11 is a circuit diagram of a conventional least significant bit generation circuit for a partial product.

FIG. 12 is a circuit diagram of a two's complement correction bit generation circuit.

FIG. 13 is a circuit diagram of a conventional least significant bit addition / partial product generation circuit for a partial product.

FIG. 14 is a block diagram of a conventional 8-bit × 8-bit first multiplier.

FIG. 15 is a block diagram of a second multiplier of the conventional 8-bit × 8-bit multiplier.

16 is a conceptual diagram of the multiplier of FIG.

[Explanation of symbols]

1, 2, 4, 11, 17, 19, 29, 37, 41, 4
8 ExNOR circuit 3 NOR circuit 5, 12, 18, 28, 30, 31, 34, 35, 3
6, 42, 46, 47 ... Inverter circuits 6, 7, 9, 13, 14, 20, 21, 38, 39, 4
3, 44, 50, 51, 53 ... AND circuit 8, 10, 15, 22, 40, 45, 52 ... OR circuit 16, 32 ... ExOR circuit 23, 26 ... 4-input NOR circuit (1 input is inverted) 24 , 25 ... 4-input NOR circuit 27 ... 4-input NAND circuit 33 ... NAND circuit 49 ... AND circuit (input inversion)

Claims (4)

[Claims] 1. A multiplication method using the Booth algorithm, wherein when a negative maximum value is multiplied by a negative maximum value, a 2's complement correction bit or a least significant bit of a most significant partial product is set to 0. A multiplication method characterized in that a result obtained by adding the least significant bit of another partial product and a 2's complement correction bit is set to 11 so as to suppress the result to a positive maximum value. 2. A multiplication method using the Booth algorithm, wherein when a negative maximum value is multiplied by a negative maximum value, a 2's complement correction bit or a least significant bit of a generated partial product is set to 0. , Wherein the (lowest order + 1) bit of the partial product is set to 1 so as to suppress the partial product to a positive maximum value. 3. An LSB addition / partial product generation circuit for a partial product of a multiplication circuit using a Booth algorithm, wherein when multiplying a negative maximum value by a negative maximum value, the least significant bit of the partial product is equal to 2 A multiplication circuit having an LSB addition / partial product generation circuit for a partial product configured so that the result of adding the complementation correction bit of 2 is set to 11, and means for setting the 2's complementation correction bit to 0. 4. A partial product generation circuit of a multiplication circuit using a Booth algorithm, wherein when multiplying a negative maximum value by a negative maximum value, the (lowest + 1) bit of the partial product is set to 1. And a means for setting a 2's complement correction bit of the partial product to 0.