JP2525083B2 - Multiplier - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multiplier, and more particularly to a multiplier suitable for use in a digital parallel multiplication circuit.

Generally, in a parallel multiplier having a practical multiplication scale of 8 × 8 bits or more, a carry save method (hereinafter, referred to as CSA method) or a wallet tree (Wall).
ace Tree) method is adopted.

The CSA method inputs a carry signal to a one-digit higher-order adder and processes it bit by bit. Although it is close to manual calculation and has a difficulty in multiplication speed, it is excellent in layout easiness. There are features.

On the other hand, in the Wallace tree system, an input signal for 3 bits is input to one adder (full adder), and the sum signal is input to the full adder at the next stage of the digit.
The carry output is input to a full adder at the next stage, which is one digit higher, and added, which has the advantage that the multiplication speed is fast, but has the disadvantage that the circuit has no regularity and is difficult to design.

Therefore, a multiplier having a high multiplication speed and an easy layout is required.

[0006]

2. Description of the Related Art As a conventional multiplier of this type, for example, there is a multiplier (CSA system) based on a modified Booth algorithm as shown in FIG.

In this example, all the partial products (P _{P0 to} P _P3 ) generated by the partial product generation unit (a) are added together by the addition unit (b). The partial product generator (a) includes a block (P _Pi generator) that generates 0, ± X, and ± 2X, and a block (Y decoder) that generates a signal that selects one of these as a partial product. And the adder unit (b) has an adder array configuration.

According to the above configuration, the partial product generator (a) and the adder (b) can be designed separately, and the functional blocks can be subdivided for design, but this is not preferable for increasing the number of multiplication bits. There is a problem that it is not possible to deal with the accompanying increase in the number of wires between blocks.

Therefore, if the multiplier is realized by the above-mentioned Wallace tree structure, the number of passage stages of the adder can be reduced, which is preferable in terms of high speed.

In general, when a multi-bit digital parallel multiplication circuit is constructed, signal processing is often performed using a multi-input, equal digit adder circuit. For example, in 8 × 8 bit multiplication, as shown in FIG. In addition, a maximum of eight inputs of the same digit addition circuit is required. In FIG. 21, a7 to a0 are multiplicands,
b7 to b0 are multipliers, both of which are represented by two's complement, and the most significant digits a7 and b7 are sign bits.

That is, when an 8 × 8 bit multiplication is processed by an 8-input Wallace tree circuit as shown in FIG. 22, six 1-bit full adder circuits (hereinafter referred to as 3W circuits) are required (see FIG. 23) Set the processing time of the 3W circuit to τ
Then, the processing time of the 8-input Wallace tree circuit is 4τ.

On the other hand, in recent years, a multi-input adder circuit has
A method has been proposed in which a digital parallel multiplication circuit is configured by dividing into input units and repeatedly using a 4-input Wallace tree circuit (hereinafter referred to as 4W circuit) as shown in FIG.

When this method is used, the circuit is integrated into an LSI ( l arg
e s cale i when ntegrated circuit) of complex construction 8 there is no need to consider the input more Wallace tree circuit to be designed steps in order to be capable of logical description and layout by the repetition of a relatively simple circuit Can be reduced.

Further, the usual 4W circuit is constructed as shown by the part marked with * in FIG. 22, but with the construction shown in FIG. 24, 8-input addition processing can be performed in 3τ, and the whole circuit is The speed can be increased.

However, in such a method, the speedup and the layout of the layout can be efficiently achieved only in the addition processing of the partial products, and in the partial product generation necessary for the multiplication processing, It is still difficult to lay out the routing portions of many signal lines whose outputs are input to the partial product addition circuit.

In order to solve this problem, as shown in FIGS. 25 and 26, a plurality of partial product generation circuits and a partial addition circuit for performing the addition are made into one block, and these are arranged by the required number. A method to simplify the layout process was considered.

This is a 3D block consisting of three partial product generation circuits (hereinafter referred to as P circuits) as shown in FIG. 27 and a 3W circuit for adding them, a 3D block, and a 3D block. 5 shows a block configuration in which a 5D block including a 4W circuit that adds four output signals (sum signal and carry signal) is vertically arranged.

Each of the 3D block and the 5D block is 1
A 6-input Wallace tree circuit is composed of these. In order to enable such a repeated arrangement of blocks, the multiplicand signal is propagated in one direction from upper right to lower left in the figure.

In this example, if a 22.times.22 bit parallel multiplication circuit is configured, the configuration is as shown in FIG. Fig. 29
FIG. 30 shows an example of a 3D block logic circuit, and FIG. 30 shows an example of a secondary Booth decoder circuit.

[0020]

However, in such a conventional multiplier, the layout man-hours can be reduced, but since the signal propagates in only one direction, the layout outline of the entire multiplication circuit is It is not a rectangle but a parallelogram that is close to a diamond. That is, in FIG. 28, there is a wasteful area in which a circuit cannot be arranged in the lower right empty area A and the upper left empty area B, and there is a problem that the integration density of the entire multiplication circuit decreases.

In order to avoid this, normally, convolution processing,
That is, the entire circuit block under the empty area B is fitted into the empty area A and molded so as to fit in a rectangle.
Then, this convolution process takes time and troubles, which causes an obstacle to the demand for reduction of man-hours and improvement of layout efficiency.

Further, in the conventional example shown in FIG. 28, 3D and 5D blocks are simply arranged, but
In practice, it is also necessary to use modified blocks of 3D and 5D blocks, which further complicates the convolution process.

[Purpose] Therefore, the present invention provides a multiplier which facilitates logic design / layout design without degrading the circuit performance and lays out at a high density to achieve both high speed and easy layout. It is intended to be provided.

[0024]

To achieve the above object, a multiplier according to the present invention arranges multiplicand bit transmission lines in parallel in a two-dimensional plane and decodes the multiplier bit transmission lines or multipliers on the multiplicand bit transmission lines. A multiplier for performing a multi-input addition process by dividing the multi-input addition process into a plurality of partial addition processes by cross-arranging signal lines, wherein signals to be partially added at the same time by the partial addition process are generated by signals from the multiplicand bit transmission line. A plurality of partial product generating means, a first partial adding means for adding the outputs of the partial product generating means, and a second adding means for adding an output of the first partial adding means and a predetermined input from the outside. A predetermined number of blocks are continuously arranged in the same row, and the multiplicand bit transmission line connected to each partial product generating means in the same block is predetermined from a block adjacent to the block. Digit-shifting and digit-shifting and connecting, and shifting the output signal line of the first partial adding means in the direction opposite to the multiplicand bit transmission line, and using the output signal line as a predetermined input from the outside. The block is connected to the second addition output of the block.

The combinations of the multiplicand bit transmission lines to the partial product generating means for generating the signals to be input to the plurality of first partial adding means in the same block are preferably all the same, and the first portion of the block is the same. It is preferable that the output signal of the first partial addition means of the other block, which is equal to the shift amount of the output signal of the addition means and is digit-shifted in the opposite direction, is input to the second partial addition means of another block.

[0026]

According to the present invention, a predetermined number of blocks are continuously arranged in the same row, and a multiplicand bit transmission line connected to each partial product generating means in the same block is aligned by a predetermined number of digits from a block adjacent to the block. The output signal line of the first partial addition means is shifted and aligned in the direction opposite to that of the multiplicand bit transmission line, and the output signal line is connected to the second addition output of another block as a predetermined input from the outside. To be done.

That is, by shifting the input of the partial product generating means of the block in which the multi-input addition processing is performed and the output of the second partial adding means, the layout outline of the entire multiplication circuit becomes a rectangle instead of a parallelogram. The logical design / layout design is facilitated and a high-density layout is achieved.

[0028]

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described below with reference to the drawings. 1 to 19 are diagrams showing an embodiment of a multiplier according to the present invention.

[0029] First, according to FIG. 1, will be described the configuration of the parallel multiplication circuits 22 × 22 bits using an algorithm of the secondary Booth, the multiplication ^{_{circuit, 6D 3, 6D 3 *,}} 6D
_3L , 6D _4H , 6E _3A , 6E _3B , 6E _3C , 6E _3L , 6
E _4H , 4W ₃ , 4W _4H , 12G, 12F, CPA (carry propagation adder circuit) blocks and circuits. Note that a _{0 to} a ₂₄ are multiplicand registers and b
_{0 to} b ₂₁ are multiplier registers.

FIGS. 2 and 3 are circuit diagrams of 6D ₃ blocks. Blocks in which the 3D and 5D of the conventional example shown in FIGS. 25 and 26 are vertically arranged are horizontally arranged for three consecutive bits of the multiplicand, That is, it corresponds to three columns of the four columns of the circuits of FIGS. In this case, the difference from the conventional example shown in FIGS. 25 and 26 is that the output sum signal S ( S um) from the above 3D block is to the right, that is, three digits in the direction opposite to the direction in which the multiplicand signal is propagated, the carry signal C a (C arry) and 2-digit shift input to 4W circuit below each column, the left output sum signal from the bottom of the 3D block, i.e., the same direction as the direction in which propagating multiplicand signal 3 digits, and the carry signal is similarly shifted by 4 digits and input to the 4W circuit below each column. The reason for configuring in this way is that each 3
This is because the combinations of the multiplicand signals to the D blocks are made the same and the digit alignment shift is performed when the output signals from these blocks are input to the next partial adder circuit.

That is, the input multiplicand signals to the 3D blocks in the same column flow from the upper right to the lower left of the figure as in the conventional example, but do not flow between blocks in different columns.

Therefore, the 6D ₃ block becomes a basic block constituting a multiplication circuit, and the 6D ₃ block and
Most of the multiplication circuit can be easily designed by repeatedly using the 6D ₃ modified block in terms of logical and layout.

By the way, the blocks of the layout images shown in FIGS. 2 and 3 can be combined into a logic block as shown in FIG. 4, and the one-to-one correspondence between the logic and the layout can be facilitated and the multiplication circuit can be designed. It can be greatly simplified.

The 6D ₃ ^* block is a _i-6 , a of the inputs to the upper and lower two 3W circuits at the right end of the 6D ₃ block.
_The one corresponding to the P circuit output for inputting the two signals _i-7 is the input of the "0" fixed signal.

[0035] Figure 5 and 6 is a circuit diagram of a 6D _3L block, when processing the least significant digit related multiplicand in 6D ₃ blocks, if the decoding result of the secondary Booth is negative, the required operation adds 1 It is the one with the necessary changes to add to the digits.

7 and 8 are circuit diagrams of the 6D _4H block. In processing the most significant digit of the multiplicand in the 6D ₃ block, necessary changes are made to the code processing digit which is the decoding result of the secondary Booth. It is a thing. In addition,
P _h circuit, two-input Wallace tree circuit (hereinafter, 2W that the circuit) Example of FIG. 9, respectively, shown in FIG. 10.

FIGS. 11 and 12 are circuit diagrams of the 6E _3A block, and show one of the lower row blocks forming the block array shown in FIG. One of the inputs to the 3W circuit in the lower stage of this block is not the output signal from the P circuit but the "0" fixed signal or the "1" fixed signal. This is because when adding the results of the Booth decoding, a correction process is performed to perform calculation without expanding each decoded output bit up to the most significant digit (42 digits) of the product. This correction is performed for the addition of.

In order to carry out this correction operation, the 6E _3B block uses the 6E _3A block to input one input to the lower 3W circuit in the column of a _i and a _i-2 to a fixed "0" signal, a
"1" for one input to the lower 3W circuit in column _i-1
The block is changed so that it becomes a fixed signal, and 6
The block of E _{3C is} a block of 6E _3A , and one input to the lower 3W circuit in the row of a _i and a _i-2 is a fixed signal of “1”, the lower 3W of the row in a _i-1 is As a block in which one input to is changed to a fixed "0" signal,
These are arranged alternately. In addition, 6E _3A
Of the inputs to the 3W block on the upper right of the block circuit diagram, one is a fixed "0" signal, but 6E _3B , 6
In the configuration of the E _3C block, the P output signal is applied to all the inputs to that 3W block.

The 6E _3L block corresponds to the 6D ₃ block by 6D
Are those subjected to a similar change to that was changed to _3L blocks into blocks of 6E _3A, also, 6E _4H of blocks changed 6D ₃ block 6D _4H blocks and 6E similar changes
It is applied to a _3A block.

FIG. 13 is a circuit diagram of the 4W ₃ circuit, and FIG. 14 is 4W _4H.
FIG. 24 is a circuit diagram of a circuit, both of which are composed of the 3W circuit shown in FIG. 23 and the 4W circuit shown in FIG. 24.

FIG. 15 is a circuit diagram of a 12G block, and 1
The 2G block is the 2W block shown in FIG. 10 and the 3G shown in FIG.
It is composed of a W circuit. 16 and 17 are circuit diagrams of the 12F block, and the 12F block is composed only of wiring between the blocks.

The CPA is a carry propagation type addition circuit, which adds the sum signal of each digit and the carry signal output from the Wallace tree circuit at each digit, and finally obtains the product output of each digit. 1 to 19, C _xx ( _xx is arbitrary) is a carry signal, and S _xx ( _xx is arbitrary) is a sum signal.

Therefore, by arranging and using the above blocks as shown in FIG. 1, a 22.times.22-bit parallel multiplication circuit using the quadratic Booth algorithm is constructed.

That is, the 6D ₃ blocks arranged in each row, or their modified blocks (6D ₃ ^* , 6D _3L , 6)
The output signal from (D _4H etc.) is shifted to the right by 6 bits for the sum signal, and shifted to the right for the carry signal by 5 bits, and is input to one of the 4W ₃ circuits arranged under each of them, and is input to each column. When the output signal from the 6E _3A block or its modified block (6E _3B , 6E _3C , 6E _3L , 6E _4H, etc.) arranged side by side is a sum signal, shifts 6 bits to the left, and if it is a carry signal, shifts it to 7 bits to the left. Then, it is input to one of the 4W ₃ circuits arranged below each.

As described above, in this embodiment, 6D ₃ , 6
Most of the multiplication circuits can be laid out simply by arranging E _3A and 4W ₃ and these modified blocks so that the wirings overlap each other, and each block can have a one-to-one correspondence between logic and layout. The design is much easier than in.

Therefore, the layout result thus obtained does not include a wasteful area, and high integration can be achieved.

Moreover, since the 4-input adder circuit (4W circuit) capable of high-speed processing for dividing the multi-input adder circuit can be used, the circuit speed can be increased. Although the above embodiment has been described by taking the case where the multi-input adder circuit is divided into three inputs as an example, the present invention is not limited to this, and for example, 28
When input addition is required, as shown in FIGS.
Divide the first division into 3 inputs and 4 inputs, configure a 7D ₃ block including a 4W circuit that receives these outputs, and use the 4 blocks to perform Wallace tree addition of each digit. However, 32-input addition can be dealt with by repeatedly using the 4-input addition block.

Although the above embodiment is described on the assumption that the second order Booth's algorithm is used, for example,
It is also possible to support a multi-order Booth algorithm such as third-order Booth or a method of directly multiplying a multiplicand and a multiplier.

[0049]

According to the present invention, by shifting the input of the partial product generating means and the output of the second partial adding means of the block in which the multi-input addition processing is performed, the layout outline of the entire multiplication circuit is set to a parallelogram. Instead, it can be a rectangle.

Therefore, the logic design and layout design are facilitated, a high-density layout can be performed, and both the high speed and the layout easiness by the Wallace tree method can be achieved.

[Brief description of drawings]

FIG. 1 is a diagram showing a circuit configuration of a 22 × 22-bit multiplier of the present invention.

FIG. 2 is a circuit diagram of a 6D ₃ block according to an embodiment of the present invention.

FIG. 3 is a circuit diagram of a 6D ₃ block according to an embodiment of the present invention.

FIG. 4 is a logical block diagram of a 6D ₃ block according to an embodiment of the present invention.

FIG. 5 is a circuit diagram of a 6D _3L block according to an embodiment of the present invention.

FIG. 6 is a circuit diagram of a 6D _3L block according to an embodiment of the present invention.

FIG. 7 is a circuit diagram of a 6D _4H block according to an embodiment of the present invention.

FIG. 8 is a circuit diagram of a 6D _4H block according to an embodiment of the present invention.

FIG. 9 is a circuit symbol and a circuit diagram of a _Ph circuit according to an embodiment of the present invention.

FIG. 10 is a circuit symbol and a circuit diagram of a 2-input Wallace tree circuit according to an embodiment of the present invention.

FIG. 11 is a circuit diagram of a 6E _3A block according to an embodiment of the present invention.

FIG. 12 is a circuit diagram of a 6E _3A block according to an embodiment of the present invention.

FIG. 13 is a circuit diagram of a 4W ₃ circuit according to an embodiment of the present invention.

FIG. 14 is a circuit diagram of a 4W _4H circuit according to an embodiment of the present invention.

FIG. 15 is a circuit diagram of a 12G block according to an embodiment of the present invention.

FIG. 16 is a circuit diagram of a 12F block according to an embodiment of the present invention.

FIG. 17 is a circuit diagram of a 12F block according to an embodiment of the present invention.

FIG. 18 is a configuration diagram of a 28-input adder circuit according to an embodiment of the present invention.

FIG. 19 is a configuration diagram of a 28-input adder circuit according to an embodiment of the present invention.

FIG. 20 is a configuration diagram of a conventional parallel multiplication circuit based on a modified Booth algorithm.

FIG. 21 is a diagram illustrating an example of multiplication of 8 × 8 bits.

FIG. 22 is a configuration diagram of a conventional 8-input adder circuit.

FIG. 23 is a circuit symbol and a circuit diagram of a conventional 3-input Wallace tree circuit.

FIG. 24 is a circuit symbol and a circuit diagram of a conventional 4-input Wallace tree circuit.

FIG. 25 is a configuration diagram of a conventional 6-input adder circuit.

FIG. 26 is a configuration diagram of a conventional 6-input adder circuit.

FIG. 27 is a circuit symbol and a circuit diagram of a conventional partial product generation circuit.

FIG. 28 is a diagram showing a circuit configuration of a conventional 22 × 22-bit multiplier.

29A and 29B are a circuit symbol and a circuit diagram of a conventional 3D block.

[Fig. 30] Fig. 30 is a circuit symbol and a circuit diagram of a decoder circuit of a secondary Booth algorithm of a conventional example.

[Explanation of symbols]

a _{0 to} a ₂₄ Multiplicand bit b _{0 to} b ₂₁ Multiplier bit C _xx Carry signal S _xx Sum signal

Claims (3)

(57) [Claims] 1. A multiplicand bit transmission line is arranged in parallel to a two-dimensional plane, and a multiplicative bit transmission line or a decode signal line of a multiplier is cross-arranged in the multiplicand bit transmission line to perform a multi-input addition process for a plurality of partial additions. A multiplier which is divided into processes and which generates a signal to be partially added simultaneously by the partial addition process by a signal from the multiplicand bit transmission line, and an output of the partial product generation unit. And a second partial addition means for adding the output of the first partial addition means and a predetermined input from the outside.
A predetermined number of blocks each having an adding means are continuously arranged in the same row, and the multiplicand bit transmission line connected to each partial product generating means in the same block is digitized by a predetermined number of bits from a block adjacent to the block. Shift and connect,
The output signal line of the first partial adding means is shifted in the direction opposite to the multiplicand bit transmission line by digit shifting, and the output signal line is connected to the second addition output of another block as a predetermined input from the outside. Characteristic multiplier. 2. One of the multiplicand bit transmission lines to the partial relation generating means for generating a signal to be input to the plurality of first partial adding means in the same block is the same. 1 multiplier. 3. A block different from the two blocks in the output signal of the first partial addition means of the other block which is equal to the shift amount of the output signal of the first partial addition means of the block and is digit-shifted in the opposite direction. 3. The multiplier according to claim 2, wherein the multiplier is input to the second partial addition means of.