JPH05334050A - Multiplier - Google Patents

Abstract

(57) [Summary] (Modified) [Purpose] To realize a multiplier with a numerical rounding function that does not require an adder separately. A multiplier 20 multiplies an 8 + 1-bit multiplicand X from x _-1 to x ₇ and an 8-bit multiplicand Y from y ₀ to y ₇ , and outputs a 16-bit multiplicand from z ₀ to z _15. It is a parallel type multiplier of 8 × 8 bit scale that outputs the product Z. 21
˜24 are shifters, 25-28 are adders, and each of the shifters has 3 bits (“x ₋₁ , x ₀ , x ₁ ”, “x ₁ , x ₂ , x _{3) of} the multiplicand consecutive from the lower order to the higher order. ...) for each multiplicand and multiplier (a _-1/0/1 , a _1/2/3 , ...)
..), and the adders function as a plurality of stages of adding means for shifting each partial product by 2 bits and sequentially adding them. A constant generator 29 generates a predetermined constant D, which is a binary number having a bit arrangement necessary for rounding a numerical value with respect to a product Z of multiplicands X and Y.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a digital parallel type multiplier for obtaining a product (Z) of a multiplicand (X) and a multiplier (Y).

[0002]

2. Description of the Related Art Conventionally, as a digital parallel type multiplier, for example, one having a circuit configuration based on a modified Booth algorithm is known. FIG. 4 is a conceptual block diagram showing the 8 + 1-bit multiplicand (X) from x _-1 to x ₇ and the 8-bit multiplicand (Y) from y ₀ to y _7.
This is an example of an 8 × 8-bit parallel type multiplier that multiplies and and outputs a 16-bit product (Z) from z ₀ to z ₁₅ .

The four shifters 10 to 13 are respectively
3 bits (“x_-1, X
₀, X₁"X₁, X₂, X₃"X₃, X_Four, X_Five"
"X _Five, X₆, X₇)), The partial product of the multiplicand and the multiplier
(A_-1/0/1, A_1/2/3, A_{3 / 4/5}, A_5/6/7,)Generate a
Functioning as a partial product generating means, and four adders
14 to 17 respectively shift each partial product by 2 bits.
Functions as a multi-stage addition means for adding and sequentially adding
It is a thing.

Here, the multiplicand X can be expressed by the following equation (1). However, the multiplicand X, the multiplier Y, and the product Z are all 2
It is assumed to be represented by the complement of.

[0005]

[Equation 1]

From the above equation (1), the product Z (Z = X × Y) can be expressed as follows.

[0007]

[Equation 2]

Here, a in equation (2)_iIs x_2i-1, X
_2i, X_{2i + 1}1 bit, that is, 3 consecutive bits of the multiplicand X
(Eg "x_-1, X₀, X₁"X₁, X₂, X₃"
"X ₃, X_Four, X_Five"X_Five, X₆, X₇))
It takes the values shown in Table 1 below, and Y and a_iMultiply by
Therefore, every 3 bits of the multiplicand X are divided by 1
Product (hereinafter a_-1/0/1, A_1/2/3, A_3/4/5, A_5/6/7)
Is generated.

Table 1 ======================================= x _2i-1 x _2i x _{2i + 1} a _i --------------------------------------- 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 2 1 1 0 0 -2 1 0 1 1 -1 1 1 1 0 -1 1 1 1 1 0 ========================== =============== The first adder 14 from the left adds 2 bits of the product Z by adding the partial product a _-1/0/1 and all zero (L level). z ₀ , z
₁ is generated and the remaining addition result is added to the second adder 1
5 to the second adder 15, the first adder 14
And the partial product a _1/2/3 are added to generate 2 bits z ₂ and z ₃ of the product Z, and the remaining addition result is given to the third adder 16. The third adder 16 adds the addition result of the second adder 15 and the partial product a _3/4/5 to generate 2 bits z ₄ and z ₅ of the product Z, and outputs the remaining addition result. The fourth adder is given to the fourth adder 17.
The addition result of the third adder 16 and the partial product a _5/6/7 are added to generate the remaining bits z _{6 to} z ₁₅ of the product Z. Note that x ₁ , x ₃ , x ₅ , and x ₇ are given to the adders 14 to 17 as carry inputs, respectively.

According to such a configuration, a partial product is generated by dividing one by 3 consecutive 3 bits of the multiplicand X, and each partial product is shifted by 2 bits for each adder to be added. For example, in the case of 8 × 8 bit parallel operation,
A 16-bit wide product Z can be generated.

[0011]

However, in such a conventional multiplier, a numerical rounding processing function for the product Z (processing for reducing the number of effective bits, corresponding to decimal rounding) is performed. When the rounding process is performed, the adder 18 is connected after the multiplier (multiplier of FIG. 4) as shown in FIG. It was necessary to add the binary number "D" having a different bit array and the product "Z".

Therefore, for example, if an 8 × 8 bit parallel multiplier is to have a numerical rounding function, in addition to at least four shifters 10-13 and four adders 14-17, an additional 1 is added. Since the number of adders 18 is required, the problem that the circuit scale increases and the additional adder 18
There is a problem that the speedup is hindered by the processing time of. [Purpose] Therefore, an object of the present invention is to realize a multiplier with a numerical rounding function that does not require an adder separately.

[0013]

The present invention achieves the above objects.
In order to generate_-1, X₀,
x ₁, X₂, X₃, X_Four, X_Five, …… ”
3 bits ("x_-1, X
₀, X₁"X₁, X₂, X₃"X₃, X_Four, X _Five"
......), the partial product (a_-1/0/1,
a_1/2/3, A_3/4/5, ...) to generate partial product generating means
And each partial product is shifted by 2 bits and added sequentially
A plurality of stages of addition means,
The first-stage addition means uses the least significant 3 bits (x
_-1, X₀, X₁) Corresponding to the partial product (a_-1/0/1) And predetermined
Of the predetermined constant
Is the number of bits needed for rounding the product of the multiplicand and the multiplier
Characterized by being a binary number having an array, preferably
Is the constant for rounding the number, the product of the multiplicand and the multiplier.
"Z₀, Z₁, Z₂, Z₃, Z_Four, Z_Five, Z₆, …… 」
And z of them₀~ Z_iCircle (i is 1, 2, ...)
When the number is lower, the i + 2th bit from the lower order is "1", etc.
Is a binary number with a bit array of "0"
Is characterized by.

[0014]

In the present invention, the numerical rounding process is executed inside the multiplier, and the product (Z) after the rounding process is output from the multiplier. Therefore, it is possible to realize a multiplier with a numerical rounding function that does not require an additional adder, and it is possible to solve the problems of the circuit scale and the operation speed described above.

[0015]

Embodiments of the present invention will be described below with reference to the drawings. 1 to 3 are diagrams showing an embodiment of a multiplier according to the present invention, which is an example of application to a multiplier having a circuit configuration based on a modified Booth algorithm. First, the principle configuration will be described. In FIG. 1, the multiplier 20 operates from x ₋₁ to x
8-bit multiplier 8 + 1 bit of the multiplicand to ₇ and (X) from y ₀ to y ₇ a (Y) by multiplying process, z from z ₀
It is a parallel type multiplier of 8 × 8 bit scale that outputs a 16-bit product (Z) up to ₁₅ .

Reference numerals 21 to 24 are shifters and 25 to 28 are adders.
And the shifters 21 to 24 are respectively from lower to higher.
3 bits of the multiplicand consecutive to (“x_-1, X₀, X₁"
"X ₁, X₂, X₃"X₃, X_Four, X_Five"X_Five, X
₆, X₇)), The partial product of the multiplicand and the multiplier
(A_-1/0/1, A_1/2/3, A_3/4/5, A_5/6/7,)Generate a
Functioning as a partial product generating means, and the adder 25 to
28 shifts each partial product by 2 bits
It functions as a multi-stage addition means that adds sequentially.
is there.

Here, 29 is a constant generator for generating a predetermined constant "D". The constant D is a binary number having a bit array necessary for rounding a numerical value for the product (Z) of the multiplicand (X) and the multiplier (Y), and the product of the multiplicand and the multiplier is represented by "z ₀ , z".
₁ , z ₂ , z ₃ , z ₄ , z ₅ , z ₆ , z ₇ , z ₈ ,
_{z 9, z 10, z 11} , z 12, z 13, z 14, z in case of the 16-bit ₁₅ ", is z _i (i from z ₀ of which 1,
When rounding up to 2, ...), i + 2 from the bottom
It is a binary code string having a bit array in which the 1st bit is "1" and the other bits are "0". For example, z _i = z ₄
Then, the code string is "0 to 0000100000 ₍₂₎ ".

"1" is given by connecting the i + 2th bit to the high potential side power source corresponding to the H level, for example, and "0" by connecting the other bits to the low potential side power source corresponding to the L level, for example. "give. According to such a configuration, the partial product a _−1/0/1 and the constant D are added by the adder 25 in the first stage, and the partial product a − is added by the adder 26 in the next stage.
_1/2/3 and the output of the first stage adder 25 are added, and further,
The partial product a _3/4/5 and the output of the adder 26 of the next stage are added by the adder 27 of the next stage and the adder 28 of the final stage is added.
The output of the partial product a _5/6/7 and the next subsequent stage of the adder 27 are added by.

Then, bit 0 (z ₀ ) and bit 1 (z ₁ ) of the product Z are taken out from the adder 25 at the first stage, and bit 2 (z ₂ ) and bit _{2 of the} product Z are obtained from the adder 26 at the next stage. 3 (z ₃ ) is taken out, bit 4 (z ₄ ) and bit 5 (z ₅ ) of the product Z are taken out from the adder 27 at the next stage, and the product Z of the product Z is taken out from the adder 28 at the last stage. the remaining bits (z ₆ ~z ₁₅₎ is taken out.

Here, since z ₀ , z ₁ , ... Z ₁₅ are values after adding a predetermined constant D, the constant D is set to, for example, “0”.
~ 0000100000 ₍₂₎ ", the lower 5 of the product Z
By truncating the bits (z _{0 to} z ₄ ), the number of effective bits can be reduced from z ₅ to z ₁₅ , and the product Z subjected to the rounding process can be obtained. Therefore, a dedicated adder for rounding processing (see reference numeral 18 in FIG. 5) can be dispensed with, multiplication with a numerical rounding function can be performed without increasing the circuit scale and preventing the processing time from increasing in speed. Can be realized.

FIG. 2 is a specific block diagram of the multiplier according to the present invention, where X is a multiplicand, Y is a multiplier, Z is a product, and 30 is a product.
Numerals 33 to 33 are shifters as partial product generating means, 34 to 37 are adders as adding means, and 38 is a constant generator. Four
The shifters 30 to 33 have the same configuration. For example, as shown in FIG. 3, the shifter 30 decodes a decoded signal corresponding to 3 consecutive bits (x _2i-1 , x _2i , x _{2i + 1} ) of the multiplicand X. A Booth decoder 30a for generating C ₀ and C ₁ , and a logic circuit 3 including an AND gate (AND), an OR gate (OR), and an exclusive OR gate (EX)
0b, and the AND gate stage or the OR gate stage of the logic circuit 30b executes any operation of x0, x1, and x2, that is, x | a _i |. The following Table 2 is a correspondence table of truth values and operations of the Booth decoder 30a.

Table 2 ============================================== ====== x _{2i + 1} x _2i x _2i-1 C ₀ C ₁ motion ------------------------------------------------- - 0 0 0 0 0 × 0 0 0 1 0 1 x 1 0 1 0 0 1 × 1 0 1 1 1 0 × 2 1 0 0 1 0 × 2 1 0 1 0 1 x 1 1 1 0 0 1 x 1 1 1 1 0 0 × 0 ============================================ ======== (C ₁ , C ₀ ) → In the case of “0, 0”, the outputs (d _{8 to} d ₀ ) of the OR gates are all “0”, and in this case × 0
Is executed. In the case of (C ₁ , C ₀ ) → “0, 1”, the output of the OR gate (d _{8 to} d ₀ ) is the multiplicand (x ₇ to
x ₀ ), where d ₈ is a copy of x ₇ and in this case x 1 is executed. (C ₁ , C ₀ ) →
In the case of "1, 0", the output of the OR gate (d ₈ ~
d ₀ ) is a value obtained by shifting the multiplicand (x _{7 to} x ₀ ) to the upper side by one bit, that is, d _i = x _{i + 1} , and in this case, x 2 is executed.

The exclusive or gate (EX) is
Complement is calculated when a _i has a negative sign. However, since this complement is a one's complement, the adder 34 of FIG.
The carry input of ~ 37 is connected to x _{2i + 1} . This is because when a _i has a negative sign, the value of x _{2i + 1} in each addition stage is “1”, and its value is “1” in the one's complement.
This is because it can be converted into a two's complement by adding.

The four adders 34 to 37 have the same structure.
Input of each stage adder (A₈~ A ₀) Corresponds to
Output of shifter (p₀~ P₇) That is, the multiplicand X
3 bits ("x_-1~ X₁"X₁~ X₃"X₃~ X
_FiveOr "x_Five~ X₇)) Gives the partial product corresponding to
Together with the output of each adder (S₈~ S₀)
It is shifted by 2 bits and input B (B₈
~ B₀) To give. However, to the input A of the first-stage adder 34
Is a predetermined constant D generated by the constant generator 38, that is,
"The bit allocation required for rounding the product of the multiplicand and the multiplier.
A binary number with columns ".

As described above, according to this embodiment, a constant having a bit arrangement in which only the i + 2th bit is "1" and the other bits are "0" in the first-stage adder constituting the multiplier. Since D is given, it is possible to perform the numerical rounding process on the product Z by simply cutting the bits z ₀ to z _i of the product Z, and a multiplier with a numerical rounding function that does not require an adder separately. Can be realized.

It is preferable that the i + 2th bit of the constant D can be switched to "1" or "0" according to a predetermined mode control signal because "0 rounding 1" can be turned on / off.

[0027]

According to the present invention, since the constant D necessary for rounding the numerical value is given to the adding means at the first stage, it is possible to realize a multiplier with a numerical rounding function which does not require an additional adder. ..

[Brief description of drawings]

FIG. 1 is a principle configuration diagram of an embodiment.

FIG. 2 is a block diagram of an embodiment.

FIG. 3 is a configuration diagram of a shifter according to an embodiment.

FIG. 4 is a configuration diagram of a conventional example.

FIG. 5 is a conventional configuration diagram in the case of performing a numerical rounding process.

[Explanation of symbols]

 D: predetermined constant 21 to 24: shifter (partial product generating means) 25 to 28: adder (adding means) 30 to 33: shifter (partial product generating means) 34 to 37: adder (adding means)

Claims (2)

[Claims] 1. The multiplicands from the lower side are "x _-1 , x ₀ , x ₁ ,
When the _{x 2, x 3, x 4} , x 5, ...... ", 3 bits of the multiplicand to be continuous from bottom to top (" x _-1, x _0, x
_{1 "and"} x _1, x _2, x ₃ "," x _3, x _4, x ₅ "...)
, The partial product of the multiplicand and the multiplier (a _-1/0/1 , a
_1/2/3 , a _3/4/5 , ...), and a plurality of stages of adding means for sequentially adding each partial product by shifting it by 2 bits. Of the adding means of the stages, the adding means of the first stage _forms a partial product (a _-1/0/1 ) corresponding to the least significant 3 bits (x _-1 , x ₀ , x ₁ ) of the multiplicand and a predetermined constant. Wherein the predetermined constant is a binary number having a bit array necessary for rounding a numerical value for a product of a multiplicand and a multiplier. 2. The constant for rounding the numerical value is obtained by multiplying the product of the multiplicand and the multiplier by "z ₀ , z ₁ , z ₂ , z ₃ , z ₄ , z ₅ ,
z ₆ , ..., Of which, z ₀ to z _i (i is 1,
When rounding 2, ...), 2 has a bit arrangement in which the i + 2th bit from the lower order is "1" and the other bits are "0".
The multiplier according to claim 1, wherein the multiplier is a base number.