Multiplying Circuit

1. Technical Field of the Invention

The present invention relates to a multiplying circuit suitable for an integrated circuit on a semiconductor chip and, more particularly, to a high-speed multiplying circuit using the Booth's algorithm.

2. Description of the Prior Art

Generally, a multiplicand X, a multiplier Y and the product P (=X.multidot.Y) are defined by the following equations for the multiplication of 16 bits.times.16 bits: ##EQU1##

Usually, in order to construct a hardware circuit for a parallel multiplication of n bits.times.n bits, there are required an n.sup.2 number (e.g., 256 in the case of 16 bits) of logic blocks. Each block has an AND gate for generating partial product and a full adder for adding the partial products. Even if the "carry save adder (CSA)" system is adopted, the carry must be propagated through 2n (e.g., 32 in the case of 16 bits) blocks so that the speed of operation cannot be increased.

While, according to the multiplying circuit using the Booth's algorithm (as is disclosed in Japanese Patent Publication No. 57-1014), the operation speed becomes faster than that of the above-mentioned parallel multiplying circuit. In this circuit, the multiplier Y is divided into groups of three bits (of which one bit is overlapped between the preceding and succeeding groups), and each group is decoded by a decoder referring to a bit pattern of three bits. Thereafter any of partial products .+-.2X, .+-.X and 0 is produced in accordance with the decoded results for each group. A total sum is obtained by accumulating all of the produced partial products.

The Booth's algorithm is featured by the facts that the partial product producing means can be reduced, since the concept of 2's complement can be introduced into the partial products, and that no correction of a sign bit is required for the multiplications, as is well known in the art. According to the Booth's algorithm, since a plurality of bits of the multiplier are simultaneously decoded, high-speed multiplication can be obtained.

In a high-grade digital computation or a complex calculation, however, it is required to multiply data of long bit lengths by each other. Especially in a 16 or 32 bits microprocessor with a high-performance, it is predicted that higher-speed and more precise computations will be required. In order to satisfy these requirements, it is conceivable to increase the number of bits of the group to be decoded for reducing the number of partial product producing steps. For example, 4 or more bits of the multiplier may be decoded at the same time. In this case, however, if a group of 4 bits are decoded, it is necessary to generate partial products corresponding to .+-.4X, .+-.3X, .+-.2X, .+-.X and 0 for the multiplicand X in accordance with the decoded results of 4 bits. Table 1 shows the partial products in the 4-bit decoder (wherein: y.sub.3i-2 to y.sub.3i+1 designate 4-bit patterns of the multiplier to be decoded; and P.sub.p designates the partial products).

Now, upon producing of the partial products .+-.4X, .+-.3X, .+-.2X, .+-.X and 0, respectively, the partial products .+-.4X and .+-.2X, i.e., even number multiplication of the multiplicand X can be generated easily by shifting the multiplicand X two bits and one bit, respectively, by means of shift operations. However, to produce the partial product .+-.3X, the multiplicand X has to be multiplied an odd number of times. This operation cannot be accomplished at high speed by the simple multiplying circuits proposed in the prior art. For a 4th-order Booth's algorithm, moreover, the partial products .+-.8X, .+-.7X, - - - , .+-.X and 0 are required, but the partial products produced with an odd multiplier (.+-.7X, .+-.5X and .+-.3X except .+-.X) cannot be easily produced. If it is possible, a long period of time must be spent to produce the partial products 7X, 5X and 3X. Further, even if the partial products 7X, 5X and 3X can be produced by a conventional multiplying circuit, since this production has to be performed after the decoding operation is terminated, a high-speed operation is very hard to achieve.

In addition, hardware elements for producing both the partial products of odd multipliers and even multipliers is required in each block for producing a partial product. Therefore, since the circuit pattern of each block becomes complex, the design of the multiplication circuit is very difficult. Moreover, it will be also difficult to integrate the circuit on a single semiconductor chip. Particularly, in an integrated circuit on a chip, it is important to align the same pattern in an array shape to make the LSI technology easy.

An object of the present invention is to provide a multiplying circuit which can execute multiplications at a high speed by a simple hardware circuit.

Another object of the present invention is to provide a multiplying circuit which can perform a multiplying operation in accordance with a decoding operation of 4 or more bits on the basis of the Booth's algorithm.

Still another object of the present invention is to provide a multiplying circuit which can be formed with a simple circuit pattern on a single semiconductor chip.

A multiplying circuit of the present invention comprises first input means receiving a multiplicand X composed of a plurality of bits, second input means receiving a multiplier Y composed of a plurality of bits, decoding means coupled to the second input means for decoding the multiplier Y and for generating at least a first signal designating a first partial product corresponding to the multiplication of the multiplicand X by an even multiplier and a second signal designating a second partial product corresponding to the multiplication of the multiplicand X by an odd multiplier according to the decoding operation, first means for producing the first partial product when said first signal is generated from the decoding means as the result of the decoding operation, second means for producing the second partial product regardless of the decoding operation, third means for selecting the produced second partial product according to the decoding result, and fourth means for producing a product by using the first partial product and the selected second partial product.

The most important feature of the present invention is the second means for producing the second partial product of an odd multiplier and the multiplicand X, for example 3X, 5X, or the like. The second means necessarily produces the second partial product according to the received multiplicand X regardless of the decoding operation. Namely, the second partial product is produced at the same time as the decoding operation is performed, and is only used when as the result of the decoding operation the decoding means generates the second signal designating the second partial product corresponding to the multiplication of the multiplicand X by an odd multiplier.

On the other hand, the production of the first partial product is started after the decoding operation is terminated. However, since the first partial product is easily obtained by a simple shifting operation, the first means can be constructed with a simple circuit element.

According to the present invention, first means for producing first partial products with even multipliers and second means for producing second partial products with odd multipliers are provided independently of each other, and specially the second partial products are produced at the same time when the decoding operation is performed or before the decoding operation is performed. As the result, it is possible to execute at a high speed the multiplying algorithm which requires the partial products of odd multipliers such as .+-.3X. Moreover, in the case where the second means is connected with the second input means of the multiplicand so that the data of odd multipliers are generated in advance in response to the input X, and whether those data are used or not is determined in accordance with the decoded results so that the multiplications can be executed in a hardware circuit without any aid of software, whereby it is possible to provide a very high-speed multiplier.

FIG. 1 is a block diagram of a multiplying circuit according to an embodiment of the present invention;

FIG. 2 is an example of a decoding circuit 3 in FIG. 1;

FIG. 3 is an example of a 3X producing circuit 1 in FIG. 1;

FIG. 4 is an example of a first group of a shift/selector circuit 2 in FIG. 1;

FIG. 5 is an example of a second group of the shift/selector circuit 2 in FIG. 1; and

FIG. 6 is an example of adder circuits 4 and 4' in FIG. 1.

First of all, the principle of the present invention will be described in the following.

The product P (=X.multidot.Y) of the unsigned magnitude data (i.e., the multiplicand X and the multiplier Y) of the 16 bits is generally defined by the equations (1) to (3). As the method of shortening the critical path (the carry propagation path) to increase the operation speed, the system is provided, in which the multiplier Y is divided into a plurality of groups (e.g., m bits group), as described hereinbefore, and the partial products are produced for the corresponding group.

Now, when it is assumed that m=2, the partial products are 0, X, 2X and 3X. For m=3, 0, X, 2X, 3X, 4X, 5X, 6X and 7X are required as the partial products. Where 2X, 4X and 8X can be easily produced by shifting the multiplicand X in the left direction by 1, 2 and 3 bits, respectively, the 3X, 5X and 7X (in which the 6X is obtained by shifting the 3X by one bit) can not be easily produced by only the shifting operation. Certainly, by increasing in the value of in the number of the partial products to be produced can be decreased, but the kinds of the partial products to be required is increased. Therefore, the circuit for producing the partial product and the partial sum is complicated. Moreover, the regularity of the layout of LSI circuit pattern is lost.

On the other hand, if the representation of negative values (e.g., the modified two's complement form) is manipulated in the partial products, it is possible to reduce the kinds of the partial products to be necessitated, e.g., 0, .+-.X and .+-.2X for m=2, and 0, .+-.X, .+-.2X, .+-.3X and .+-.4X for m=3 (in the two's complement form, the negative value is easily obtained by inverting the respective bits and by adding 1 to the least significant bit (LSB) of the inverted bits).

Next, with respect of the number of full adders which are necessarily used in the multiplying circuit the following is to be considered. In the parallel multiplication system in which the multiplicand (16 bits) is multiplied by the multiplier (16 bits) without the decoding operation to produce partial products (e.g. AND operation is usually used), and in which these partial products are summed up by adders, full adders are required for the partial products of each bit except for the first LSB bit. As a result, 16.times.(16-1)=240 of full adders are required. In the carry save system, further, the adder for carry addition is required at the final stage so that the number of the full adders to be required becomes 16.times.[(16-1)+1]=256. On the other hand, in the Booth's algorithm, if 2 bits (m=2) of the multiplier are decoded at a time, four kinds of the partial products (0, 1X, 2X and 3X) are to be produced. Therefore, the number of the partial products becomes 18.times.(16/2-1). If the 3X is produced by 2X+X, moreover, the number of the partial products becomes 18.times.(16/2-1)+16=142 because adders of 16 bits are required. In the carry save adder system, moreover, the number of the partial products becomes 18.times.[(16/2-1)+1]16=160.

If the representation of negative value is employed in the partial product, the kinds of the partial products are 0, .+-.X and .+-.2X. Further, since the sign bit is added in the multiplier, the multiplication of 16 bits.times.17 bits are to be executed. Thus, 17.times.(17/2.vertline..sub.integer -1)+32=168 are required. Here, the value 32 indicates the CSA of the final stage. The result of the examinations for 3 bits (m=3) and for 4 bits (m=4) are shown in Table 2:

Where, parenthesized numerical values belong to the carry save adder system.

The above simulations are more or less different depending upon whether the method of generating the value 7X is made by 8X-X or by 4X+(2X+X). However, the table shows reasonable data in practical use.

As the result of the above examination, the quantity of hardware elements will be minimized in m=2 (*) in the unsigned magnitude. While, if the representation of negative value is allowed in the partial product, m=3 (**) will be best as shown in Table 2. Therefore, the partial product producing system of m=3 is effective. Despite this fact, however, it is necessary to sufficiently examine the hardware for correction of complement and the regularity of the circuit pattern in the layout.

Here, in order to represent the negative value by 2's complement, x.sub.16 and y.sub.16 are further added to the equations (1) and (2). Thus, the modified equations may be written as: ##EQU2## where x.sub.16 =0 ##EQU3## where y.sub.16 =0

The equation (5) is expanded as follows: ##EQU4## As is apparent from (6) and (7), the value B.sub.j takes one of 0, .+-.1, .+-.2, .+-.3 and .+-.4 in dependence upon the bit pattern of the consective four bits (one of the four bits is overlapped with the adjacent bit pattern). The maximum 4X (=X.multidot.2.sup.2) of the partial products is produced by a leftward shift of the mutliplicand X by 2 bits. Further, the multiplicand can be represented as follows, where the sign bit is expanded and the minus (negative) means inversion of each bit and addition of 1 to the LSB. ##EQU5## Since the product P is determined as the summation of the partial products, the following equation (9) is obtained from the equations (7) and (8): ##EQU6## The righthand term of the equation (9) is determined by the array circuit which shifts the multiplicand A by a weight 2.sup.3j-1 according to the value B. Since the sign bit is expanded, in the lefthand term, a.sub.18 =x.sub.16, and the following inequalities are obtained depending upon the value of B.sub.j : ##EQU7##

Thus, the partial product can be negative. If the 2's complement form is used in the negative representation, expansions of the sign bit is required for summations of j=0 to 5. Therefore, the sign portion will be expanded by making use of the characteristics of binary numbers, as follows: ##EQU8## In the equation (11), the sign bit is not expanded to the 34th bit so long as the multiplication of -1.times.-1 is not executed in the multiplication of 17.times.17 bits. Since both the multiplier and the multiplicand are positive in this case from the conditions of the equations (4) and (5), the first term of -2.sup.33 may be ignored.

On the other hand, although the operation speed, the number of elements and the power consumption are important factors in the design of the LSI circuit, the regularity in the layout is also important.

Therefore, in the present invention, the production of the partial products corresponding to multiplication (except for one) of the multiplicand by odd multipliers is separated from that of the partial product of even multipliers and the multiplicand. That is, in the case when 4 bits are decoded at a time, 3X is produced regardless of the decoding results.

For example, 3X may be produced, before 2X, 4X or the like is calculated, by the calculation (2X+X) whenever the multiplicand X is received in the multiplying circuit, or may be read out of a table memory in which the partial products corresponding to the multiplication of the multiplicand by odd multipliers are preliminarily prepared therein. Thus, the righthand term of (9) can be performed by the regular array circuit (shifting and adding).

Further, according to the present invention, with respect to the lefthand term of (9), the equation (11) is used. That is, since summation can be conducted at a suitable position by expanding the lefthand term of (9) as indicated in (11), the correction of the sign bit is unnecessary. Therefore, no expansion of the sign bit is required.

Moreover, in the case where the carry operation (C.sub.a .multidot.2.sup.i) is performed at the time, when the partial product with the negative value is produced, the carry propagation speed becomes slow. Therefore, the summation of C.sub.a .multidot.2.sup.i is performed at the final CSA portion. Here, for the multiplicand X=0, since the carry of +1 is propagated to the MSB (i.e., the sign bit) (In other words, the carry stops midway to exert no influence to the sign bit for X.noteq.0), the value of the sign bit become different. This makes it necessary to detect X=0 to drop the output to zero.

As a result, according to the present invention a multiplying circuit can be constructed with the regular array pattern by means of: a generation circuit of 3X; an adder of 16 bits; a decoder of B.sub.ja ; a selector circuit at j=0; 18.times.5=90 arrays of unit circuits having a full adder and a selector of j=1 to 5; and a 32 bits adder of CSA at the final stage. Thus the multiplying circuit can be formed with 138 full adders and a code correcting circuit (which can be formed with little hardware as is expressed by the equation (11)). According to this construction, it is possible to provide a multiplying circuit which satisfies the regularity of the pattern layout in addition to the high speed operation and the small number of the elements.

FIG. 1 is a circuit block diagram showing an embodiment of the present invention. There is shown an example of the multiplier for multiplying the multiplicand X (x.sub.0 to x.sub.15) of 16 bits and the multiplier Y (y.sub.0 to y.sub.15) of 16 bits. The circuit is constructed by applying an N-channel MOSIC technology. Incidentally, the operation is described in positive logic, but the negative logic is also acceptable. The multiplicand X is supplied to a 3X producing circuit 1 through input terminals (x.sub.0 to x.sub.15). On the other hand, the multiplier Y is received at input terminals (y.sub.0 to y.sub.15) and is divided into a plurality of bits (e.g., two bits y.sub.0 and y.sub.1 at the first stage of a decoder 3 and subsequently y.sub.1 -y.sub.4, y.sub.4 -y.sub.7, y.sub.7 -y.sub.10, y.sub.10 -y.sub.13 and y.sub.13 -y.sub.15), which are simultaneously applied to the corresponding stages 3-2 to 3-6, respectively. A shift/selector circuit 2 has a plurality of logic circuits 2.sub.1 2.sub.108 arranged in array shape. The logic circuits 2.sub.18, 2.sub.36 . . . , 2.sub.108 at the right side are coupled to an adding circuit 4, while the logic circuits 2.sub.1, 2.sub.19, . . . , 2.sub.91 at the botton side are coupled to an adding circuit 4'. The product of 32 bits (e.g., P.sub.0 to P.sub.15 and P.sub.16 to P.sub.31) are extracted from the adding circuits 4 and 4'. The 3X producing circuit 1 is composed of sixteen blocks 1.sub.1 to 1.sub.16 and executes 2X+X by its shift operation and adding operation. Wherein, the LSB (x.sub.0) of the multiplicand X is directly transferred to the logic circuit 2.sub.18 in the shift/selector circuit 2. The block 1.sub.1 at the left side of the 3X producing circuit 1 receives a low level signal (ground level signal) at an input terminal. Each block has the same element. The first stage 3-1 and the second stage 3-2 of the decoder are shown in FIG. 2. The decoding operation is executed according to the four bits of the multiplier Y at a time as shown in table 3.

As shown in table 3, the decoder 3 generates six kinds of signals (0, X, 2X, 3X, 4X, P and N), where P and N mean the sign signals designating a positive value and a negative value, respectively. Further, since y.sub.-1 and y.sub.-2 are both "0", the y.sub.0 and Y.sub.1, the signals generated from the first stage 3-1 are only 0, .+-.2X and .+-.4X as shown in table 3. Therefore, by applying only y.sub.0 and y.sub.1 to the first stage 3-1 of the decoder 3, the circuit can be simplified. That is, in FIG. 2, when y.sub.0 and y.sub.1 are both "0", the signal 0 is generated, while when y.sub.0 and y.sub.1 are "0, 1", "1, 0" and "1, 1", the signals 2X, 4X and N, and 2X and N are generated, respectively. On the other hand, with respect to the remainder stages 3-2 to 3-6, four bits are applied thereto. Therefore, the same circuit 3-2 in FIG. 2 is used in each stage, in which transistor switching gates G.sub.1 to G.sub.8 are employed. For example, the transistor gate G.sub.1 receives an output of an inverter I.sub.1 at a gate electrode and its source (or drain) electrode is coupled to the y.sub.2, while its drain (or source) electrode is coupled to an inverter I.sub.2 and to a source (or drain) electrode of the transistor gate G.sub.2. It will be noted that the sixth stage 3-6 receives y.sub.13 to y.sub.15 and a ground level signal the same as the block 1.sub.1 of the 3X producing circuit 1. Further, the signal N of each stage is directly applied to the corresponding block 2.sub.1, 2.sub.19, 2.sub.37, 2.sub.55, 2.sub.73 and 2.sub.91 and is inverted by inverters 10 to 14 to correct the sign bit. The inverted signals N are applied to the adjacent blocks 2.sub.19 to 2.sub.91, respectively.

The 3X producing circuit 1 is shown in detail in FIG. 3 in which 16 blocks 1.sub.1 to 1.sub.16 have the same circuit pattern. Each block has an AND gate 30 and a NOR gate 31 which receives the corresponding bit and the bit of the previous bit. A NOR gate 32 receives outputs of the AND gate 30 and the NOR gate 31 and generates a control signal for controlling a carry signal propagation. That is, the carry signal is propagated through a propagation line 34 which is extended through all blocks. The control signal is applied at a gate electrode of a switching transistor gate G.sub.33. If x.sub.0 and x.sub.1 are all "0", the gate G.sub.33 is turned off. Therefore, the carry signal is stopped, but the signal (a ground level) designating no carry generation is transferred to the adjacent block 1.sub.15 since the gate G.sub.30 is turned on. However, if either x.sub.0 or x.sub.1 is "1", the gate G.sub.33 is turned on, thereby the carry signal from the previous block is transferred to the adjacent block. Further, if y.sub.1 and y.sub.0 are all "1", the gate G.sub.33 is turned off and the gate G.sub.31 is turned on by an output "1" of NOR gate 33. Therefore, a carry signal generated by the block itself is transferred to the next block. As shown in FIG. 3, the AND gate 30 and the NOR gate 31 receive the signal from the previous bit which is equal to the shifted bit by one (that is, 2X). In other words, each block receives 2X and X and adds them to each other, thereby 3X is produced and is transferred to the shift/selector circuit 2 through line 36. On the other hand, the X is also directly transferred through line 35 to the shift/selector circuit 2.

The logic circuits 2.sub.1 to 2.sub.18 of the shift/selector circuit 2 are shown in FIG. 4. These circuits are different from the subsequent circuits 2.sub.19 to 2.sub.108 because the number of input signals from the decoder 3 is different from that of the circuits 2.sub.19 to 2.sub.108. The circuits 2.sub.1 to 2.sub.18 includes four switching transistor gates G.sub.40 to G.sub.43, an inverter 40 and a NOR gate 41, respectively. The gate G.sub.40 is turned on in response to the signal 4X, as the result the multiplicand X shifted in the left direction by two bits, that is 4X is selected and is transferred to the NOR gate 41. While, when the signal 2X is generated from the decoder 3, the one bit shifted multiplicand X, that is, 2X is selected by the gate G.sub.41. Further, the selected data is transferred through line 42 to the lower logic circuits shown in FIG. 5 with the multiplicand X. In FIG. 5, the logic circuits 2.sub.19 to 2.sub. 90 are omitted. The logic circuits in FIG. 5 receive the signals X, 2X, 3X, 4X, 0, P and N from the decoder 3 for selecting the data 4X, 3X, 2X, X and 0 according to the decoding operation. The selecting operation is executed by four switching gate transistors G.sub.50 and G.sub.53. In the circuit, a NAND gate 50, an AND gate 51 and NOR gates 52, 53 and 54 act as a full adder, and two output 55 and 56 are produced. Further, the signal N is used as the sign bit 57.

Adder circuits 4.sub.0 to 4.sub.31 are shown in FIG. 6, in which each circuit pattern may be the same as that of FIG. 3. The product (total sum) of 32 bits are obtained at the output terminals P.sub.0 to P.sub.31.

As described above, the shift/selector circuit 2 executes the shift operation to produce partial products according to the result of the decoding operation, but it has not the 3X producing circuit. That is, the circuit 2.sub.1 to 2.sub.18 has only a selector (40, G.sub.40, G.sub.41) and a zero-inversion control circuit (G.sub.42, G.sub.43 and 41). Moreover, the remaining circuits 2.sub.19 to 2.sub.108 connected with the decoders 3-2 to 3-6 are made to have the same construction as that of the circuit 2.sub.91, which is equipped with a shift/selector means (G.sub.50 to G.sub.53), a zero-inversion control means (G.sub.54, G.sub.55 and 54) and a full adder (50 to 53 and 60). This full adder executes the operation of inverting the value of 4X, 2X, X or 3X and to add 1 to the LSB, if these are negative (minus). Moreover, the decoder 3 and the shift/selector circuit 2 are connected through a compensation circuit based upon the equation (11).

In the present embodiment, the value 3X is generated in response to the input of the multiplicand X so that the two data X and 3X are supplied from the 3X generating circuit 1 to the shift/selector circuit 2. These data are selected and processed in accordance with the decoded results. The partial products thus generated are added in the final-stage adders 4 and 4' so that the products P.sub.0 to P.sub.31 of 32 bits are outputted.

As is apparent from the description thus far made, according to the present embodiment, the multiplier can be decoded in 4 bits at a time so that a high-speed multiplier can be provided. Moreover, the generations of the odd multipliers (3X) are conducted simultaneously with the input of the multiplicand, and the selections of the values 3X and X are conducted in accordance with the decoded results. As a result, the multiplications can be easily executed by a small quantity of the hardware. In place of the 3X generating circuit, incidentally, a table of a ROM or the like prepared with the data for odd multipliers of X for 3X or more may be used and referred to in accordance with the decoded results.

Moreover, it is possible to adopt either of the construction for repeating the processes of Table 3 or the construction equipped with all the hardware in parallel. Despite of this fact, however, the basic construction may be composed of: the 3X generator which is separated from the circuit 2, the shifter means for generating 2X and 4X for the multiplicand X in accordance with the results of decoding an arbitrary group of the multiplier Y; the selector for selecting one of the values 3X, 0, X, 2X and 4X; the inverter for inverting those values; the adder for adding the partial products thus generated; and the circuit for weighing in accordance with the multiplication groups (For example, a shift of each 3 bits is made to the MSB in the parallel system, whereas a shifter is required in the sequential system).

As shown in FIG. 1, moreover, the number of the bits of the shift/selector circuit is so expanded (to 18 bits) as to correspond to the maximum (i.e., 4X in this example) of the partial products so that the code bits are diffused in the computing process. As a result, the multiplier having its code bits overflowing requires a circuit for temporarily holding the overflowing bits, which can be eliminated from the present invention. Especially, the multiplier shown in FIG. 1 has other advantages to be enumerated in the following:

(1) The generation of 3X is deduced by adding the value 2X (which is prepared by shifting the value X by one bit to the MSB) and the value X by means of the total adder.

(2) The circuit does not contain any latch or register means but is constructed of a static combination circuit.

(3) The addition of the 32 bits of the final stage for deducing the products P.sub.0 to P.sub.31 resorts not to the CSA system but to the ripple through system (which is identical to the 3X circuit), which is easy to fabricate using MOS circuits.

(4) Since this example is applied to the absolute value of 16.times.16 bits, no correction of sign bits is required. Identical processings are also sufficient for the multiplicand X=0000.sub.H.

Specifically, the present multiplier can be constructed of a reduced number of elements and can have its critical path (i.e., its longest carry transmission path) shortened.