JPH1011267A - Multiplier - Google Patents

Abstract

PROBLEM TO BE SOLVED: To make the circuit scale small without losing the quickness of a multiplier, and to reduce the power consumption of the multiplier for performing the multiplication of binary numbers by digitally outputting the product of digital multiplicand and multiplier using the complement expression of 2. SOLUTION: When the multiplier Y is the numerical data of 8 digits, in the algorithm of Booth, constitution can not be performed by three encoders 1-3 and three partial product generation control circuit 7-9. Therefore, the algorithm of the multiplication is changed. That is, in this multiplier for inputting the digital multiplicand X and multiplier Y using the complement expression of 2 and outputting the product X.Y of the multiplicand X and the multiplier Y, when the value of the order of 2<i> of the multiplier Y is indicated by yi (where i=0, 1...3n-1), y-1 is defined so 0, Z31 is obtained for each (i) (where i=0, 1...n-1) from Z31 =-4y31+2 +2y31+1 +y31 +y31-1 , the partial product X.Z31 is obtained from Z31 and the multiplicand X and further, the partial product X.Z31 is multiplied by 2<31> and a sum is obtained for (i).

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multiplier used for digital signal processing, and more particularly to a multiplier for digitally outputting a product XY of a digital multiplicand X and a multiplier Y using a two's complement representation.

[0002]

2. Description of the Related Art When numerical data is represented by a binary number, each digit is 0 or 1. For example, the multiplicand X and the number of digits are 2
Multiplication of the multiplier Y, which is n, results in creating 2n partial products at each digit of the multiplier Y and adding each of the partial products while shifting them.

Conventionally, the Booth algorithm has been known as a device for reducing the number of partial products to reduce the number of additions and simplify the circuit. As will be described in detail later, the algorithm of Booth considers a partial product in units of two bits adjacent to a certain digit, and performs a one-bit shift and a two's complement operation to reduce the number of partial products from 2n to n.
It is to reduce to individual.

A conventional constant multiplier using this Booth's algorithm will be described with reference to FIGS. FIG. 10 is a block diagram of a conventional constant multiplier for obtaining a product X · Y of a multiplicand X and a multiplier Y. Multiplier Y is 8 in binary
Digit data. The value of the 2nd power of the multiplier Y is y
_i (where i = 0, 1,... 7).

A multiplier Y is input to a multiplier 70. Numerical data of the multiplicand X is stored in a read-only storage device (hereinafter, referred to as “memory”) 71. By selecting the address input of the memory 71, one multiplicand X is selected from several constants stored in the memory 71. The numerical data output from the memory 71 is
Is input to

The main processing of the multiplier 70 will be described. Multiplier Y
The Dear values y _i is divided is input to the encoder 72 to 75. The signals S from the encoders 72 to 75 respectively
1, S2 and NG are output. The signals S1, S2, N
G will be described later. These signals S1, S2, NG
Is sent to the partial product generation control circuits 76 to 79. As described later, four partial products are generated by the partial product generation control circuits 76 to 79 using the signals S1, S2, NG and the numerical data output from the memory 71. The four partial products are added while being shifted by the adder 81. In order to perform addition at high speed, the adder 81 includes, for example, an addition tree and a parallel adder. It is separated into a digit and a carry by an addition tree and added one after another, and finally added by a parallel adder. Thus, the multiplication result 16 which is the product X · Y of the multiplicand X and the multiplier Y is output.

When obtaining four partial products from an 8-digit multiplier Y, the Booth's algorithm is used. Next, the algorithm of Booth will be described. Generally, the number of digits of the multiplier Y is 2n. It is assumed that both the multiplicand X and the multiplier Y use the two's complement representation. Regarding the multiplier Y, the value of the 2 i-th power is y _i (where,
i = 0, 1,... 2n-1). In particular, the ones place is y
It is ₀ . The most significant bit y _2n-1 is also called a sign bit.
Thus, the multiplier Y can be expressed by the following equation.

[0008]

(Equation 1)

Here, if y _-1 = 0 is defined, the following can be written.

[0010]

(Equation 2)

Here, assuming that Z _2i = −2y _{2i + 1} + y _2i + y _2i−1 , the product XY of the multiplicand X and the multiplier Y is expressed by the following equation.

[0012]

(Equation 3)

[0013] than the defining equation of Z _2i, Z _2i -2, -1,
It is one of 0, 1, and 2. The partial product X · Z _2i (where i = 0, 1,..., N−1) can be obtained by shifting the multiplicand X by one bit, performing a two's complement operation, and performing a zero-times operation. Partial product generation control circuits 76 to 7
9 can be easily configured. The number of partial products X · Z _2i is n, which is half the number of digits of the multiplier Y. The adder 81 converts the n partial products X · Z _2i into 2 ²ⁱ
Double and add. _{Multiplying the} partial product X · Z _3i by 2 ²ⁱ shifts the partial product X · Z _2i upward by 2i bits, so that it can be easily performed by the adder 81. In this way, the product XY of the multiplicand X and the multiplier Y is obtained.

FIG. 11 is a circuit diagram of the encoder 74 according to the above-mentioned Booth's algorithm. The encoder 74 converts the input y ₁ to y ₃ into a signal S, which is a calculation result of Z _2.
1. Convert to S2, NG. S1 is a signal that the absolute value of Z ₂ becomes 0 becomes 1, at other times when the 1. S
2 is a signal which becomes 1 when the absolute value of Z ₂ is 2, and becomes 0 otherwise. NG is a signal that becomes 1 when Z ₂ is a negative number and becomes 0 when Z ₂ is a positive number. However, when S1 and S2 are both a 0, NG may also be 1. Any 0, but for simplicity, next NG is 0 when all y ₁ ~y ₃ 0, when y ₁ ~y ₃ are all 1 NG is set to 1.

To realize this, an exclusive OR of y ₁ and y ₂ is calculated by an XOR gate 85, and y
The exclusive OR of ₂ and y ₃ is taken. The output of the XOR gate 85 is S1. Further, the output of the XOR gate 85 is NOT
The gate 88 takes a negation, and the output of the XOR gate 86 and A
The logical product is obtained by the ND gate 87. The output of the AND gate 87 is S2. In addition, y ₃ as it is the NG. Table 1 shows the truth table.

[0016]

[Table 1]

In FIG. 10, encoders 72 and 73 are the same circuits as the circuit shown in FIG. 11 except that the digit of the input numerical data is different. The encoder 75 is the same as the circuit shown in FIG. 11, but 0 is input to the least significant bit corresponding to y ₋₁ = 0. Thereby, the encoders 72 to
Signals S1, S2, and NG are output from 75 and sent to partial product generation control circuits 76 to 79.

The signal S is supplied to the partial product generation control circuits 76 to 79.
1, S2, NG, as well as multiplicand X from memory 71
Is also input. As shown in FIG. 12, the memory 71 stores r + 1-digit numerical data m _j (where j =
0, 1,... R). In particular, m ₀ is the least significant bit (LSB) and m _r is the most significant bit (MSB). Also, it is defined that m ₋₁ = 0. Note that the number of digits of the multiplicand X is r + 1. The partial product generation control circuits 76 to 79 convert the numerical data input from the memory 71 into signals S1, S2,
Using NG, a partial product X · Z _2i is generated.

The value of the j-th bit of the partial product X · Z _2i output from the partial product generation control circuits 76 to 79 is P _j (j = 0, 1,..., R + 1). The circuit shown in FIG. 13 is connected to each digit of the partial product generation control circuits 76 to 79. Each of the partial product generation control circuits 76 to 79 is provided with r + 2 circuits shown in FIG. 13 corresponding to the number of digits of the multiplicand X.

When S1 is 1, the AND gate 92 outputs m _j
Is output. On the other hand, when S2 is 1, the AND gate 93
Outputs m _j-1 . Outputs of the AND gates 92 and 93 are input to an OR gate 94. The OR gate 94 outputs m _j when S1 is 1, and outputs m _j-1 when S2 is 1. When S1 and S2 are both 0, the OR gate 94 outputs 0. Note that S1 and S2 do not become 1 at the same time.

S1 is the multiplicand X output from the memory 71
This is a signal when the numerical data is converted to a partial product without being shifted. When S1 is 1, the numerical data of the multiplicand X is output from the OR gate 94 as it is. On the other hand, S2 is a signal when the multiplicand X is doubled to be a partial product by shifting the numerical data upward by one bit. When S2 is 1, one bit lower bit m
_{When the} OR gate 94 outputs _j-1 , the multiplicand X
Is performed, and the multiplicand X is doubled. Thus, since there is a one-bit shift, the partial product X · Z _2i
Is 9 digits.

Further, the output of the OR gate 94 and the signal NG are exclusive-ORed by the XOR gate 95. This allows
P _j is output. NG is a signal which becomes 1 when Z _2i is a negative number as described above. When NG is 1, since taking the 2's complement, and P _j inverts the output of the OR gate 94. As will be described later, the final two's complement operation of adding 1 after inverting the bit is performed by the adder 81. on the other hand,
When NG is 0, the output of the OR gate 94 becomes _Pj as it is. Thus, the partial product generation control circuits 76 to 79 output the respective partial products.

When the multiplication result 16 is obtained by adding the partial products X · Z _2i by the adder 81, the multiplication result 16 is larger than the number of digits of the multiplier Y. Therefore, when the partial products X · Z _2i are added while shifting, the sign of each partial product X · Z _2i is extended and added. For example, if the multiplicand X and the multiplier Y are both 8
If it is a digit, its sign extension will be described with reference to FIG. In this case, the four partial products X · Z _2i are multiplied by 2 ²ⁱ and added. As shown in FIG. 14A, four partial products 100
〜１０103 are added while shifting by 2 bits.

The partial product 100 is a partial product output from the partial product generation control circuit 76 in FIG. Similarly, the partial products 101 to 103 are sequentially output from the partial product generation control circuit 7.
This is the partial product output from 7 to 79. Partial product 100 ~
103 has 9 digits as described above. In FIG. 14, the digits are aligned and displayed. NG1, NG3, NG
5, NG7 is 1 which is added to the partial products 100 to 103 in the two's complement operation as described above.

The bits representing the positive and negative signs of the partial products 100 to 103 are referred to as S ₁ , S ₃ , S ₅ , and S _{7 in} order from the upper side. Numerical data excluding the sign bits S ₁ , S ₃ , S ₅ , and S ₇ is indicated by P. By adding the four partial products 100 to 103 in this manner, a 16-digit multiplication result 16 (FIG. 10) is obtained. 16
In order to add by the digit, each of the sign bits S ₁ , S ₃ , S ₅ , and S ₇ is sign-extended to a region surrounded by a dotted line on the upper bit side. The addition of the sign bits S ₁ , S ₃ , S ₅ , and S ₇ is based on the sign bit S ₇ shown at 105.

[0026]

(Equation 4)

As a result, as shown in FIG.
What is necessary is just to add 1 to the inverted bits of the sign bits S ₁ , S ₃ , S ₅ , S ₇ and a predetermined digit. Thus, sign extension is simplified.

Further, the simplification of the sign extension can be shown in the drawings also by FIGS. 14 (a) and 14 (b). The sign bit S ₇ shown at 106 is converted into eight inverted bits of 1 and S ₇ shown at 107 in FIG. Similarly, the same conversion is performed on the sign bits S ₁ , S ₃ , and S ₅ . Then, since the addition of the portions of the strike-through lines 110 to 112 does not affect the addition of 16 digits, the addition does not have to be performed. Therefore, FIG.
As shown in FIG.

As described above, in FIG. 10, the partial products output from the partial product generation control circuits 76 to 79 are added to the adder 81.
, And the multiplication result 16 is output from the multiplier 70.

[0030]

However, since the number of encoders 72 to 75 and partial product generation control circuits 76 to 79 is still large, the circuit scale is large and the power consumption is large. Further, as the number of partial product generation control circuits 76 to 79 increases, the number of partial products increases. As a result, the adder 81 must perform a large number of additions, so that the circuit size of the adder 81 is also large. Therefore, the circuit scale has been further increased as a whole.

An object of the present invention is to solve the above-mentioned problems and to provide a multiplier for performing multiplication of a binary number, in which the circuit scale is reduced without losing the high speed of the multiplier and the power consumption is small. I do.

[0032]

According to a first aspect of the present invention, a digital multiplicand X and a multiplier Y using a two's complement representation are input, and a multiplicand X and a multiplier Y are provided. In the multiplier that outputs the product X · Y, the value of the 2 ⁱ -th place of the multiplier Y is y _i (i = 0, 1,... 3n−
When represented by 1), y _-1 is defined as 0. From Z _3i = −4y _{3i + 2} + 2y _{3i + 1} + y _3i + y _3i−1 , each i (where i = 0, 1,...) n-1) obtains the Z _3i for, from Z _3i and the multiplicand X, obtains a partial product X · Z _3i, further, the partial product X · Z _3i and 2 ³ⁱ times, i (although, i = 0, 1 .. N-1) are summed.

In such a configuration, the number of digits of the multiplier Y is 3n
It is. From the definition equation of Z _3i, n-number of Z _3i (where i =
0, 1,... N-1) are obtained. From Z _3i and the multiplicand X, a partial product X · Z _3i is obtained. At this time, Z _3i is -4, -3, -2, -1, 0, 1, 2, 3, 4 according to the definition formula.
Is one of the following values.

When Z _3i is 0, the partial product X · Z _3i is 0. When Z _3i is 2, the partial product X · Z _3i may shift the multiplicand X one bit higher. Multiplicand X when Z _3i is 4
May be shifted to the upper side by 2 bits. When Z _3i is 3, it is slightly complicated, but three times the multiplicand X is obtained. When Z _3i is a negative number or positive, a 2's complement operation is further performed on the partial product obtained as described above. Two's complement operation can be realized with a simple configuration.

As described above, n partial products X · Z _3i are obtained. When the partial product X · Z _3i is multiplied by 2 ³ⁱ and added, a multiplication result of the multiplicand X and the multiplier Y is obtained. ^Multiplying by 23i is only a bit shift, so it can be done easily. If a 1-bit shift, a 2-bit shift, and a process for obtaining a triple are provided, a 2's complement operation and a 0-fold operation are provided, the partial product X
・ Z _3i is n. Compared with the related art, the number of partial products X · Z _3i is reduced to one third of the number of digits of the multiplier Y. This allows
The addition of the partial products X · Z _3i is reduced, the circuit scale is reduced, and the power consumption is reduced.

In the second configuration of the present invention, the first
A storage device for storing a constant, storing numerical data of one and three times the multiplicand X in the storage device, and providing a means for determining whether the absolute value of Z _3i is 3; When the absolute value of Z _3i is 3, the storage device outputs numerical data that is three times the multiplicand X. On the other hand, when the absolute value of Z _3i is other than 3, the storage device outputs the numerical data that is one time the multiplicand X. And outputs the partial product X · Z using the numerical data.
I want _3i .

In such a configuration, the value of Z _3i is -4, -3, -2, -1, 0, 1, 2, 3, 4,
Is one of If Z _3i is 0, the partial product X · Z _3i
Is 0. If Z _3i is 1, the partial product X · Z _3i is numerical data that is one times the multiplicand X output from the storage device. When Z _3i is 2, the partial product X · Z _3i may be obtained by shifting the numerical data of one time the multiplicand X output from the storage device by one bit. When Z _3i is 4, the partial product X · Z _3i may be obtained by shifting numerical data that is one time the multiplicand X output from the storage device by 2 bits. When Z _3i is 3, the partial product X · Z _3i is numerical data that is three times the multiplicand X output from the storage device. In this way, when Z _3i is 3, numerical data three times as large as the multiplicand X is output from the storage device, so there is no need to perform complicated processing to triple the multiplicand X.

When Z _3i is a negative number such as -4, -3, -2, -1, Z _3i is 4, 3, 2, 1 and the partial product X · Z _3i obtained as described above. Operate two's complement. Thereby, even if Z _3i is a negative number, the partial product X · Z _3i is obtained. As described above, according to the present configuration, the partial product X · Z _3i can be obtained by _performing 1-bit shift, 2-bit shift, 2's complement operation, and 0-times operation.
The circuit scale and the power consumption are further reduced as compared with the configuration of FIG.

In the third configuration of the present invention, the first
A storage device for storing a constant is provided, and numerical data of -1 times, -3 times, 1 time and 3 times of the multiplicand X are stored in said storage device, and it is determined whether Z _3i is a negative number. And a means for determining whether the absolute value is 3 is provided. When Z _3i is -3, the storage device stores the multiplicand X
When Z _3i is 3, the storage device outputs numerical data that is three times the multiplicand X. When Z _3i is a positive number other than 3, the storage device outputs the multiplicand X. The storage device outputs numerical data of 1 time, and when Z _3i is a negative number other than -3, the storage device outputs numerical data of -1 times the multiplicand X, and obtains a partial product X · Z _3i by using the numerical data. Like that.

In such a configuration, the multiplicand X is stored in the storage device.
Numerical data of -1 times, -3 times, 1 time, and 3 times of are stored. As described above, when Z _3i is 2, 4, the partial product X
For Z _2i , it is sufficient to shift the numerical data of one time the multiplicand X output from the storage device by 1 bit or 2 bits, respectively. When Z _3i is −2 or −4, the numerical data of −1 times the multiplicand X output from the storage device is 1 for each.
Bits may be shifted upward by two bits. Z _3i is 3,
When −3, the partial product X · Z _3i is numerical data that is three times and −3 times the multiplicand X output from the storage device. Thus, when _{obtaining the} partial product X · Z _3i , it is not necessary to obtain three times the multiplicand X. In addition, two's complement operation is not required. As described above, although the amount of data stored in the storage device increases, the processing of the multiplier is simplified and the power consumption is further reduced.

In the fourth configuration of the present invention, the first
In any one of the above configurations to the third configuration, the multiplier Y of an arbitrary number of digits is sign-extended to obtain 2 ⁱ of the multiplier Y.
Is the value of the order y _i (where i = 0, 1,... 3n-1)
And the partial product X · Z _3i is obtained.

In such a configuration, even if the number of digits of the multiplier Y is not a multiple of 3, it can be represented by y _i by sign extension. Thus, in any of the first to third configurations, the product X of the multiplicand X and the multiplier Y
Y is obtained. Further, even if the sign extension is not actually performed, the same processing may be performed.

[0043]

BEST MODE FOR CARRYING OUT THE INVENTION

<First Embodiment> A first embodiment of the present invention will be described with reference to FIGS. FIG. 1 is a block diagram of a constant multiplier according to the present embodiment. In this embodiment, an 8-digit multiplier Y is input to the constant multiplier. The conventional constant multiplier described above (FIG. 1)
0), the number of encoders 1 to 3 and the number of partial product generation control circuits 7 to 9 are smaller. Multiplier Y is 8
In the case of digit numerical data, the above-mentioned Booth algorithm cannot be configured with three encoders 1 to 3 and three partial product generation control circuits 7 to 9. Therefore, in the present embodiment, the algorithm of multiplication is changed. First, the multiplication algorithm will be described.

In general, a multiplier, when given a multiplicand X and a multiplier Y, calculates a product X · Y. It is assumed that the multiplicand X and the multiplier Y both use the two's complement representation. The number of digits of the multiplier Y is 3n (where n is an integer).
If the number of digits of the multiplier Y is not a multiple of 3, sign extension is performed. Assuming that the value of the 1's place is y ₀ and the value of the 2's i-th place is y _i (where i = 0, 1,... 3n−1), the multiplier Y is represented by the following equation.

[0045]

(Equation 5)

Here, if y _-1 = 0, the following can be written.

[0047]

(Equation 6)

Here, assuming that Z _3i = −4y _{3i + 2} + 2y _{3i + 1} + y _3i + y _3i−1 , the product XY of the multiplicand X and the multiplier Y is expressed as follows.

[0049]

(Equation 7)

[0050] than the defining equation of Z _3i, Z _3i -4, -3, -
It takes any value of 2, -1, 0, 1, 2, 3, and 4.
In order to obtain the partial product X · Z _3i (where i = 0, 1,..., N−1), the multiplicand X and its 3
It suffices if there are double numerical data, 1-bit shift, 2-bit shift, 2's complement operation, and 0-fold operation. As a result, the number of partial products X · Z _2i generated is n, which is one third of the number of digits of the multiplier X.

By using this algorithm, the encoders 1-3 and the partial product generation control circuit 7 shown in FIG.
9 is smaller than that of the conventional constant multiplier (FIG. 10). FIG. 2 shows a circuit diagram of the encoder 2. The multipliers y ₂ to y ₅ are input. M3 outputted from the encoder 2 is a signal absolute value of Z ₃ becomes 0 becomes 1, at other times when the 3. S1 is 0 and becomes signal when the 1, and the other when the absolute value of Z ₃ is 1 or 3.

S2 becomes 1 when the absolute value of Z ₃ is 2,
Otherwise, it is a signal that becomes 0. S4 is a signal which becomes 1 when the absolute value of Z ₃ is 4, and becomes 0 otherwise. NG is 1 when Z ₃ is a negative number, and 0 when Z ₃ is a positive number.
This is the signal. When Z ₃ is 0, NG may be any value in theory, but in this embodiment, NG is 0 when y ₂ to y ₅ are all 0, and y ₂
When ~y ₅ are all 1 NG is set to be one of.

From the signals y _{2 to} y ₅ , the signals M3, S1, S2, S
4. To obtain NG output, use XOR gates 21 to 23
AND gates 24-26, NOT gates 27-29
Is provided. An XOR gate 21 takes an exclusive OR of y ₂ and y ₃ . Thereby, S1 is obtained. XOR
XORing y ₃ and y ₄ by the gate 22. From the output of the XOR gate 22 and the output of the XOR gate 21,
The result of negating the OT gate 27 is the AND gate 25
Is input to The signal output from the AND gate 25 is S2. XORing y ₄ and y ₅ in XOR gate 23. The output of XOR 23 and the output of XOR gate 21 are ANDed by AND gate 24. Thereby, M3 is obtained.

The output of the XOR gate 21 is negated by a NOT gate 28 and input to an AND gate 26. The output of the XOR gate 22 is negated by a NOT gate 29 and input to an AND gate 26. The output of the XOR gate 23 is also input to the AND gate 26. AND
The gate 26 outputs 1 when all the input signals are 1, and outputs 0 otherwise. As a result, the output of the AND gate 26 becomes S4. y ₅ is as it is signal NG
Becomes Table 2 shows the truth table.

[0055]

[Table 2]

In FIG. 1, the encoders 1 and 3 have the same configuration except that the digits of the input numerical data are different. However, in the encoder 3 y ₀ ~
Three bits of y ₂ are input, and 0 is input to the least significant bit corresponding to y ₋₁ = 0. Thereby, a configuration similar to that of the circuit diagram shown in FIG. 2 is obtained. Encoder 1 is also 3 bits of y ₅ ~y ₇ is input, by sign extension to the circuit shown in FIG. 2 may be 4-bit input. In addition, another circuit configuration is used so that an output equivalent to that is obtained.
It may be a bit input. Although a circuit diagram of the encoder 1 in the case of 3-bit input is not shown, it can be simply configured.

[0057] Since the encoder 1 input of 3-bit y ₅ ~y _7, M3 is 0, S4 also becomes zero. For simplicity, the encoder 1 does not send the signals M3 and S4 to the memory 4 and the partial product generation control circuit 7. The signal M3 output from the encoders 2 and 3 is input to the memories 5 and 6. By selecting the address input of the memories 4 to 6, the multiplicand X is selected from some stored constants. FIG.
As shown in (1), when M3 is 0, the memories 5 and 6 output numerical data that is one times the multiplicand X. When M3 is 1, the memories 5 and 6 output numerical data that is three times the multiplicand X. The output is m _j (where j = 0, 1,... R) in binary. Especially,
The value of the least significant bit (LSB) is m _0, the most significant bit (MSB) is m _r. Note that M3 is not input to the memory 4, and numerical data that is one times the multiplicand X is output.
Further, it is assumed that m ₋₁ = 0 and m ₋₂ = 0.

In partial product generation control circuits 7-9, memories 1-
3 are output as signals S1, S2, S4, NG
_{Are used} to generate partial products X · Z _3i . The value of the j-th bit of the partial product X · Z _3i output from the partial product generation control circuits 7 to 9 is represented by P _j (where j = 0, 1,... R +
1). Each digit of the partial product generation control circuits 7 to 9 is shown in FIG.
Is connected. Partial product generation control circuit 7
In addition, r + 2 circuits shown in FIG. 4 are connected in correspondence with the number of digits of the multiplicand X of each of .about.9.

When S1 is 1, the AND gate 31 outputs m _j
Is output. When S2 is 1, AND gate 32 outputs m
Output _j-1 . When S4 is 1, the AND gate 33 outputs _mj-2 . The output of AND gates 31-33 is O
Input to the R gate 34. In the OR gate 34, S1 is 1
Outputs m _j when, S2 outputs the m _j-1 when 1, S
When 4 is 1, m _j-2 is output. When S1, S2 and S4 are all 0, the OR gate 94 outputs 0.

S1 is a signal when the numerical data output from the memories 4 to 9 is used as a partial product without shifting. When S1 is 1, the numerical data from the OR gate 34 is output as it is. S2 is a signal used to shift the numerical data output from the memories 4 to 6 upward by one bit. When S2 is 1, _mj-1 corresponding to one lower bit is output. As a result, the numerical data output from the memories 4 to 6 is doubled. S4 is the memory 5,
This signal is used to shift the numerical data output from No. 6 upward by 2 bits. When S4 is 1, _mj-2 corresponding to the two lower bits is output. As a result, the numerical data output from the memories 5 and 6 is quadrupled by shifting to 2 bits higher.

Thereafter, the output of the OR gate 34 and NG are X
Are exclusive-ORed by OR gate 35, P _j is outputted. As described above, NG is a signal that becomes 1 when Z _3i is a negative number. When NG is 1, 2's complement is taken, so OR
The output of the gate 34 is inverted to _Pj . As will be described later, the final two's complement operation of adding 1 after bit inversion is performed by the adder 10. On the other hand, when NG is 0, O
The output of the R gate 34 becomes _Pj as it is. Adder 10
Then, the addition is performed while multiplying the partial product X · Z _3i by ²³ⁱ . In order to perform high-speed addition, the adder 10 includes, for example, an adder tree and a parallel adder. In this way, a multiplication result 16 is obtained.

As described above, when adding, the partial product X
_-Sign- extend _Z3i . This will be described with reference to FIG. The partial products 41 to 43 are partial products X · Z _3i output from the partial product generation control circuits 7 to 9. However, the multiplicand X has eight digits. And S _1, S _4, S ₇ the sign of the partial product 41 to 43 from the upper side. As described above, at the time of addition, as shown in FIG. 5A, the signs of S ₇ , S ₄ , and S ₁ are extended in the dotted line areas, respectively. At this time, the extension of the code is simplified as follows. Consider addition only for the symbols S ₇ , S ₄ and S ₁ .

[0063]

(Equation 8)

As a result, as shown in FIG.
_It suffices to add 1 to the inverted bits of ₁ , S ₄ and S ₇ and a predetermined digit. As described above, when drawing is obtained, FIG. 5B is obtained by using the inverted bit from FIG.
Erase the part. This can also be simplified as shown in FIG. Note that NG1, NG4, and NG7 are 1-bit signals NG output from the encoders 1, 2, and 3 that are added at the time of 2's complement operation when the partial products 41 to 43 are negative numbers.

As described above, in the present embodiment, as compared with the above-described conventional constant multiplier (FIG. 10), three encoders 1 are used.
-3 and three partial product generation control circuits 7-9,
The circuit scale of the constant multiplier is reduced. Further, since the number of partial products is reduced, the circuit scale of the adder 10 is also reduced.
As described above, since the entire circuit scale is reduced without losing the high speed, the power consumption is also reduced.

In the partial product generation control circuits 7 to 9, if the input multiplicand X can be tripled, the memories 4 to 6 can be omitted and the multiplicand X of an arbitrary variable can be input. However, at this time, the partial product generation control circuits 7 to 9 perform, for example, a 1-bit upper shift operation,
Further, by adding the original multiplicand X, 3 of the multiplicand X is calculated.
However, since the processing is complicated, the circuit scale is larger than that of the constant multiplier of FIG. Needless to say, the multiplicand X need not be eight digits. The number of digits of the multiplier Y can also be increased by using an appropriate code extension or an equivalent encoder.
Since the product X and Y can be obtained, any number of digits may be used.

<Second Embodiment> Next, a second embodiment of the present invention will be described with reference to FIGS. FIG. 6 is a block diagram of the present embodiment. The configuration is almost the same using the same algorithm as that of the first embodiment (FIG. 1) described above, except that NG signals output from encoders 1 to 3 are input to memories 4a to 6a. different. In FIG. 6, the same portions as those in FIG. 1 are denoted by the same reference numerals, and description thereof will be omitted.

The memories 5a and 6a have the same configuration.
Shown in M3 and NG are input to the memories 5a and 6a.
When M3 = 0 and NG = 0, the memories 5a and 6a output numerical data that is one times the multiplicand X. M3 = 0, NG
When = 1, the memories 5a and 6a output numerical data of -1 times the multiplicand X. When M3 = 1 and NG = 0,
Numerical data three times the multiplicand X is output from the memories 5a and 6a. When M3 = 1 and NG = 1, the memories 5a and 6
Numerical data of -3 times the multiplicand X is output from a.

Thus, numerical data m of r + 1 digits
_j (where j = 0, 1,... r) is the memory 5a, 6a
Output. Since M3 is 0 in the memory 4a, only NG is input. Along with this, the memory 4a stores numerical data that is 1 time and -1 time the multiplicand X. In particular, the least significant bit (LSB) is m ₀ and the most significant bit (MSB) is M _r . Also, m ₋₁ = 0, m ₋₂ = 0
And As described above, the amount of data stored in the memories 4a to 6a is doubled as compared with the memories 4 to 6 of the first embodiment.

In the first embodiment, the circuit shown in FIG. 4 is used for the partial product generation control circuits 7 to 9. In the present embodiment, the circuit shown in FIG. 8 is used for the partial product generation control circuits 7a to 9a. In FIG. 8, the same portions as those in FIG. 4 are denoted by the same reference numerals, and description thereof will be omitted. In this embodiment, the signal NG is not input, and the XOR gate 35 (FIG. 4) is omitted. This is because, when Z _3i is a negative number, a negative number is output from the memories 4a to 6a, so that the two's complement operation is not required in the partial product generation control circuits 7a to 9a.

FIG. 9 shows the sign extension when adding the partial products X · Z _3i . In FIG. 9, the same portions as those in FIG. 5 are denoted by the same reference numerals, and description thereof will be omitted. Partial product 41
The sign extension of .about.43 is the same as the sign extension of the first embodiment described above (see FIG. 5). However, in this embodiment, when the partial products 41 to 43 are negative numbers, they are already represented by two's complement. , NG1, NG4, and NG7 are not added.

In view of the circuit scale, the present embodiment has a larger storage capacity of the memories 4a to 6a than the first embodiment, and therefore has a larger circuit scale. However, from the viewpoint of power consumption, the power consumed by the XOR gate 35 (see FIG. 4) is greater than the power consumed by the memories 4a to 6a. Reduces power consumption.

[0073]

【The invention's effect】

<Effect of Claim 1> The number of partial products is reduced in the remainder circuit for calculating the product of the multiplier Y and the multiplicand X. This allows
The circuit size of the adder for obtaining the sum of the partial products can be reduced. The circuit scale of the multiplier can be reduced, and power consumption can be reduced.

<Effect of Claim 2> The storage device stores a multiplicand X of a constant and numerical data three times the multiplicand X. By using numerical data three times as large as the multiplicand X when obtaining the partial product, the processing is simplified when _{obtaining the} partial product X · Z _3i . Therefore, the circuit scale is further reduced. The overall circuit scale of the multiplier having the multiplicand X as a constant is reduced,
Power consumption is also reduced. Thus, the present invention is effective for a constant multiplier.

<Effect of Claim 3> Numerical data of -1 times, -3 times, 1 time and 3 times of the multiplicand X is stored in the storage device. Thus, when determining the partial product X · Z _3i ,
Only the operation of multiplying the multiplicand X by 0 and shifting by 1 bit and 2 bits are performed. In particular, the two's complement operation becomes unnecessary. Although the amount of data stored in the storage device increases, the processing is simplified. As a whole, power consumption is further reduced.

<Effect of Claim 4> Even if the number of digits of the multiplier Y is not a multiple of 3, the above multiplication can be performed by sign extension. As described above, the product XY of the multiplicand X and the multiplier Y can be obtained even when the multiplier Y has an arbitrary number of digits. Further, even if the sign extension is not directly performed, a process having an equivalent effect may be performed.

[Brief description of the drawings]

FIG. 1 is a block diagram of a constant multiplier according to a first embodiment of the present invention.

FIG. 2 is a circuit diagram of the encoder.

FIG. 3 is a block diagram of the memory.

FIG. 4 is a circuit diagram of each bit of the partial product generation control circuit.

FIG. 5 is a diagram illustrating sign extension of the partial product.

FIG. 6 is a block diagram of a constant multiplier according to a second embodiment of the present invention.

FIG. 7 is a block diagram of the memory.

FIG. 8 is a circuit diagram of each bit of the partial product generation control circuit.

FIG. 9 is a view for explaining sign extension of the partial product.

FIG. 10 is a block diagram of a conventional constant multiplier.

FIG. 11 is a circuit diagram of the encoder.

FIG. 12 is a block diagram of the memory.

FIG. 13 is a circuit diagram of each bit of the partial product generation control circuit.

FIG. 14 is a diagram illustrating sign extension of the partial product.

[Explanation of symbols]

1-3 encoder 4-6 memory 7-9 partial product generation control circuit 10 adder 35 XOR gate m _j numerical data

Claims (4)

[Claims] 1. A digital multiplicand X and a multiplier Y using a two's complement representation are input, and a product X · of the multiplicand X and the multiplier Y is input.
In the multiplier that outputs Y, the value of the order 2 ⁱ of the multiplier Y is y _i (where i = 0, 1,...)
3n-1), y _-1 is defined as 0, and from Z _3i = -4y _{3i + 2} + 2y _{3i + 1} + y _3i + y _3i-1 , each i (where i = 0, 1, · · n-1) obtains the Z _3i for, from Z _3i and the multiplicand X, obtains a partial product X · Z _3i, further, the partial product X · Z _3i and 2 ³ⁱ times, i (although, i = 0 , 1... N−1). 2. A storage device for storing a constant is provided. Numerical data of one and three times the multiplicand X is stored in the storage device, and means for determining whether the absolute value of Z _3i is 3 is provided. When the absolute value of Z _3i is 3, the storage device outputs numerical data that is three times the multiplicand X, while when the absolute value of Z _3i is other than 3, the storage device outputs the numerical value that is one time the multiplicand X. Data is output, and the partial product X · Z is
_3. The multiplier according to claim 1, wherein _3i is obtained. 3. A storage device for storing a constant is provided, and numerical data of -1 times, -3 times, 1 time, and 3 times of the multiplicand X are stored in the storage device, and it is determined whether Z _3i is a negative number. Means and means for determining whether the absolute value is 3 are provided. When Z _3i is -3, the storage device stores the multiplicand X
When Z _3i is 3, the storage device outputs numerical data that is three times the multiplicand X. When Z _3i is a positive number other than 3, the storage device outputs the multiplicand X. The storage device outputs numerical data of 1 time, and when Z _3i is a negative number other than -3, the storage device outputs numerical data of -1 times the multiplicand X, and obtains a partial product X · Z _3i by using the numerical data. The multiplier according to claim 1, wherein: 4. Sign-extending a multiplier Y of an arbitrary number of digits to change the value of the 2 ⁱ -th place of the multiplier Y to y _i (where i = 0,
1... 3n-1), the partial product X · Z
The multiplier according to any one of claims 1 to 3, wherein _3i is obtained.