JP3264280B2 - Multiplier - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Summary] The present invention relates to a multiplication device that divides an n-bit multiplier into a plurality of pieces when multiplying an n-bit multiplier by a multiplicand, performs a plurality of multiplications, and outputs a final multiplication result. An object of the present invention is to reduce the amount of hardware of a multiplication device that divides a bit multiplier into M pieces and outputs a final multiplication result by performing M multiplications, wherein an n-bit binary multiplicand and an n-bit binary multiplier are provided. When multiplying by n, the multiplier n bits is divided into M bits, and n bits and n / M
When a quotient n / M has a remainder 1, a multiplier is sequentially selected M times by a number of bits equal to the integer part of the quotient n / M from the lower order in a multiplication device that executes a bit multiplication M times to obtain a multiplication result. The multiplier selecting means does not select the multiplicand when the state of the most significant bit of the multiplier is 0, and multiplies when the state of the most significant bit of the multiplier is 1 according to the state of the most significant bit of the multiplier. The first of the M multiplications is the number of bits obtained by adding 1 to the integer part of n / M, and the second to M times are the multiplicands of the number of bits equal to the integer part of n / M. And a multiplicand selecting means for sequentially selecting from the lower bit side, and adding an output of the multiplicand selecting means to an upper part of a product of n bits of the multiplicand and an output of the multiplicand selecting means to obtain a partial multiplication result in each round. It is configured to have multiplication means.

[Industrial applications]

The present invention relates to a multiplication method, and more particularly, to a multiplication device that divides an n-bit multiplier into a plurality of pieces when multiplying an n-bit multiplier and a multiplicand, performs a plurality of multiplications, and outputs a final multiplication result. .

[Problems to be solved by conventional technology and invention]

In multiplying the n-bit binary multiplicand by the n-bit binary multiplier, the n-bit multiplier is divided into M pieces, and a part of the multiplicand of the n-bit multiplicand is multiplied by n / M bits to execute M times. Conventionally, multiplication of the multiplicand n bits and the number of bits obtained by rounding up the fractional part of the quotient n / M in the multiplier, regardless of whether n / M is divisible or has a remainder Multiplication was performed using a multiplier capable of performing the multiplication. For example, when a multiplication of 53 bits × 53 bits is divided into four and executed, the multiplication is performed using a multiplier capable of multiplying 53 bits × 14 bits.

Therefore, when the multiplication of 53 bits × 53 bits is executed in four times, the multiplier is apparently 56 bits, and the multiplication becomes redundant. In the case of realizing a multiplication device, this leads to an increase in the number of multiplication circuits, that is, the amount of hardware, and causes a problem in mounting.

Further, even when the quotient n / M bits are divisible, if the multiplication of n bits × n bits is executed in M times, n
In feeding back the partial product resulting from the multiplication of the bit × n / M bits, the sum output S of the partial products and the carry output C are fed back. At this time, the upper part of both the sum output S and the carry output C are not significant figures, but are code data for simply obtaining a code of a partial product and sign extension bits added to the code data. Code data for both output and
And the sign extension bits are fed back.

The sum output S and the carry output C thus fed back are added to another partial product by a multi-input adder to obtain a final multiplication result. The carry output C and the sum output S are input.
Therefore, when code data and sign extension bits are added to the upper part of both the carry output C and the sum output S and fed back, the number of input bits of the code data portion to the multi-input adder increases. In addition, there is a problem in that the hardware amount of the multi-input adding device and, consequently, the entire multiplying device increases.

An object of the present invention is to reduce the hardware amount of a multiplication device that divides an n-bit multiplier into M pieces and outputs a final multiplication result by M multiplications.

[Means for solving the problem]

FIG. 1 is a block diagram showing the principle of the present invention. FIG.
Is a block diagram of the principle of the first invention, that is, 2 bits of n bits.
Multiplier n when multiplying a base multiplicand by an n-bit binary multiplier
When a bit is divided into M bits and multiplication of n bits and n / M bits is performed M times to obtain a multiplication result, the quotient n / M is a remainder 1
FIG. 4 is a principle block diagram of a multiplication device when the multiplication device has the following.

In FIG. 1 (a), the multiplier selection means 2 is, for example, a selector, and sequentially selects the multiplier 1 M times from the lower order by the number of bits equal to the integer part of the quotient n / M. The multiplicand selecting means 4 is, for example, a selector. When the state of the most significant bit of the multiplier is 0, the multiplicand selecting means 4 does not select the multiplicand according to the state of the most significant bit of the multiplier. 1
In the case of, the first of the above-mentioned M multiplications by multiplicand 3 is
The remaining number of bits (M−M) is equal to the number of bits obtained by adding 1 to the integer part of n / M.
1) The number of times is sequentially selected from the lower bit side by the bit number equal to the integer part of n / M.

The multiplying means 5 adds the output of the multiplicand selecting means 4 to the upper part of the product of the n bits of the multiplicand 3 and the output of the multiplier selecting means 2 to obtain a partial multiplication result each time. This partial multiplication is repeated M times to obtain a final multiplication result.

FIG. 1 (b) is a principle block diagram of the second invention.
The figure shows a multiplication device when the quotient n / M has no remainder when the multiplication of n bits and the multiplicand n / M bits is performed M times in multiplication of n bits × n bits to obtain a multiplication result. It is a principle block diagram of. In the figure, a multiplier selecting means 6 sequentially selects a multiplier 1 M times in n / M bits from the lower order. Further, the multiplying means 7 obtains a partial multiplication result each time as a product of n bits of the multiplicand 3 and the output of the multiplier selecting means 6.

The code detecting means 8 is, for example, a multi-input adder and is provided inside the multiplying means 7. The sign output means 8 outputs the sum of partial products of n bits of the multiplicand 3 and the output of the multiplier selecting means 6 and the partial output from the carry output. Detect sign.

(Operation)

In FIG. 1 (a) showing the principle of the first invention, for example, when performing a multiplication of 53 bits × 53 bits, for example, at the time of the multiplication in FIG. Is selected from the lower side of the multiplicand, and the lower 14 bits of the multiplicand are added to the upper part of the product of the 53 bits of the multiplicand and the output of the multiplier selecting means 2, that is, the lower 13 bits of the multiplier. Is obtained.

In the second and subsequent multiplications, the 13 bits of the multiplicand are sequentially selected from the lower side, and the 13 bits are added to the upper part of the product of the 53 bits of the multiplicand and the output of the multiplier selecting means 2, that is, 13 bits. A multiplication result is obtained, and a final multiplication result is obtained using these.

In FIG. 1 (b) showing the principle of the second invention, n /
Multiplication is performed assuming that M has no remainder. The partial multiplication result in each round is obtained as the product of n bits of the multiplicand and n / M of the multiplier output from the multiplier selecting means 6. When the sum output and the carry output of each partial product are fed back for the next multiplication inside the multiplication means 7, the sign data of the sum output and the carry output are added, for example, to add the partial product. Is detected, the code detection result is inserted as code data of a partial product into only one of the sum output and the carry output, and the result after the insertion is fed back. That is, for example, when the detection result of the code detection means 8 is inserted into the code data of the sum output, the code data of the carry output is not fed back, and only the significant digit of the carry output is fed back.

In the above description, n / M does not have a remainder in the second invention for simplicity. However, when n / M has a remainder, that is, in the first invention, the second invention is also used. Can be applied.

As described above, in the present invention, even when the quotient n / M has a remainder 1, a multiplier for multiplying n bits of the multiplicand and the number of bits equal to the integer part of n / M of the multiplier is used, and Regardless of whether the quotient n / M has a surplus or not, the number of input bits of the code data portion in the multi-input adder to which the sum output and the carry output of the partial products are input is reduced.

〔Example〕

FIG. 2 is a block diagram showing the overall configuration of a multiplication device as an embodiment of the first invention. In the figure, a multiplier register 10
N bits of the multiplier (multiplier, MULTIPLIER) in
The number of bits equal to the integer part of the quotient n / M is sequentially selected four times by the selector 11 four times in units of 13 bits in the case of n = 53 bits, for example, and input to the multiplication gate 15 in the multiplier 14.

On the other hand, the multiplicand (multiple predicate, MULTIPLICAND) in the multiplicand register 12 does not select the multiplicand when the state of the most significant bit of the multiplier is 0 according to the state of the most significant bit of the multiplier, and also selects the most significant bit of the multiplier. When the state of a bit is 1, the whole is output to the multiplication gate 15, and at the same time, the selector
13, the number of bits obtained by adding 1 to the integer part of the quotient n / M at the time of the first multiplication, for example, 14 bits are selected when n = 53 bits, and at the time of the second to fourth multiplications 13 bits are sequentially selected from the lower side.

The product of the number of bits equal to the integer part of n / M of the multiplier selected by the selector 11 and the entire multiplicand is multiplied by the multiplication gate 15.
Is obtained as a partial product, and the output of the multiplication gate 15, the output of the selector 13, and the sum output S of the previous partial product and the digit are added in such a manner that a part of the multiplicand output from the selector 13 is added to the higher order of the partial product. The carry output C is added by a carry save adder (CSA) 16.

Further, the sum output S of each partial product, the carry output C, and the output of the spill adder 17 which is an adder for obtaining a carry from a digit that is not required at the time of addition as described later are CLA.
(Carry look-ahead adder) input to 18 and the final multiplication result
19 is required.

FIG. 3 is an explanatory diagram of the multiplication method in the first invention. The figure shows an example in which the multiplication is divided into four times, that is, executed in four cycles. By adding the bit strings of the outputs G1 to G7 of the multiplication gate in FIG. 2, a partial product in the current cycle can be obtained. In the next cycle, the carry gate output C and the sum output S as a result of the partial product of the multiplication in the previous cycle are added to the bit strings G1 to G7. By repeating such multiplication for four cycles, a final multiplication result is obtained.

In FIG. 3, in the first cycle, the carry output C and the sum output S of the partial product of the previous cycle are all empty.
In the second to fourth cycles, the upper 13 bits of these outputs are empty, and a sign (sign) and an extension bit are actually inserted. This insertion is carried out by a carry output C or a sum output as described later. S may be performed on one of the S, and a partial bit string of the multiplicand corresponding to the multiplication of the most significant bit of the multiplier is inserted into one of the empty portions.

This bit string is selected by the selector 13 shown in FIG. 2. In the first cycle, the least significant 14 bits of the multiplicand are selected and inserted in order of 13 bits from the lower side in the second to fourth cycles. In FIG. 3, the number of bits in the bit string in each cycle is 66 bits as a result of multiplication of 53 bits × 13 bits, and the number of bits is
13 bits are shifted and added.

FIG. 4 shows an embodiment of the selector 13 for selecting a multiplicand. In the figure, a selector 13 for selecting a multiplicand in a multiplicand register 12 includes an AND circuit 20 for selecting the 0th to 12th bits from the upper bit of the multiplicand, and an AND circuit 21 for selecting the 25th bit from the 13th bit. AND circuit for selecting the 26th bit to the 38th bit From the 22nd and 39th bit
An AND circuit 23 for selecting the 51st bit, an AND circuit 24 for selecting the 52nd least significant bit, and an OR circuit 25 to which the outputs of the AND circuits 20 to 23 are input. Then, in the first cycle, the outputs of the AND circuits 23 and 24 are selected, and in the second cycle, the AND circuit 22, and in the third cycle,
In the 21st and 4th cycles, 20 outputs are selected. The fourth
The AND circuit and the OR circuit in FIG. 7A are omitted for convenience of illustration, and for example, an AND gate whose output is 3 bits is actually configured as shown in FIG.

FIG. 5 is an explanatory diagram of an embodiment of multiplication of 9 bits × 9 bits. In the figure, the multiplication of 9 bits × 4 bits is 2
Is done many times. The multiplier is selected by 4 bits at a time from the lower side, and the control signals g ₁ , g ₂ , and
It is recoded in g _3. That is, these control signals are a control signal g ₁ for obtaining any of 0 times, +1 times, −2 times, or −1 times of the multiplicand based on the value of the lower 2 bits of the 4 bits of the multiplier, Control signal g ₂ for obtaining 0 times, +1 times, −2 times, or −1 times × 2 ² of the multiplicand based on the 3-bit value excluding the least significant bit of
0 times multiplicand based on the value of the most significant bit of the bit, or a control signal g ₃ for obtaining the 1-fold × 2 ^4, the output of the multiplier gate 15 by the multiplicand and the control signals G1~
G3 is obtained as shown in FIG. 5 (a), and these outputs are CS
The result is added by A (carry-save adder) 16 to obtain a 9-bit × 4-bit partial product.

In order to perform the multiplication of 9 bits × 8 bits, the above multiplication of 9 bits × 4 bits is performed twice. FIG. 5B shows the multiplication in the first cycle and the second cycle.
The carry output C and the sum output S as the outputs of the CSA 16 in FIG.
Are added to the bit strings of G1 to G3 in the next cycle.
G1 to G3 in the second cycle, carry output C, and sum output S are added to obtain a 9-bit × 8-bit multiplication result.

To find the product of the most significant bit of the multiplier and the multiplicand,
As shown in FIG. 5 (C), the multiplicand is divided into lower 5 bits and upper 4 bits, and the lower 5 bits are, for example, in the upper 5 bits of the carry output C in the first cycle.
The upper 4 bits are the upper 4 bits of the carry output in the second cycle.
By selecting and inserting the bits, these are added, and the multiplication result of the second cycle finally becomes a multiplication result of 9 × 9 bits.

FIG. 6 is an explanatory diagram of the operation of the spill adder 17 as an adder for obtaining a carry from a digit that becomes unnecessary in the next cycle in FIG. In the case of the above-described multiplication of 53 bits × 53 bits, the multiplication result is 106 bits, but in many cases, the required result is the upper 53 bits. In other words, the lower 53 bits become unnecessary, but when the upper 53 bits are obtained, it is natural to consider the carry from the lower.

In FIG. 3, 66 bits (53 ×
13 bits), the lower 13 bits are not required in the second cycle of addition. However, only carry is necessary, and 3
The same can be said for the fourth and fourth cycles. The spill adder is an adder for obtaining a carry from a digit that is no longer needed. The output of the spill adder in the current cycle is input to the carry input of the least significant digit in the next cycle as shown in FIG. Is done.

FIG. 7 is a comparison explanation of the number of gates of the multiple gates required in the conventional method in which a multiplier of 53 bits is selected by 14 bits and multiplication is performed, and in the method of the present invention in which 13 bits excluding the most significant 1 bit are selected. FIG. FIG. 3A is an explanatory diagram of the conventional system, in which the number of gates 3 for obtaining a control signal for G1 of +1 or -2 or -1 according to the contents of the least significant 2 bits of a 14-bit multiplier, and G2 Control of G8 based on the number of gates 4 × 6 for obtaining four control signals (excluding digit shift) +1, +2, -2 or -1 for G7 and the least significant bit of the multiplier The number of gates 1 for obtaining +1 as a signal is added, and the product 1484 of the addition result 28 and the number of bits 53 of the multiplicand is the number of gates required in the conventional method.

On the other hand, in the method (b) using the method of the present invention, +1 and −2 as control signals of G1 based on the contents of the least significant 2 bits are used.
Or, the number of gates for obtaining −1, the number of gates for obtaining control signals +1, +2, −2, −1 for G2 to G6, 4 ×
The product 1325 of the result 25 obtained by adding 5 and the number of gates 2 for obtaining the control signal +1 or +2 for G7 according to the contents of the most significant 2 bits and the number of bits 53 of the multiplicand is the required number of gates. Thus, 159 gates are reduced as compared with the conventional method.

FIG. 8 shows a comparison of the tree structure of the CSA 16 of FIG. 2 between the conventional system and the system of the present invention. (A) shows the conventional system, in which the carry output C and the sum output S of the partial product of the previous cycle are input in addition to the outputs G1 to G8 of the multiplication gate, so that the number of CSAs is 8 and the tree is 5 It becomes a step. On the other hand, in (b) showing the method of the present invention, since the output of the multiplication gate is seven from G1 to G7, there are seven CSAs and four trees. Since the CSA is configured with 12 gates per unit, the product of 66 bits and the 12 gates of the multiplication result of 53 bits x 13 bits is 792 gates, and this reduces the number of gates and the amount of hardware. Thus, speeding up of one CSA tree is realized.

FIG. 9 is a block diagram showing the overall configuration of a multiplier according to an embodiment of the second invention. FIG. 9 is compared with FIG. 2 for the first invention. FIG. 9 shows a selector 13 for selecting a multiplicand.
In that a sign detection circuit 26 for obtaining the sign of the partial product from the sign data of the carry output C as the output of the CSA 16 and the sign data of the sum output S is added.
Note that in FIG. 9, the following description will be made on the assumption that the n-bit multiplier and the multiplicand are divisible by the number of multiplications M.

FIG. 10 is an explanatory diagram of a multiplication method in each cycle in the second invention. In the figure, for example, 52 bits × 52
Bit multiplication is performed, and the 52-bit multiplier is divided into four 13 bits, and the multiplication of the 52-bit multiplicand with the 13-bit multiplier is repeated in each cycle. Then, the sign of the partial product, that is, the sign is detected by the sign data of the carry output C and the sum output S for the next cycle in each cycle, and the sign data is inserted above the carry output in FIG. Is returned and used in the next cycle.

FIG. 11 is a comparison diagram between the conventional system and the coded data feedback system of the second invention. FIG. 2A shows a conventional system, in which code data of a carry output C and a sum output S are both code-spread, and both of them are fed back. On the other hand, in the present invention, the sign of the partial product is detected by the sign detection circuit using the code data of the carry output C and the sum output S as shown in FIG. The result is inserted, for example, at the upper position of the carry output C and fed back.

FIG. 12 shows an embodiment of a feedback system for code data. FIG. 6A shows input data a, b, c, a carry gate output C and a sum output S of the addition result, and the carry output C and the sum output S as shown in FIG. 2 is returned as it is and added, whereas in (c) of the embodiment of the present invention, the carry output C and the sum output S
Are added to the sum output S and fed back as 1-bit string code data.

FIG. 13 is an explanatory diagram of an embodiment of the sign detection circuit 26 in FIG. The sign detection circuit 26 is a multi-input adder, and is characterized in that the data to be added is code data. In FIG. 3A, input data A, B and C
Are added by the CSA and the CLA, and the sign as the addition result is obtained. That is, the sign data of the input data A, B, and C are added as shown in FIG.

FIG. 14 is a general explanatory diagram of an embodiment of a feedback system for code data. Here, for the sake of simplicity, −Sa · 2 ³ + a ₁ · 2 ² + a ₂ · 2 ¹ + a ₃ −Sb · 2 ³ + b ₁ · 2 ² + b ₂ · 2 ¹ + b ₃ −Sc · 2 ³ + c ₁ · 2 ² + c Consider the case of adding ₂ · 2 ¹ + c ₃ . FIG. 9A shows the sum output code data X _S , as the output of the CSA, for three inputs to the CSA.
_XS , _XS , and the carry output sign data Y _S , Y _S , Y ₁ show a conventional method in which feedback is performed as it is, whereas (b) shows the sum output sign data and the carry output sign. The sum with the data is detected by the sine detection circuit and fed back as carry output sign data S ₃ , S ₂ , and S ₁ .

Where _{S 1 = X S Y 1 S} 2 = X S Y S (G S1) S 3 = X S Y and _{S (G SS + G S1 ·} P SS). Code data above S ₃ is _{S 4 = X S Y S (} G SS + G SS · P SS + G S1 · P SS · P SS) = X S Y S (G SS + G S1 · P SS) = S 3 becomes , it is the same as the S _3. (Sign extended) X _1, carry from the digit of _{Y 2 C 12 = G 12 +} G 23 · P 12 · G 3 P 23 ·
When adding P ₁₂ to the code data, the sign of the result _{S A1 = S 1 C 12 =} X S Y 1 C 12 S A2 = S 2 S 1 · C 12 = X S Y S G S1 P S1 · C 12 = X _S Y _S (G _S1 + P _S1 · C ₁₂ ) In the expression of S _A2 , G _S1 P _S1 · C ₁₂ is _{S A3 = S 3 S 2 ·} S 1 · C 12 = X S Y S (G SS + G S1 · P SS) {P SS + G S1 · P S1 · C 12} = X S Y S (G SS + G S1 · P _SS ) C ₁₂ · P _S1 · P _SS = X _S Y _S (G _SS + G _S1 · P _SS + P _SS · P _S1 · C ₁₂ ) Note that P _SS G _S1 · P in the second line of the expression of S _{A2. S1}・ C ₁₂
Is ▲ ▼ ・ G _S1・ P _S1・ C ₁₂ + P _SS・ ▲ ▼ ・ P _S1
・ C ₁₂ ＝ C ₁₂・ P _S1・ P _SS (∵G _S1・ P _S1 = 0, ▲ ▼ ・ P
_S1 = P _S1 ), and (G _SS + G _S1 · P _SS ) C ₁₂ · P _S1 · P _SS in the third row is (G _SS + G _S1 · P _SS ) · (▲ ▼ + ▲ ▼ + ▲)
▼) + ▲ ▼ ・ (▲ ▼ + ▲ ▼)
- is transformed with _{P SS · P S1 · C 12} = G SS + G S1 · P SS + P SS · P S1 · C 12.

Even in the normal method, sum output and carry output
Results in the case of C ₁₂ came in is the same. That is,
The sign of the result is S _A1 = X _S Y ₁ C ₁₂ S _A2 = X _S Y _S (G _S1 + C ₁₂ · P _S1 ) S _A3 = X _S Y _S (G _SS + G _S1 · P _SS + C ₁₂ · P _S1 · P _SS ) Therefore, the code data is 2 of (X _S , X _S , X _S ) (Y _S , Y _S , Y ₁ )
It is not necessary to feed back the bit string, and it is sufficient to feed back one bit string of S ₃ , S ₂ , and S ₁ .

FIG. 15 is an explanatory diagram of the gate reduction effect in the second invention. FIG. 1A is an explanatory diagram of the CSA tree of the conventional system. Although the input to the CSA 16 is 9 for the upper 13 bits, the sign data is converted into a 1-bit string by the sign detection circuit in the present invention. In addition, for example, the input of the upper 13 bits of the sum output becomes unnecessary and becomes eight inputs, and the number of CSAs becomes six as shown in FIG. C
Since each SA is composed of 12 gates, 13 bits × 12 gates = 156 gates can be reduced.

In the above description, both of n
Although the bit multiplier and the multiplicand are assumed to be divisible by the number of multiplications M, the first invention and the second invention can be naturally combined even when the remainder of n / M is 1.

〔The invention's effect〕

As described in detail above, according to the present invention, even when the quotient n / M of the bit number n of the multiplicand and the multiplier and the number of multiplications M has a remainder 1, the number of bits of the integer part of n / M × n The final multiplication result is obtained by repeating the bit multiplication M times, and the sign detection result of the partial product is inserted above any of the carry output and the sum output as a result of the partial product, and the result is fed back. This makes it possible to significantly reduce the amount of hardware, greatly contributing to cost reduction and solving problems in mounting.

[Brief description of the drawings]

1 (a) and 1 (b) are block diagrams showing the principle of the present invention, FIG. 2 is a block diagram showing an overall configuration of a multiplication device as an embodiment of the first invention, and FIG. 4 (a) and 4 (b) are circuit diagrams showing a configuration of an embodiment of a multiplicand selector, and FIGS. 5 (a) to 5 (c) are embodiments of multiplication of 9 bits × 9 bits. FIG. 6 is an explanatory diagram of the operation of the spill adder. FIGS. 7 (a) and 7 (b) are explanatory diagrams of the effect of reducing the number of multiple gates in the first invention, and FIGS. 8 (a) and (b). FIG. 9 is an explanatory diagram of a CSA reduction effect in the first invention, FIG. 9 is a block diagram showing an overall configuration of a multiplication device as an embodiment of the second invention, and FIG. 10 is an explanation of a multiplication method in the second invention. FIGS. 11 (a) and 11 (b) are explanatory diagrams of a code data feedback system in the second invention, and FIGS. 12 (a) to 12 (c). ) Is an explanatory diagram of an embodiment of a feedback system for code data, FIGS. 13A and 13B are explanatory diagrams of an embodiment of a sine detection circuit, and FIGS. 14A and 14B are feedback systems of a code data. FIGS. 15 (a) and 15 (b) are explanatory diagrams of the CSA reduction effect in the second invention. 1 ... multiplier, 2,6 ... multiplier selecting means, 3 ... multiplicand, 4 ... multiplicand selecting means, 5,7 ... multiplier means 8 ... sign detecting means, 11 ... multiplier selector, 13 ... multiplicand Selector, 16 CLA (carry-save adder), 18 CLA (carry-look-ahead adder).

──────────────────────────────────────────────────続 き Continued on front page (58) Field surveyed (Int.Cl. ⁷ , DB name) G06F 7/00

Claims (2)

(57) [Claims] When multiplying an n-bit binary multiplicand by an n-bit binary multiplier, the multiplication n bits is divided into M, and the multiplication of n bits and n / M bits is performed M times, and the multiplication result is obtained. A multiplier selecting means for sequentially selecting the multiplier M times from the lower order by a number of bits equal to the integer part of the quotient n / M when the quotient n / M has a remainder 1, and a state of the most significant bit of the multiplier When the state of the most significant bit of the multiplier is 0, the multiplicand is not selected, and when the state of the most significant bit of the multiplier is 1, the multiplicand is divided by the first of the M times of multiplication. One time is the number of bits obtained by adding 1 to the integer part of n / M, and the second to M times are the numbers of bits equal to the integer part of n / M. Means for selecting the multiplicand in the upper part of the product of n bits of the multiplicand and the output of the multiplier selecting means. Multiplier, characterized in that it comprises a multiplier means for adding the output of the stage to obtain a partial multiplication result in each time. 2. The multiplication of an n-bit binary multiplicand and an n-bit binary multiplier divides the n-bit multiplier into M pieces, executes n-bit and n / M-bit multiplications M times, and calculates the multiplication result. In the multiplying device to be obtained, when the quotient n / M has a remainder 1, a multiplier selecting means for sequentially selecting the multiplier M times from the lower order by the number of bits equal to the integer part of the quotient n / M, and the most significant bit of the multiplier Depending on the state, if the state of the most significant bit of the multiplier is 0, the multiplicand is not selected, and if the state of the most significant bit of the multiplier is 1, the multiplicand is multiplied by 1 in the M times. multiplicand selecting means for sequentially selecting from the lower bit side of the multiplicand any number of bits obtained by adding 1 to the integer part of n / M, and the second to M-th times the number of bits equal to the integer part of n / M, The output of the multiplicand selecting means is provided in the upper part of the product of n bits of the multiplicand and the output of the multiplier selecting means. And a multiplication means for obtaining partial multiplication results at each time by adding the sum output and the carry output of a partial product of n bits of the multiplicand and the output of the multiplier selection means. Code detection means for detecting the sign of the partial product, and when the sum output and the carry output are fed back, the detection result of the code detection means is applied to only one of the sum output and the carry output. A multiplication device that inserts as code data of a product and feeds back only the insertion result as code data.