JPH02300930A - Multiplication circuit - Google Patents

Abstract

PURPOSE:To improve a speed even if the number of digits increases by decoding a multiplier in the decoder of a tertiary booth and calculating a multiplied result in an operation using a redundancy binary expression based on the decoded result. CONSTITUTION:The circuit consists of the decoder 10 of the tertiary booth outputting the selection signal S of four bits from the multiplier Y, and an internal arithmetic circuit 20 executing an internal operation by using redun dancy binary (RB) expression. A shift selection circuit 22 inputs three kinds of data of a multiplicand X and + or -3X from a + or -3X generation circuit 21, generates six kinds of partial products of + or -X, + or -2X and + or -4X and selects one kind from nine kinds of partial products 0, + or -X to + or -4, which are obtained by adding '0' and + or -3X to said partial products by the selection signal S. An intermediate sum carry generation circuit 23 generates an intermediate sum and a carry, an RB addition circuit 24 adds the intermediate sum and the carry, and an RB/B conversion circuit 25 converts the output of the RB addition circuit 24 into binary (B) expression so as to output the multiplied result P. Thus, the addition speed can be improved irrespective of the number of digits.

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention uses redundant binary (Redundant binary) in the internal representation of operations.
The present invention relates to a multiplication circuit using an ant Binary (hereinafter referred to as RB) expression.

(Prior art) Conventionally, as a technology in this field,
3-690, ■Japanese Unexamined Patent Publication No. 60-163128, and ■``Fairchild First Data Book (
E^IRCHILD FAST DATA BOO)
J (1985) (US) 9, 4-63-4-65
There was something written in.

Conventionally, for example, a binary multiplication circuit multiplies each digit of the multiplier Y by the multiplicand X to obtain a nine-part product, and the sum of the partial products is taken as the product. Here, for multiplication of binary numbers including negative numbers, the negative number is represented by a sign and an absolute value and multiplied by the absolute value, or the negative number represented by the complement of the negative number is used as is and multiplied. Multiplication by a negative number expressed as a complement generally requires a circuit to correct the multiplication result, which slows down the multiplication speed. Therefore, as a means of realizing high-speed multiplication, Booth (Booth
The algorithm h) is known. Booth's algorithm is a method of multiplying negative numbers by complement representation without correction, and by dividing the multiplier Y into m(m)2) bit patterns and decoding them, the partial product number is reduced to approximately 1/( m-1). Among the Booth algorithms, the most basic quadratic (m=3>Booth) is
Apply the algorithm in Table 1.

Table 1 Quadratic Booth Algorithm In Table 1, the multipliers y2i+2. For example, if 'o, o, o' is applied to i in y2i+1°y2i, 3'
2, yl, y□, and their multiplier y2゜3
If we calculate the partial product of '1, 3'0 and the multiplicand X, we will obtain the calculation result 0 in the right column. Similarly, each partial product 0,
By determining X, 2X, -2X, -X, -X, and O, and taking the sum of their partial products, the multiplication result can be obtained. Here, each partial product can be easily found by simply shifting or inverting the sign of the multiplicand X.

In the above-mentioned document (2), the cubic Booth algorithm shown in Table 2 is applied in order to further increase the speed. As a result, the number of partial products (Booth) is reduced to about 2/3 of that of the quadratic Booth algorithm, and the number of addition stages of partial products can be further reduced.An example of its configuration is shown in FIG.

Table 2 cubic booth algorithm FIG. 2 is a block diagram of a conventional multiplication circuit.

This multiplication circuit includes a cubic Booth decoder 1 that decodes a multiplier Y and outputs a selection signal S, a ±3X generation circuit 2 that calculates ±3 times the multiplicand X, and an output of the ±3X generation circuit 2 and a multiplicand. It is comprised of a shift select circuit 3 that selects X using a selection signal S, and an adder circuit 4 that adds the outputs of the shift select circuit 3 and outputs a multiplier result P.

In the above configuration, when the multiplier Y and the multiplicand X are supplied, the tertiary Booth decoder 1 decodes the multiplier Y and provides the selection signal S to the shift select circuit 3. The ±3X generation circuit 2 inputs the multiplicand X, performs addition of (2X+X), generates ±3X, and supplies it to the shift select circuit 3. When the shift select circuit 3 generates a partial product,
Its partial product is 0. ±X, ±2X, ±3X, ±4X 9
The type is selected by the selection signal S. Here, among the nine types, seven types other than ±3X can be easily determined by the shift select circuit 3 by simply shifting or inverting the sign of the multiplicand X. On the other hand, ±3X is independent of the result of decoder 1,
Based on the addition result of (2X +
Partial products of x can be generated. Then, the sum of the partial products generated by the shift select circuit 3 is added by the adder circuit 4,
A multiplication result P is output from the adder circuit 4.

(Problem to be Solved by the Invention) However, in the circuit with the above configuration, the ±3X generation circuit 2
Since a carry occurs in the addition of the adder circuit 4, there is a problem that as the number of digits in the internal calculation increases, the time required for the carry increases, making it impossible to speed up the calculation. It was difficult.

The present invention provides a multiplication circuit that solves the problem of the prior art, which is that the calculation speed decreases as the number of digits increases.

<Means for Solving the Problems> In order to solve the above problems, the present invention uses a cubic Booth algorithm to multiply each digit of a multi-bit multiplier Y by a multi-bit multiplicand X to obtain a partial product. A multiplication circuit that uses the total sum of partial products as the product is configured as follows. That is, the multiplication circuit of the present invention includes at least a tertiary Booth decoder that soto-overlaps the multiplier Y with 1 and decodes it every 4 bits, and a 3rd order Booth decoder that decodes the multiplier Y every 4 bits.
A redundant binary expression that can take any of the three values (redundant binary expression -1, 0, 1 is hereinafter referred to as "T°゛,"0''°).

a ±3X generation circuit that calculates ±3 times the multiplicand X using the redundant binary
nt Binary, hereinafter referred to as rRBJ) expression, by selecting the output of the ±3X generation circuit and the multiplicand X by the output of the decoder, thereby generating a plurality of partial products; and the redundant binary expression. an intermediate sum carry generation circuit that generates an intermediate sum and carry of the plurality of partial products using The RB addition circuit and the result X-Y are 2
It is composed of a conversion circuit that converts into a binary (hereinafter referred to as "B") representation.

(Function) According to the present invention, since the multiplication circuit is configured as described above, the decoder has the function of decoding the multiplier Y using the cubic Booth algorithm and reducing the number of partial products. The ±3X generation circuit and shift select circuit have a B/RB conversion function and enable internal calculations using R8 representation. The shift select circuit generates partial products, the partial products are added by the intermediate sum carry generation circuit and the RB addition circuit, and the addition result is converted into B representation by the RB/B conversion circuit and output as a multiplication result. . The internal calculation using the R8 representation suppresses carry, improves the addition speed regardless of the number of digits, and further simplifies the circuit configuration. Therefore, the above problem can be solved.

(Embodiment) FIG. 1 is a block diagram of a multiplication circuit showing an embodiment of the present invention.

This multiplier circuit overlaps the multiplier Y by 1 bit and generates 4
Bit by bit is decoded and a 4-bit selection signal s (=s5
．． A tertiary Booth decoder 1 outputting S2, 31, So (where the appendix S represents a sign bit)
0 and an internal arithmetic circuit 20 that performs internal arithmetic operations using redundant binary (hereinafter referred to as -RB) representation.

The internal arithmetic circuit 20 has a ±3X generation circuit 21 that inputs the multiplicand X and a shift select circuit 22. On the output side of the shift select circuit 22, an intermediate sum carry generation circuit 23, an RB addition circuit 24, and a shift select circuit 22 are provided. RB/B conversion circuit 2
5 are connected in cascade.

The ±3X generation circuit 21 inputs the multiplicand X and generates (2X+X
This is a circuit that performs the addition of >, and also has a B/RB conversion function from B representation to R8 representation. The shift select circuit 22 inputs three types of data: multiplicand X and ±3X,
±X, ±2X.

Generate six types of partial products of ±4X, and add them to 0°±3X
Nine types of partial products including 0. ±X, ±2X.

This circuit selects one type from ±3X and ±4 using a selection signal S, and also has a B/RB conversion function.

The intermediate sum carry generation circuit 23 is a circuit that generates an intermediate sum and a carry from the output of the shift select circuit 22 according to the RB addition algorithm, and the RB addition circuit 24 is a circuit that adds the intermediate sum and carry. Also, R
The B/B conversion circuit 25 is a circuit that converts the output of the RB addition circuit 24 into B representation and outputs the multiplication result p (-x·Y).

FIG. 3 is a circuit diagram showing a configuration example of the decoder 10 in FIG. 1. This data button 10 has a multiplier y31+3Iy3
4-bit selection signal s from 1+2Iy31, 11y31
,,s2. s1. This is a circuit that generates an exclusive OR gate (hereinafter referred to as a FOR gate).
0 to 4, NAND gates (hereinafter referred to as NAND gates) >311 to 31-5, and OR gates (hereinafter referred to as OR gates).
It is composed of >32-4.32-2 gates.

Figures 4(a) and (b) show the ±3X generation circuit 2 in Figure 1.
FIG. 1 is a circuit diagram showing a configuration example of No. 1;

When an n-bit multiplicand Xi (i=1 to n) is input, the circuit of FIG. 4(a) is used only when i=n, and O<
When i<n, the circuit shown in FIG. 4(b) is used. ±3X
The generation circuit 21 includes one circuit shown in FIG.
It is composed of 2> circuits shown in FIG. 4(b). The circuit of FIG. 4(a) is constructed from multiplicands X, This circuit generates ±3X, and is composed of OR gates 40-1 to 40-3 and negative OR gates (hereinafter referred to as NOR gates) 41-1 to 41-3. Further, the circuit shown in FIG. 4(b) has multiplicands Xi, X1-1. This circuit generates partial products ±3Xi from X1-2, and is composed of NOR gates 42-1 to 42-3 and OR gates 43-1 and 43-2. Note that the symbol S appended to each partial score "±3X, 2 to ±3Xo, ±3Xi" represents a sign bit, and the symbol V represents a normal bit.

FIG. 5 is a circuit diagram of the select portion of the shift select circuit 22 in FIG. 1. This circuit includes inverters 50-1 to 50-8, logical logic gates (hereinafter referred to as AND gates), and
1-8, and N.

Using an 8-man power 1-output selection circuit consisting of R gates 52,
Nine types of partial products based on cubic Booth algorithm 0. ±
It has a function to select one type of Z from X, ±2X, ±3X, and ±4X.

FIG. 6 is a circuit diagram showing a configuration example of the intermediate sum carry generation circuit 23 in FIG. 1.

This circuit is provided with the number of partial products (9 types) x the number of bits, and the unit circuit is constructed from the summand aiL ai and the addends bi-1, bi, and the intermediate sum Si and carry C
It has the function of generating 1, and the NAND card +-60-1
60-5, OR gates 61-1 to 61-3, FOR gates 62-1, 62-2, and NOR gate 63.

FIG. 7 is a circuit diagram showing an example of the configuration of the RB adder circuit 24 in FIG. 1. This circuit is provided with the number of partial products (9 types) x the number of bits, and its unit circuit adds the intermediate sum Si and the signal 1/no C, and then calculates the multiplication result 2 in R8 expression. EOR gate 70 and NA
It is composed of ND gates 71-1 to 71-3.

FIG. 8 is a main circuit diagram showing an example of the configuration of the RB/B conversion circuit 25 in FIG. 1. This circuit is provided as many as the number of output bits, and its unit circuit is composed of an EOR gate 80 that generates a minuend Ci and a subtractive di from the multiplication result Zi in R8 expression.

Next, the operation will be explained.

The multiplier Y is input to the cubic Booth decoder 10, and the multiplicand X is ±3.
When input to the X generation circuit 21, the tertiary Booth decoder 10 converts the conventional tertiary Booth algorithm shown in Table 2 into a 4-bit selection signal s8 as shown in Table 3.
．． s2. s1. decode to so.

Table 3 (however, "-'° is indeterminate)" That is, as shown in the cubic Booth decoder truth table in Table 3, when the multipliers y3i+3 to y31 are input to the decoder 10 in FIG. y3i+3 to y31 are EOR gates 30-1 to 30-3 and NAND gates 31-1 to 3
1-5 and OR gate 32-1.

Logic is determined at 32-2, and selection signals S, .about.So are output and applied to the shift select circuit 22.

On the other hand, the ±3X generation circuit 21 inputs the multiplicand X and (
By performing the addition 2X+X>, ±3X is generated without particularly inverting the sign, and this is provided to the shift select circuit 22. Normal addition of B numbers (binary numbers) causes propagation of carry from the lower order, but by treating the multiplicand X, which is the input of this circuit, as an RB number (redundant binary number), the carry from the lower order is 1. Only digits are propagated, and addition is possible in a fixed time. Conversion from this complement representation to R8 representation is easy; only the most significant digit needs to be inverted, and the other digits can be left as they are. Moreover, as described in the above-mentioned document (■), the R8 expression is the binary xis, xiv(
=xi) as shown in Table 4, and the addition is performed according to the R8 expression addition algorithm shown in Table 5.

Table 5 In Table 5, for example, if one of the summands a and bi is "1" and the other is "0", the next lower digit ai-1, bi- 1 is positive (“0′° is considered positive), then the carry Ci and the intermediate sum Si are “°1.
T "°, and if at least one of them is negative, it is 0, 1".

Also, if one of the summand aH and the addend bi is "TII" and the other is "0'°, then the next lower digit a, b,
If both of are positive, the carry +-1+-1 C. and the intermediate sum Si are "0.T", and if at least one is negative, it is "1.1".

Using the above, the input multiplicand X can be handled as an R8 expression without specifically converting it into an R8 expression. Therefore, for example, if the multiplicand X is n bits (XH, i=1~
n), using the circuit in Figure 4(a) only when i=n,
When ○<inn, by using the circuit shown in FIG. 4(b) and encoding as shown in Table 6, ±3X can be found.

Table 6 ±3X3X generation truth table In this case, decoder 10 in Figure 3 and ±3X3X in Figure 4
As is clear from the generation 21, the maximum number of element stages for signal passage is three, and since ±3X generation can be performed at the same time as the tertiary booth decoding, ±3X can be efficiently generated, and it is sent to the shift select circuit 22. Given.

The shift select circuit 22 inputs the multiplicand X and ±3X, and selects nine types of partial products 0.
Among ±X, ±2X, ±3X, ±4X, -X, ±2X,
In the five types of ±4X, the multiplicand X is shifted at the input part of the shift select circuit 22, and the selection signal S3. S2. Sl,
It is obtained by selecting by So, and B/RB conversion is also performed at the same time. Such partial products ±X, ±2X, ±3
X, ±4X are selected by selection signals S, .about.So in the select portion of the shift select circuit 22 shown in FIG. Here, the partial product 0 means that the selection signal S is logic "
1'', the outputs of the AND gates 51-1 to 51-8 become logic II O11, so that the partial product 0 is selected.

The intermediate sum carry generation circuit 23 is a shift select circuit 2
The partial products selected in step 2 are divided into intermediate sum 5is1Siv and carry-C15,C according to the RB addition algorithm in Table 5.
Generate 1v. That is, in FIG. 6, the summand ai5. of the selected partial product. aiv.

When ai-1s and addends bis, biv, bi-1s are input, the intermediate sum Si5. S
1v and carry Cis, Civ are generated, which is RB
It is output to the adder circuit 24.

Table 7 Intermediate sum carry generation circuit truth table (however, "-" is undefined) In this intermediate sum carry generation circuit 23, R shown in Table 4 is
Since 8 representation is used, in the sign determination of the next lower digit in Table 5, the upper side of the next lower digit (x Hs >
Since it is only necessary to judge the number of elements, the number of elements can be reduced accordingly.

In the RB adder circuit 24, as shown in FIG.
- Input S., carry Cis, and Civ, add them according to the truth table shown in Table 8, and output the addition result Z-Z. to the RB/B conversion circuit 25Is' IV.

Table 8 Note that in the two combinations indicated by the symbol * in Table 8, a carry occurs, so the circuit of FIG. 7 is configured so that this does not exist.

The RB/B conversion circuit 25 inputs the addition results Zis and Ziv in FIG. Outputs the binary subtractive number di, which collects only the digits that exist. R
The B/B conversion is determined by ordinary subtraction between the minuend C. and the subtrahend d, as described in the above-mentioned document (2). Therefore, for example, if a carry lookahead type subtracter is used to subtract the minuend Ci and the subtrahend di, the result of the subtraction will be the product P of the multiplicand X and the multiplier Y.

In this embodiment, the decoder 10 uses the third-order Booth algorithm and the internal arithmetic circuit 20 uses the R8 expression, which has the following advantages.

(i) ±3X Generation The ±3X generation in 21 can be performed easily and quickly, and can be performed simultaneously with the tertiary Booth decoding, so that apparently no special time is required for the ±3X generation.

(ii) Even if the number of digits of multiplicand X and multiplier Y increases,
Speed-up can be achieved.

(iii) Since the cubic Booth algorithm is used, the number of partial products can be reduced.

(iv) Since the circuit configuration is relatively simple, it is easy to implement LSI or VLSI.

Note that the present invention is not limited to the illustrated embodiment, and may be modified in various ways, such as configuring each circuit in FIG. 1 with a circuit other than those in FIGS. 3 to 8 depending on the number of digits of the calculation to be processed. is possible.

(Effects of the Invention) As described in detail above, according to the present invention, the multiplier Y is decoded by the decoder using the cubic Booth algorithm, and based on the decoding result, the multiplication result is Therefore, the ±3X generation can be performed easily and quickly, and since it can be performed simultaneously with the tertiary Booth decoding, it appears that no time is required for the ±3X generation. Furthermore, effects such as speeding up even when the number of digits increases, reduction in the number of partial products, and easy implementation into LSI or VLSI due to the simple circuit configuration can be expected. Therefore, it can be applied to various high-speed calculations.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a multiplication circuit according to an embodiment of the present invention, FIG. 2 is a block diagram of a conventional multiplication circuit, FIG. 3 is a circuit diagram of a decoder in FIG. 1, and FIG. >, (b)
is a circuit diagram of the ±3X3X generation in Figure 1, Figure 5 is a circuit diagram of the main part of the shift select circuit in Figure 1, Figure 6 is a circuit diagram of the intermediate sum carry generation circuit in Figure 1, and Figure 6 is a circuit diagram of the intermediate sum carry generation circuit in Figure 1. Figure 7 is a circuit diagram of the RB adder circuit in Figure 1, and Figure 8 is a circuit diagram of the RB/RB adder circuit in Figure 1.
It is a principal part circuit diagram of a B conversion circuit. 10...Third booth decoder, 20...
...Internal calculation circuit, 21...±3X3X generation,
22...Shift select circuit, 23...
・Intermediate sum carry generation circuit, 24...RB addition circuit, 25...RB/B conversion circuit, S...
...Selection signal, X...Multiplicand, Y...
Multiplier, P... Multiplication result.

Claims (1)

[Claims] In a multiplication circuit that uses the cubic Booth algorithm to obtain partial products by multiplying each digit of a multi-bit multiplier Y by a multi-bit multiplicand X, and uses the sum of the partial products as a product. , uses a cubic Booth decoder that decodes the multiplier Y every 4 bits with a 1-bit overlap, and a redundant binary representation in which each digit can take one of three values -1, 0, or 1 during calculation. a ±3X generation circuit that calculates ±3 times the multiplicand X by using the redundant binary representation; and a plurality of partial products by selecting the output of the ±3X generation circuit and the multiplicand a shift select circuit that generates an intermediate sum and carry of the plurality of partial products using the redundant binary representation; and an intermediate sum carry generation circuit that uses the redundant binary representation to generate an intermediate sum and carry of the plurality of partial products. A multiplication circuit comprising: a redundant binary addition circuit that outputs a product X and Y by adding the outputs of the two; and a conversion circuit that converts the product X and Y into a binary representation.