JP3112662B2 - 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.

[0002]

2. Description of the Related Art A multiplier for multiplying digital data includes:
In addition to being used as a single LSI, DSP (digital
It is also widely used for incorporation into LSIs such as signal processors. This type of multiplier is required to further increase the speed, reduce the circuit scale, and reduce the chip area with the increase of the multiplication bit width and diversification of applications, and a circuit system to which various multiplication methods are applied has been proposed. ing.

For example, one of the fastest multiplication methods, a multiplication method using a 2-bit booth recoding method is shown in "Nikkei Electronics" (May 29, 1978, pp. 76-89). ing. This multiplication method is
The following algorithm is used to speed up multiplication and the like. For example, when multiplying a multiplier Y having an m-bit width by a multiplicand X having an n-bit width, the multiplier Y is represented by a two's complement expression as follows.

[0004] Here, y _m = y _s q is such that when m is an even number, q = m / 2, and when m is an odd number, q = (m
-1) / 2 Further, y ₀ is a value for convenience, and y ₀ = 0.

Therefore, the product P of X and Y is Becomes

Here, Y_2i, Y_{2i + 1}, Y_{2i + 2}Each
Since it takes a value of 0 or 1, (Y _2i+ Y_{2i + 1}-2Y
_{2i + 2}) Indicates 0, ± 1, or ± 2 as shown in (Table 1).
And each partial product is either 0, ± X, or ± 2X
To 2²ⁱMultiplied by

[0007]

[Table 1]

Therefore, the circuit for generating each partial product mainly includes
And shift one bit to double the multiplicand ± X
Lid and mantissa (0, ± X, or ± 2X)²ⁱDouble (heavy
Shifter that shifts two bits at a time
Can be configured. Also find the sum of the partial products
The number of logical stages of the circuit is such that the number of partial products is q = m / 2 (m is
(Even number) or q = (m-1) / 2 (m is an odd number)
Therefore, when connecting a two-input adder in a binary tree form,
og_Twom-1 stage (m is an even number) or log _Two(M-1)
-1 stage (m is an odd number).

As a high-speed multiplier other than the 2-bit booth recoding method, a multiplier using a redundant binary number is proposed in Japanese Patent Application Laid-Open No. 03-0177737. In the multiplier as described above, for example, when the multiplier is 24 bits, the number of partial products is 12, and the number of logical stages is 4. On the other hand, the increase of the multiplication speed and the reduction of the circuit scale are not limited to the improvement of the performance of the multiplication algorithm as described above, but also the optimization of the circuit at the logic element level.

That is, in recent years, a multiplier and a logic circuit including the multiplier are often designed using an automatic design apparatus. In this type of device, when developing circuit information at the logic element level into circuit information at the mounting element level mounted on the chip, a part of the circuit is replaced with an equivalent circuit having a smaller number of logic elements and logic stages. For example, redundant circuit portions are deleted.

In such an automatic design apparatus, when function description information in which a function required for a circuit is represented in a hardware description language or the like is input, the function is mainly converted into a virtual function in which only the function is defined. After converting to functional circuit information in an internal representation format that represents a circuit composed of elements, and then converting it to logic circuit information that indicates a circuit composed of actually existing logical elements, the mounted elements implemented with a specific technology are allocated The generated circuit information indicating the specified circuit is generated.

When the function indicated by the function description information includes multiplication, for example, a predetermined bit width (4, 8, 17, 32 bits, etc.) registered in a library as a hardware macro in advance If a general-purpose multiplier is applicable, it is assigned,
When a multiplier that is not registered in the library is required, a logic circuit that constitutes an addition-shift type multiplier or the like is newly generated. Note that the multiplier,
Alternatively, one of the multiplicands is a constant and the value is 2
In the case of exponentiation, a circuit using a shifter is usually generated.

When the multiplier is a constant that is not a power of 2, the partial product corresponding to a bit having a value of 0 in the multiplier has a value of all bits of 0. Therefore, a circuit for generating such a partial product, The adding circuit always has a constant signal state. Therefore, in the conventional automatic design device, after once generating a multiplication circuit in which the multiplier and the multiplicand are variables and a circuit for generating a constant, as described above, for example, by optimizing the circuit at the logic element level, for example, Deletion or the like of a logic element having a constant signal level has been performed.

[0014]

However, in the conventional automatic design apparatus, optimization of a circuit at a logic element level requires, for example, that only a circuit portion that matches a predetermined pattern set in advance has a larger logic element or circuit element. It is performed by replacing with an equivalent circuit with a small number of logic stages,
Even when such optimization is performed when the multiplier or the multiplicand is a constant, there is a problem that a circuit that minimizes the number of logic elements in the entire circuit cannot always be generated. In particular, when a two-input adder is connected in the form of a binary tree in order to add a partial product, if a portion related to a partial product addition circuit in which all bits have a value of 0 is omitted, usually a binary tree is used. Since the balance is lost, it is difficult to minimize the number of logic elements and the number of logic stages by partial circuit replacement.

SUMMARY OF THE INVENTION In view of the above, it is an object of the present invention to provide a high-speed multiplier which performs multiplication in which a multiplier or a multiplicand is a constant, has a small number of logic elements and logic stages, and is suitable for LSI.

[0016]

In order to achieve the above object, the present invention provides a multiplication that receives a signal X representing an n-bit number and a signal A representing an m-bit constant and outputs a product P of n + m bits. A logical NOT signal A of the constant A
A multiplying means for inputting 0 and the signal X and outputting a signal P0 representing the product thereof; inputting the signal X and the signal P0 to calculate X · (2m -1) -P0 and outputting the signal P Computing means for performing the operation.

A multiplier which inputs a signal X representing an n-bit number and a signal A representing an m-bit constant and outputs a product P of n + m bits, wherein a logical NOT signal A0 of the constant A Multiplying means for receiving the signal X and outputting a signal P0 representing the product thereof; calculating means for receiving the signal X and outputting a signal P01 representing X · (2m -1); With the signal P01 as input,
A subtractor for outputting a signal representing the value of P01-P0.

A multiplier which receives a signal X representing an n-bit number and a signal A representing an m-bit constant and outputs a product P of n + m bits, wherein a logical NOT signal A0 of the constant A Multiplying means for inputting the signal X and outputting a signal P0 representing the product thereof; logical negating means for receiving the signal P0 and outputting a logical NOT signal Q0 of the signal P0; and receiving the signal X as an input. X · (2m -1)
Arithmetic means for outputting a signal Q6 representing +1;
It is characterized in that there is provided an adder which receives 0 and the signal Q6 as inputs and outputs a signal representing the sum of the signal Q0 and the signal Q6 as the signal P.

[0019]

Embodiments of the present invention will be described below with reference to the drawings. Embodiment 1 FIG. 1 is a block diagram showing an example of a hardware configuration of an automatic logic circuit design system.

In FIG. 1, an input device 11 is for inputting function description information and the like on a circuit to be designed by an automatic design system. As the input device 11, a keyboard, a mouse, a light pen, a card reader, a schematic entry system, or the like is used. Further, the present invention is not limited to a device directly input by an operator's operation, and a magnetic disk device that stores information input by the above-described device in advance as a file or a network device that receives information sent from another device is used. You can also.

The central processing unit 12 performs various processes described later to perform circuit design processing such as logic synthesis and circuit optimization processing. The output device 13 outputs circuit information, which is a design processing result of the central processing unit 12, and various information related to processing. As the output device 13, a graphic display, a character display, a printer, a plotter, or the like is used. Further, similarly to the input device 11, a magnetic disk device, a network device, or the like can be used.

As shown in FIG. 2, for example, the storage device 14 includes a design processing storage unit 21, an element library storage unit 22,
And a circuit data storage unit 23 for storing information input from the input device 11, programs and data relating to circuit design processing, and the like. More specifically, for example, the design processing storage unit 21 stores various processing programs for the central processing unit 12 to execute the design processing, conversion rule information applied in the processing, and the like.

The element library storage unit 22 stores information such as functions such as functional elements, logic elements, and mounted elements, and information indicating an area, a delay time, a driving force, and the like as an element library. The circuit data storage unit 23 stores function description information input from the input device 11, function circuit information generated by circuit design processing, logic circuit information, mounted circuit information, and the like.

Here, the function description information mainly includes
The function required for the circuit is information expressed in a hardware description language or the like. The function circuit information is mainly information representing a circuit composed of virtual function elements in which only functions are defined in an internal representation format. The logic circuit information is information indicating a circuit composed of actually existing logic elements at a logic level that hardly depends on a manufacturing process, a design method, or the like. Further, the mounted circuit information is highly dependent on a manufacturing process, a design method, and the like, and is based on a mounted element (for example, a standard cell using a CMOS transistor, a cell in a library of a gate array, or a TTL, This is information indicating a circuit to which an element that depends on a manufacturing process such as ECL is allocated.

An example of the above functional element is shown in (Table 2). For example, a multi-bit adder or the like represents a functional element that adds two numbers having a multi-bit width. The comparator represents a functional element that compares two numbers having a plurality of bit widths. Multi-bit a
nd represents a functional element for obtaining a logical product of each bit of two signals having a plurality of bit widths. Also, a multi-bit in
v represents a functional element that obtains logical negation for each bit of a signal having a plurality of bits.

The ripper and the mixer are functional elements indicating that a plurality of bits of signals are collectively handled or divided for the sake of convenience in the course of the conversion process, and are finally converted into a circuit composed of mounted elements. , Are all functional elements that are deleted when all signals are handled for each 1-bit signal. In general, there is no circuit composed of mounted elements that directly correspond to these functional elements, and once developed into a circuit composed of logic elements that realize those functions, it is replaced with a circuit composed of mounted elements.

[0027]

[Table 2]

An example of the logic element is shown in (Table 3).
In Table 3, for example, a 1-bit adder represents an element that adds two signals having a bit width of 1 bit. Also, 1-bit and is 2 bits whose bit width is 1 bit.
Represents a logic element for calculating the logical product of two or more signals. Circuits composed of mounting elements corresponding to these logic elements are predetermined, and are replaced in the final stage of the design processing.

[0029]

[Table 3]

Next, specific examples of function description information and function circuit information stored in the circuit data storage unit 23 will be described. These pieces of information are stored as, for example, text data. For example, a circuit composed of a 1-bit 2-input AND gate and a 1-bit 3-input adder as shown in FIG. 3A is described as function description information as shown in FIG. 3B. This function description information is converted into, for example, functional circuit information or logic circuit information as shown in FIG. When the function description information directly corresponds to a circuit composed of logic elements, the function circuit information and the logic circuit information may not be particularly distinguished.

In this example, the functional circuit information includes an identification name 31 for identifying each element, and a plurality of pairs of an attribute code 32 and an attribute value 33. The attribute code 32 and the attribute value 33 of each pair are associated with “::”, each pair is separated by “;”, and the identifier 31 is distinguished from other data by “:::”. . As the attribute code 32, “a_kind_of”, “input”, “ou”
put ", etc., and the corresponding attribute value 33
Indicates the type of element, input signal, and output signal.

That is, the element of gate01 is adde
r (adder) whose input signals are sig1, sig
2, sig3 and the output signal are sig4 and sig5, while the element of gate02 is and, the input signals are sig6 and sig7, and the output signal is sig3. Also, it is shown that gate01 and gate02 are connected by a signal sig3.

Similarly, as shown in FIG.
A multiplier 51 that is a functional element, a signal line 52 to which a multiplier of an 8-bit width constant having a value of 130 (82h in hexadecimal notation) is input, and a signal line 53 to which an 8-bit width multiplicand a is input A circuit composed of a signal line 54 to which a multiplication result b having a 16-bit width is output is described as function description information as shown in FIG. 4B, and a function as shown in FIG. Converted to circuit information. Here, the distinction between the multiplier and the multiplicand is for convenience in the conversion processing.

In the function description information of FIG. 4B, the multiplicand a
Is a signal having an 8-bit width from 0 to 7 bits, a variable b is a signal having a 16-bit width from 0 bits to 15 bits, and the value of this variable b is represented by a multiplicand a and a value of 130 It is shown that the product is a product of a multiplier 130 and an 8-bit signal. In the functional circuit information of FIG. 4C, the identification name of the functional element is gate on the first line.
1 indicates that the functional element is a multiplier (multiplier), and in the description on the second and fourth lines, the signal indicated by the symbol i1 is the input signal a and the bit width is 8 bits. In the description on the third and fifth lines, the symbol i
The signal indicated by 2 is an input signal, which indicates that the bit width is 8 bits and the value is a constant of 130. In the description on the sixth line, the signal indicated by the symbol o is the output signal b and the bit width is It is shown to be 16 bits.

In the following description, for simplicity, functional description information, functional circuit information,
3A or 4 regardless of the distinction of the logic circuit information.
The contents of the information are represented by a schematic diagram as shown in FIG. Words such as a multiplier and a multiplicand are also used to indicate a signal representing these values or a multiplier or a multiplicand, etc., and a word of a circuit is also used to indicate information indicating a circuit, as long as it is not confused.

In the following description, the following notation is used. The number of (a−b + 1) bit widths from the ath bit to the bth bit (where a> b) counted from the least significant bit of the number X is expressed as X (a: b). The value of the a-th bit of the number X is represented as X (a). Further, the function is defined as follows.

For a signal Y expressed in k bits,
The number of bits having a value of 1 is defined as posibibits (Y), and the number of bits having a value of 0 is defined as negatives (Y). Also, counting from the least significant bit, 1
Is defined as effbitwidth (Y, P) until the number of bits becomes P (where P <k). Further, since the processing for obtaining the values of these functions can be easily realized, detailed description will be omitted.

Next, design processing performed by the automatic design system will be described. FIG. 5 is a flowchart showing the main routine of the design process. Step 41 is a process of inputting the function description information created by the function designer of the circuit based on the function specifications from the input device 11 and storing it in the circuit data storage unit 23. Not only the function description information but also input of, for example, functional circuit information or logic circuit information for a relatively simple circuit portion may be received.

In step 42, the function description information input in step 41 is interpreted to generate functional circuit information composed of functional elements and representing the circuit having the function indicated by the function description information in an internal representation form. This is a process of storing the data in the circuit data storage unit 23. Step 43 is a process of converting all the functional elements included in the functional circuit information into logic elements and storing the logic elements in the circuit data storage unit 23 as the logic circuit information. Further, with respect to the circuit including the multiplier, the circuit is optimized at the functional element level. The detailed processing content of this step 43 will be described later.

Step 44 is a process of allocating all the logic elements included in the logic circuit information to the mounted elements by element conversion processing based on predetermined conversion rule information, and storing the allocated elements in the circuit data storage unit 23 as mounted circuit information. . Also,
In the step 44, in the process of allocating the logic elements to the mounting elements, the optimization of the circuit at the logic element level is also performed.

Step 45 is a process of generating a circuit diagram and a netlist based on the mounted circuit information and the like and outputting the generated circuit diagram and netlist to the output device 13. Here, the netlist is, for example, information indicating a connection relation of the mounting elements in a circuit including the mounting elements. Note that the processes performed in step 42 and step 44 are respectively described below.
JP-A-3-15984 or US Pat.
Because it is similar to that shown in Japanese Patent No. 043914,
Detailed description is omitted.

In step 43, a process as shown in FIG. 6 is performed in detail. In step 81, one functional element included in the functional circuit information is selected. Step 8
In step 2 and step 83, it is determined whether the selected functional element is an adder or a multiplier. If the adder is an adder, step 84; if the multiplier, step 85; If it is neither a multiplier nor a multiplier, the process proceeds to step 86.

In each of steps 84 to 86, after the selected functional element is generated as circuit information of a circuit having the same function constituted by another functional element and / or a logic element, the process proceeds to step 87. . Step 8
At 7, it is determined whether or not a functional element is included in the circuit. If the functional element is included, the process returns to step 81 and the same processing is repeated. If it has been converted to a circuit, the process returns to the main routine.

Here, in the above steps 84 to 86, there is a case where the processing is not always converted into a circuit composed of only logic elements by a single process, but is converted once into a circuit including other functional elements. In this case, it is determined in step 87 that a functional element is included, and the same conversion process is repeatedly performed recursively, so that the circuit is finally converted into a circuit composed of only logic circuits. In particular,
For example, the multi-bit adder may
By repeating the conversion into an adder (functional element) with a smaller number of bits and a 1-bit adder (logical element), the circuit is converted into a circuit consisting of only a 1-bit adder. Further, the subtractor and the divider are converted into a circuit composed of functional elements such as an adder and a logic element in step 86, and then the adder is converted into a 1-bit adder in step 84. Is done. By performing the conversion process recursively in this manner, it is easy to simplify each process.

The multiplier for which "yes" is determined in step 83 and conversion is performed in step 85 has, for example, the functions shown in FIGS. 7 (a) to 7 (d). Each of the multipliers multiplies the multiplier represented by the signal having the width of m bits by the multiplicand represented by the signal having the width of n bits, and outputs a product P represented by the signal having the width of n + m bits. They are common in that they have a function, and differ in whether the input multiplier and multiplicand are constant A, constant B, variable X, or variable Y. Here, for the sake of simplicity, the constant A will be described as a positive number. In addition, when the constant A is a negative number, it can be easily dealt with by generating circuit information of a multiplication circuit for A 'in which the sign of the constant A is inverted and a circuit for inverting the sign of the multiplication result. The variable X will be described as being able to take a positive or negative value. However, if the variable X is limited to a positive number, 0 extension may be performed in sign extension for bit width adjustment described later.

Hereinafter, the conversion processing performed in step 85 will be described in detail with reference to the flowchart shown in FIG. 8 using the multiplier shown in FIG. 7 as an example. This process is a process of converting the multiplier into another functional element (a multiplier, an adder, or the like) or a circuit including a logic element. Step 100
In step 1, it is determined whether the multiplier and the multiplicand are both constants. If both are constants as shown in FIG. 7A, the process proceeds to step 1002 to calculate the product, and the values are set to 2 The signal is converted to a circuit that generates a signal represented by a base number. Specifically, when the multiplicand X = 4 and the multiplier A = 5, FIG.
As shown in the figure, the value 4 × 5 = 20 ('1010
0 ′) is output as P (4: 0), and a signal indicating the value 0 is converted to a circuit that outputs P (n + m−1: 5).

If it is determined in step 1001 that at least one of them is a variable, step 1003
Then, it is determined whether the multiplicand is a constant. If the multiplicand is a constant, the multiplier and the multiplicand are exchanged in step 1004, and then the process proceeds to step 1005. If the multiplicand is not a constant, the process directly proceeds to step 1005. Transition. That is, in the case of the multiplier as shown in FIG. 7B, it is converted into a multiplier as shown in FIG. 7C, and at least the multiplicand is always a variable.

In steps 1005, 1007, and 1009, it is determined whether the multiplier is a special constant, that is, whether the value is a power of 0, 1, or 2, and if it is 0, it is shown in FIG. 9B. To a circuit that outputs a signal indicating that the values of all bits are 0 (step 100)
6). If it is 1, the signal indicating the value of the multiplicand is output as it is as P (n-1: 0) as shown in FIG. 9C, and the signal having the value X (n-1) is output as P (n + m-1). :
n) is converted to a circuit that outputs (with sign extension) (step 1008). If it is a power of 2,
For example, when the multiplier is 8 (= 2 ³ ), FIG.
The signal indicating the value of the multiplicand is represented by P (n + 2: 3) as shown in FIG.
And outputs a signal having a value of 0 as P (2: 0)
And a signal whose value of each bit is X (n-1) is P
It is converted into a circuit that outputs (with sign extension) as (n + m-1: n + 3) (step 1010). Note that the variable X
Is limited to a positive number, the upper bits may be 0-extended without sign extension as described above.

In step 1011, it is determined whether the multiplier is 1 bit or more than 2 bits.
For example, if the bit is 1 bit as shown in FIG. 10A, the process proceeds to step 1012 to perform a process of converting into a circuit composed of AND circuits 132... 135 as shown in FIG. It is to be noted that the determination of 1 bit in step 1011 is limited only when the multiplier is a variable.
Because if it is a 1-bit constant, the above step 10
This is because “yes” is determined in 05 and 1007.
On the other hand, the determination as having two bits or more includes the case where the multiplier is a variable and the case where the multiplier is a constant.

Here, the above steps 1006, 100
The conversion of the circuits performed in steps 8, 1010, and 1012 is performed based on conversion rule information stored in the design processing storage unit 21 in advance. For example, in the conversion in step 1012, the conversion rule 1 shown in FIG.
The conversion is performed by the processing shown in FIG. First, in step 71, the conditional clause shown before “==>” in the conversion rule information is compared with the original circuit information, and if the conversion application condition is satisfied, the correspondence of the signal line name and the like is determined. I do.

In step 72, the circuit information indicating the multiplier which is the original functional element is deleted from the circuit data storage unit 23. In step 73, “==
Based on the circuit information indicating the functional element or the logical element in the result section indicated after the “>” and the association, the information indicating the circuit to be converted is generated and registered in the circuit data storage unit 23.

In step 74, it is determined whether an unprocessed functional element or logical element remains in the result section. If it is, the process returns to step 73. If not, the process returns to the original process. . The proof that conversion to a circuit equivalent to the original multiplier can be performed by the conversion rule 1 will be described later together with the proofs of other conversion rules. However, specific element conversion processing based on such conversion rule information is described in US Pat.
No. 4, the detailed description is omitted.
Further, the conversion rule information is actually represented in an internal representation format as shown in FIG. 10C, but in the following description, for the sake of simplicity, the conversion rule information is basically shown in FIGS. 10A and 10B. This will be described with reference to a schematic diagram as shown.

If it is determined in step 1011 that the multiplier is 2 bits or more, the process proceeds to step 1013, where another functional element (a multiplier or an adder having a smaller bit width) and / or A process of converting to a multi-bit-width multiplier composed of logic elements is performed. FIG. 12 is a flowchart showing the detailed processing performed in step 1013. In this processing, the number of partial products and the number of logical stages of the circuit for obtaining the sum of partial products are reduced as follows.

That is, when the multiplier is a constant, the partial product is reduced only for the bit whose value is 1 in the multiplier or a number obtained by logically negating all bits of the multiplier in order to reduce the partial product number. Convert to the desired circuit. In both cases where the multiplier is a constant and a variable, in order to reduce the number of logic stages of the circuit for calculating the partial product sum, the adder is converted into a circuit connected in a binary tree.

First, in step 141, it is determined whether or not the multiplier is a variable. If the multiplier is a variable, the process proceeds to step 142 since the multiplication between the variables is performed, and the conversion rule 2 shown in FIG. The circuit is converted into a circuit including two multipliers each having a bit width of about 1/2 of the multiplier. The conversion rule 2 is that the multiplier 191 that multiplies the multiplier Y having the bit width m by the multiplicand X having the bit width n and outputs the product P includes the lower K bits Y1 and the upper m−K bits Y2 of the multiplier Y. To the multiplicand X
192, 1 to obtain partial products P1, P2
93 and a circuit configured to add these partial products P1 and P2. However, since the circuit for performing the above addition needs to add only the bits that are equal to or more than the overlapping bits of the partial products P1 and P2, a ripper 194 that divides the upper n bits of the partial product P1 from the K bits lower than that is used. And a mixer 195 for outputting a signal R1 obtained by sign-extending the signal R1, and an adder 196 for adding the signal R1 and the partial product P2.

More specifically, the multiplier 192 converts the lower K bits Y1 = Y (K-1: 0) of the multiplier Y into the multiplicand X
(N-1: 0), and outputs a signal P1 (n + K-1: 0) having an n + K bit width as a partial product.
Further, the multiplier 193 calculates the upper mK bits Y2 of the multiplier Y.
= Y (m-1: K) is multiplied by the multiplicand X (n-1: 0), and as a partial product, a signal P2 (n +
m−K−1: 0).

The ripper 194 outputs the signal P1 (n + K-
1: 0) is converted to the upper n-bit signal P1 (n + K−
1: K) and a lower-K bit signal P1 (K-1: 0). The latter signal P1 (K-1: 0)
Is output as a signal P (K−1: 0) indicating the lower K bits of the product P. The mixer 195 combines an m-K bit width signal whose value of each bit is P1 (n + k-1) on the upper side of the signal P1 (n + K-1: K) output from the ripper 194 (signal P1). This is a circuit that outputs a signal R1 (n + m−K−1: 0) having an n + m−K bit width by sign-extending.

The adder 196 outputs the signal P2 (n + m-
K-1: 0) and the signal R1 (n + m-K-1: 0) are added, and the sum of the signals R2 (n
+ M−K−1: 0) as a signal P (n + m−1: K) indicating the upper n + m−K bits of the product P. When the bit width K, m−K of the multiplier input to the multiplier 192 and / or the multiplier 193 included in the circuit converted based on the conversion rule 2 is 2 or more (that is, the converted multiplier also functions In the case where the element is an element, when step 142 is executed in the processing of the next loop, it is converted into a circuit including a multiplier with a smaller bit width. Also,
When the bit width K or m−K of the multiplier becomes 1, it is converted into a circuit composed of an AND circuit (logic element) in the processing of step 1012 (FIG. 8).

Here, the value of K is a minimum integer equal to or greater than m / 2 or a maximum integer equal to or less than m / 2, that is, K and m
Addition is performed by setting the difference m−2K to the integer so that the absolute value of the difference m−2K is minimized, or by setting K or m−K to be a minimum power of 2 that is not less than m / 2. The number of logic stages can be reduced when a circuit for obtaining a partial product sum is formed by connecting the devices in a well-balanced binary tree.

FIG. 14 is a block diagram showing a configuration for performing the processing of step 142, focusing on its function. The input unit 241 reads circuit information indicating the multiplier 191 as the original functional element from the circuit data storage unit 23, and
The information indicating that the input of 91 is an m-bit multiplier Y and an n-bit multiplicand X is output to the multiplier division means 242. The output of the multiplier 191 is the product P of m + n bits.
Is output to the division operation circuit generation means 244.

The multiplier dividing means 242 first obtains the value of K for dividing the multiplier Y, and outputs information indicating the lower K-bit signal Y1, the multiplicand X, and the partial product P1 of the multiplier Y, and the higher order of the multiplier Y. The multiplication module generation unit 24 multiplies the m−K bit signal Y2, the multiplicand X, and information indicating the partial product P2 by
Output to 3. In addition, information indicating each of the partial products P1 and P2 is output to the division operation circuit generation unit 244. Here, the names P1 and P2 of the partial products are assigned by an assigning means (not shown).

The multiplication module generating means 243 outputs the signal Y
A multiplier 19 for multiplying the multiplicand X by 1 to obtain a partial product P1
2 and the signal Y2 are multiplied by the multiplicand X to generate information indicating the multiplier 193 for obtaining the partial product P2.
5 is output. The division operation circuit generation means 244 calculates the partial product P1, P2 based on the information indicating the product P and the information indicating the product P.
A ripper 194 that outputs the lower K bits of the partial product P1 as the lower K bits of the product P and outputs the sum of the upper n−K bits of the partial product P1 and the partial product P2 as the upper n + m−K bits of the product P; 195 and adder 196
Is output to the output unit 245.

The output unit 245 stores the circuit information indicating the converted circuit output from the multiplication module generation unit 243 and the divided operation circuit generation unit 244 in the circuit data storage unit 23. Incidentally, in the case of a multiplier for multiplying variables, not only the division as described above, but also a general-purpose multiplier registered in a library or a 2-bit multiplier as in the conventional automatic design system. The circuit may be converted to a circuit to which the booth recoding method is applied.

If it is determined in step 141 that the multiplier is a constant multiplier A, the process proceeds to step 143, and the number po of bits whose value in the multiplier A is 1 is set to po.
It is determined whether or not sibits (A) is 2 or less, and if it is 2 or less, the process proceeds to step 144. (Note that posi
If bits (A) is 1, the processing is performed in the step 1008 or 1010, so that it is determined that it is 2 or less only in the case of 2. Here, in step 143, the value of m may be determined. posibi
If ts (A) is 2, a circuit that adds two values obtained by shifting the multiplicand X in accordance with the bit position, that is, a circuit that obtains a partial product only for bits having a value of 1 can be configured. Such a circuit may be generated in a single process, but here, in order to simplify each process by using a recursive process, an m-1 bit multiplier is provided. , The multiplier A is divided into the most significant 1 bit and the lower m-1 bits, and the multiplicand X and the lower m-1 of the multiplier A are divided.
The product is converted to a circuit that adds the product of the bit and the value obtained by shifting the multiplicand X. However, if the most significant bit of the multiplier A is 0, it is only necessary to set the most significant bit of the product P to 0, so that a circuit for addition or the like is not required.

Therefore, in step 144, as shown in more detail in FIG.
It is determined whether or not the value of the most significant bit of is “1”. If the value is “1”, the process proceeds to step 162, and FIG.
While the conversion rule 3 (a) shown in FIG. 7 is applied, if the value is 0, the process shifts to step 163 to apply the conversion rule 3 (b) shown in FIG.

The conversion rule 3 (a) indicates that the multiplier 151 is to be converted into a circuit composed of a multiplier 152, a ripper 153, and an adder 154. The multiplier 152 calculates the lower m-1 bits A3 = A (m−
2: 0) is multiplied by the multiplicand X (n−1: 0) to obtain n + m−
A 1-bit partial product P3 (n + m-2: 0) is obtained.

The ripper 153 has a partial product P3 (n + m−
2: 0) is replaced by the upper n bits P3 (n + m-2: m-1)
And lower m-1 bits P3 (m-2: 0).
The adder 154 calculates the above P3 (n + m-2: m-1) and the multiplicand X (n-1: 0) (logically, as a partial product,
The product of the most significant bit of the multiplier A and the multiplicand X (n−1: 0)) is added.

When this processing is performed, the value of posits (A3) for the multiplier 152 becomes 1
Therefore, the step 1 in the processing of the next loop
The processing of 008 or 1010 (FIG. 8) is performed. Here, the conversion rule 3 (a) is stored in the design processing storage unit 21 in an internal representation format as shown in FIG. 17A, for example. In the figure, “Gate” in the conditional clause shown before “==>” corresponds to the multiplier 151 in FIG. Also, “Gate1” to “Gate4” of the result clauses shown after “==>” are the multipliers 1 respectively.
52, the ripper 153, or the adder 154.

The conversion rule 3 (b) is based on the multiplier 151
With a multiplier 155, and the lower m-1 bits A of the multiplier A
3 = A (m−2: 0) is multiplied by the multiplicand X (n−1: 0), and the obtained partial product of n + m−1 bits width is set to the lower n + m−1 bits P (n + m−2: 0) and outputs the value X (n-1) as the most significant bit P (n
+ M-1). That is, in this case, conversion to a circuit including a multiplier having a small bit width can be performed without increasing the number of partial products. When this process is performed,
Since the value of posibibits (A3) for the multiplier 152 remains 2, the step 144 is executed again in the processing of the next loop, and is converted to a circuit including a multiplier with a smaller bit width in the step 163. Alternatively, in step 162, the value is converted to a circuit including a multiplier having one bit having a value of one.

Note that instead of dividing the multiplier A into the most significant 1 bit and the lower m-1 bits as described above, the multiplier A is divided into the upper m-1 bits and the least significant bit. Is also good. FIG. 18 is a configuration diagram showing the configuration for performing the process of step 144, focusing on its function.

The input means 251 reads circuit information indicating the multiplier 151 as the original functional element from the circuit data storage unit 23, and the input of the multiplier 151 is an m-bit multiplier A,
Information indicating that it is an n-bit multiplicand X and that the output is a product P of m + n bits is output to the most significant bit separating means 252. The most significant bit separation means 252
The multiplier A is separated into the most significant bit A (m−1) and the lower bits A (m−2: 0), and
(M-1), information indicating the multiplicand X and the product P are output to the bit value determination means 253, and the lower bits A
(M−2: 0) and information indicating the multiplicand X are output to the multiplication module generation means 254.

The bit value determining means 253 determines whether the value of the most significant bit A (m-1) is 1 or 0, and according to the determination result, the lower bit A (m-2: 0) Is multiplied by the multiplicand X and the partial product P3 or the product P (n + m−
2: 0) is output to the multiplication module generation means 254. Further, the most significant bit A (m-
If the value of 1) is 1, information indicating the multiplicand X, the product P, and the partial product P3 is output to the addition shift operation circuit generating means 255. If the value of 0 is 0, the most significant bit of the product P is output. Information indicating P (n + m-1) and information indicating the value of the most significant bit X (n-1) of the multiplicand X are output to 256.

The multiplication module generating means 254 calculates the multiplier A
Multiplying the multiplicand X by the lower bit A (m−2: 0) of the multiplicand X and generating information indicating the multipliers 152 and 155 that output the partial product P3 or the product P (n + m−2: 0), and output means 257 Output to Addition shift operation circuit generation means 255
When the value of the most significant bit A (m-1) of the multiplier A is 1, information indicating the partial product P3, information indicating the multiplicand X,
And the lower order m of the partial product P3 based on the information indicating the product P
The bits are output as lower m-1 bits P (m-2: 0) of the product P, and the sum of the upper n bits of the partial product P3 and the multiplicand X is calculated as the upper n + 1 bits P (n + m-1: m) of the product P.
-1) ripper 153 and adder 15
4 is generated and output to the output unit 257.

On the other hand, when the value of the most significant bit of the multiplier A is 0, the circuit generating means 256 outputs a value X (n-1) as the most significant bit P (n + m-1) of the product P. Is generated and output to the output unit 257. The output unit 257 stores the circuit information indicating the converted circuit output from each of the units 254 to 256 in the circuit data storage unit 23.

If it is determined in step 143 that posibibits (A) in the constant multiplier A is greater than 2, the flow shifts to step 145, where p
Osibits (A) is the number ne of bits having a value of 0
It is determined whether or not greater than gabits (A) +1. In step 145, posibibits (A) is ne
If it is determined that the value is not larger than gabits (A) +1, the process proceeds to step 146 to apply the conversion rule 2 shown in FIG. 13 as in step 142 when the multiplier is a variable. The multiplier A is divided and converted into a circuit including two multipliers. However, as compared with the case where the multiplier is a variable, the value of K for dividing the multiplier A is
Is not about 1/2 of the bit width m of L, for example, L is pos
When the minimum integer of ibits (A) / 2 or more is used, a value effbitwidth (A, L) is used such that the number of 1 bits counted from the lower bits of the multiplier A is L. Note that the value of L is equal to pos, similarly to the value of K.
ibits (A) / 2 or a maximum integer less than or equal to 2
It may be a power of.

The processing in step 146 is performed once or two times.
The multiplier A is divided by performing the
As described above, in the multiplier in which bits (A) is 2 or less, a circuit for obtaining a partial product for only the bit whose value is 1 is generated by step 1006 in FIG. 8 or step 144 in FIG. Is divided so that the number of bits having a value of 1 is substantially equal to each other, so that the number of logic stages in the case where a circuit for obtaining a partial sum of products by connecting adders in a well-balanced binary tree is suppressed. be able to.

If posibibits (A) is 3, the number of logical stages becomes 2 no matter how the multiplier A is divided. Therefore, it is determined in step 143 whether posibibits (A) is 3 or less. Step 144 also in case of 3
May be used to divide the multiplier A into one most significant bit and lower m-1 bits. The configuration for performing the process of step 146 is the same as the configuration of FIG. 14 corresponding to step 142 except that the method of determining the value of K for dividing the multiplier A is different.

On the other hand, at step 145,
When it is determined that s (A) is larger than negatives (A) +1, the process proceeds to step 147, and FIG.
The conversion rule 4 shown in (1) is applied, and the value obtained by taking the logical negation of all bits of the multiplier A is set as the multiplier A0, and is converted into a circuit including a multiplier for obtaining the product of the multiplier A0 and the multiplicand X. The multiplier included in the circuit after the conversion performs a logical negation to obtain the value of the positives (A) and the negative
Since the value of s (A) is reversed, in the next loop processing,
For example, "no" is determined in step 145, and conversion for dividing the multiplier A0 is performed in step 146. Therefore, the number of bits having a value of 1 is smaller than the original multiplier A, and a circuit for obtaining a partial product for only the bit having a value of 1 is generated. The number of logic stages of the circuit for calculating the sum can be reduced.

However, in order to find the product of the multiplier A and the multiplicand X, it is necessary to correct the product of the multiplier A0 and the multiplicand X. The conversion rule 4 indicates that conversion is performed to a circuit including a circuit for the correction. That is, FIG.
, 171 is a multiplier before conversion. Multiplier 1
72 multiplies the multiplicand X by the multiplier A0 and outputs a product P0 (= XA0) having an n + m bit width.

Inverter 178 performs a logical negation on all bits of product P0 and outputs a signal having a width of n + m bits. The mixer 173 combines the multiplicand X with the upper n bits and the m-bit width signal having a value of 0 as the lower m bits to obtain n + m
A bit width signal R2 (= X · 2 ^m ) is output.

The mixer 174 sets the value of each bit to the multiplicand X
The signal of m bit width which is the value of the most significant bit X (n-1) is the upper m bits, and the logical negation of the multiplicand X is the lower n bits.
The signals are synthesized as bits and a signal having a width of n + m bits is output. The inverter 177 performs a logical negation of all bits of the output from the mixer 174, and outputs a signal R3 having an n + m bit width.
(= −X−1) is output.

The adder 175 receives the signal R2, the signal R3, and the carry-in having a value of 1 as inputs, and inputs n +
The sum R4 (= X · (2 ^m −1)) of m bit width is output. Adder 176 receives as inputs the logical negation of product P0, sum R4, and the carry-in value of 1, and n +
The m-bit width sum R5 (= XＸ (2 ^m -1) -P0) is expressed as
Output as product P.

Note that the condition for determination in step 145 is that positives (A)> negatives
Not limited to (A) +1, but posibibits (A) ≧ m / 2
And so on. Further, in consideration of the scale of each circuit for the above correction, the process may proceed to step 147 only when the value of posibibits (A) is further large.

FIG. 20 is a block diagram showing the configuration for performing the processing of step 147, focusing on its function. The input unit 231 reads circuit information indicating the multiplier 171 as the original functional element from the circuit data storage unit 23, and
The input of 71 is an m-bit multiplier A and an n-bit multiplicand X
Is output to the logical negation unit 232. Further, information indicating the multiplicand X and the multiplier 17
The information indicating that the output of 1 is the product P of m + m bits is output to the logical NOT operation circuit generating means 234.

The logical negation means 232 takes the logical negation of all bits of the multiplier A and outputs the multiplier A0.
9 is output to the output unit 235, and the information indicating the multiplier A0, the information indicating the multiplicand X, and the information indicating that the result of multiplication of the multiplier A0 and the multiplicand X is the product P0 are output to the multiplication module generation unit. 233. The information indicating the product P0 is also output to the logical NOT operation circuit generating means 234.

The multiplier module generating means 233 calculates the multiplier A
The information indicating the multiplier 172 for obtaining the product P0 of 0 and the multiplicand X is generated and output to the output unit 235. Based on the product P0 and the multiplicand X, the logical NOT operation circuit generating means 234 calculates the product R4 of the multiplicand X and 2 ^m −1 (= X · (2
^m- 1)) and a signal R5 (= X · (2
By calculating ^m- 1) -P0), information indicating the circuits 173 to 178 that correct the product P0 and output the product P is generated and output to the output unit 235.

The output means 235 includes the means 232 to 234
Is stored in the circuit data storage unit 23, which indicates the converted circuit output from the circuit. Hereinafter, it will be proved by using mathematical expressions that the circuit can be converted into a circuit equivalent to the original multiplier by the conversion rules 1 to 4. <Conversion Rule 1> (FIG. 10) In FIG. 10, 132, 133,..., 13
4, 135 are multipliers Y of 1-bit variable, respectively.
(0) and multiplicands X (0), X (1) each having a 1-bit width,
..., X (n−2), X (n−1) and their logical products P (0), P (1),.
2) An AND circuit that takes P (n-1). Y (0)
= 0 or 1, so Here, since Y (0) and _Pi are both 1 bit, X
_i · Y (0) = X _i and Y (0).

Therefore, P (i) = X (i) and Y (0) (0 ≦ i
≦ n−1) P (n) = 0 <Conversion Rule 2> (FIG. 13) P = X · Y = X · Y (m−1: 0) = X · ： Y (m−1: K) · 2 ^K + Y (K−1: 0)｝ = XY (m−1: K) · ^2K + XY (K−1: 0) = P2 (n + m−K−1: 0) · ^2K + P1 ( n + K-1: 0) = P2 (n + m-K-1: 0) ^2K + P1 (n + K-1: K) ^2K + P1 (K-1: 0) = P2 (n + m-K-1: 0) ^2K + R1 (n + m-K-1: 0) ^2K + P1 (K-1: 0) (where R1 (n + m-K-1: n) = 0), R1 (n-1: 0) ) = P1 (n + K-1: K)) = {P2 (n + m-K-1: 0) + R1 (n + m-K-1: 0)}. ^2K + P1 (K-1: 0) = R2 (n + m) -K-1: 0) · 2 K + P1 (K-1: 0) Thus, P (K-1 0) = P1 (K-1: 0) P (n + m-1: K) = R2 (n + m-K-1: 0) Note that it is also the case multiplier is a multiplier A constant.

<Conversion Rule 3 (a)> (FIG. 16A) P = X · A = X · A (m−1: 0) = X · ｛A (m−1) · 2 ^m−1 + A (M−2: 0)｝ = X · A (m−1) · 2 ^m−1 + X · A (m−2: 0)... (∵A (m−1) = 1) = X · 2 ^{m −1} + P3 (n + m−2: 0) = X · 2 ^m−1 + P3 (n + m−2: m−1) · 2 ^m−1 + P3 (m−2: 0) = R1 (n: 0) · 2 ^{m -1} + P3 (m-2: 0) Therefore, P (m-2: 0) = P3 (m-2: 0) P (n + m-1: m-1) = R1 (n: 0) <Conversion Rule 3 (B)> (FIG. 16 (b)) P = X · A = X · A (m−1: 0) = X · ΔA (m−1) · 2 ^m−1 + A (m−2: 0) ＝= X · A (m−2: 0) ∵ (ｍA (m−1) = 0) = P3 (n + m−2: 0) Therefore, P (n + m−2: 0) = P3 n + m-2: 0) P (n + m-1) = 0 < conversion rule 4> (Fig. 19) or less, represented by the logic NOT number of all the bits of the number Z of a plurality of bits ^* Z.

Regarding the constant A, −A = ^* A + 1−2 ^m ← → ^* A + 1 = 2 ^m− A
Holds, and for the n-bit number X, (two's complement of X) = ^* X + 1 = −X. Therefore, P = X · A = X · (2 ^{m− *} A−1) = X · 2 ^m− XX− ^* A = X · 2 ^m + (2's complement of X) + (X · ^* A X1 = X · 2 ^m + (2's complement of X) and P0 = X · ^* A, X · A = X1 + (2's complement of P0) = X · 2 ^m + (X X · A = X · 2 ^m + ^* X + 1 + ^* P0 + 1 The first term X · 2 ^{m in the above} equation is obtained as R2 by the mixer 173.

The second term X is sign-extended by the mixer 174 and the inverter 177, logically negated, and R
It is required as 3. The fourth term P0 is obtained by the multiplier 172 and the inverter 178. In addition, the first term X
The addition of 2 ^m , the second term X, and the third term or the fifth term 1 is obtained by the adder 175 as R4. XA is n +
Since the number of bits is m, the digit of the (n + m + 1) th bit of the addition result need not be considered.

The addition of R4, the fourth term P0 in the preceding equation, and the fifth or third term 1 is obtained as R5 by the adder 176. Since X · A is an n + m bit number,
The digit of the (n + m + 1) th bit of the addition result need not be considered. Therefore, P = XA = P (n + m-1: 0) = R5 (n + m-1: 0) According to the automatic logic circuit design system of the first embodiment, the signal is input to the multiplier as described above. If the multiplier is a constant,
If the total number of bits having a value of 1 in the multiplier is 3 or more, the circuit for obtaining the partial sum of products is divided by dividing the multiplier so that the number of bits having a value of 1 becomes equal. It is configured in a tree shape, and the number of logical stages of addition can be reduced, and the multiplication speed can be increased.

If the total number of bits having a value of 1 is 2 or less, a circuit for obtaining a partial product only for a bit having a value of 1 is constituted, so that the number of partial products can be reduced. The circuit area can be reduced. If the total number of bits having a value of 1 is large, a multiplier that multiplies the logical negation of the multiplier by the multiplicand and a circuit that corrects the multiplication result are configured. With this configuration, the number of partial products and the circuit area can be reduced. (Embodiment 2) Step 10 of FIG.
13, that is, a modification of the configuration that performs the same processing as in steps 141 to 147 of FIG. 12 will be described with reference to FIG. 21.

In the figure, an input means 2901 reads circuit information indicating a multiplier which is an original functional element from a circuit data storage unit 23, and the input of the multiplier is an m-bit multiplier A
Alternatively, information indicating that Y is an n-bit multiplicand X and that the output is a product P of m + n bits is output to the logical negation determining means 2902. Logical NOT determining means 29
02: Posibits (A) is negative
(A) It is determined whether or not it is larger than +1. If it is larger, information indicating the multiplier A or Y, the multiplicand X, and the product P is output to the logical negation means 2904. Is output to the multiplier bit width determination means 2903.

The multiplier bit width determining means 2903 determines whether the multiplier is a variable or a constant and
(A) is 3 or more or a constant and po
It is determined whether or not sibits (A) is 2 or less. In the case of the former two, the information indicating the multiplier A or Y, the multiplicand X, and the product P is output to the multiplier dividing means 2907. Outputs information indicating the multiplier A, the multiplicand X, and the product P to the multiplier most significant bit separating unit 2909.

The other means 2904 to 2913 are shown in FIG.
Since they have the same functions as those of the units 4, 18, and 20 except that the information transmission path is slightly different, the description is omitted. (Embodiment 3) Step 10 of FIG.
Another example of the process performed in step 13 will be described with reference to FIG.

In this embodiment, when the bit width of the multiplier is 3 or more, the multiplier is divided into approximately 1/2 bit width regardless of whether the multiplier is a constant or a variable. When the bit width of the multiplier is 2, if the multiplier is a constant, the above conversion rule 3 (a) (b) (FIGS. 15 and 16) is applied, and only the bit whose value is 1 is applied. If the multiplier is a variable, the multiplier is 1
A circuit comprising two multipliers of bits is constructed.

First, at step 211, it is determined whether or not the bit width of the multiplier is 3 or more.
In step 212, the conversion rule 2 (FIG. 19) is applied to convert the multiplier into a circuit including two multipliers having a bit width of about 1/2. If the bit width of the multiplier is not 3 or more, the process shifts to step 213 to determine whether the multiplier is a constant. If the multiplier is a constant, step 2
14, the conversion rules 3 (a) and (b) (FIG. 15,
16) is applied to convert to a circuit that obtains a partial product only for a bit having a value of 1 in the multiplier.

On the other hand, if the multiplier is a variable, step 215
Then, the conversion rule 5 shown in FIG. 23 is applied. The conversion rule 5 is that the multiplier 221 includes the multiplier 222 and the multiplier 22
3, a ripper 224, a mixer 225, and an adder 226.
This indicates that the data is converted into a circuit composed of

The multiplier 222 multiplies the lower one bit A (0) of the multiplier A (1: 0) by the multiplicand X (n−1: 0) to obtain a partial product R1 (n: 0) having an n + 1 bit width. Ask for.
The multiplier 223 outputs the upper one bit A of the multiplier A (1: 0).
(1) is multiplied by the multiplicand X (n-1: 0) to obtain a partial product R2 (n + 1: 1) having an n + 1 bit width. Ripper 22
4 represents the partial product R1 (n: 0) as the upper n bits R1
(N: 1) and lower one bit R (0),
(0) is output as the product P (0).

The mixer 225 outputs a signal R3 (n + 1: 1) obtained by sign-extending the above R1 (n: 1) by one bit to the upper side.
1) is output. The adder 226 outputs the signal R3 (n +
1: 1) and the partial product R2 (n + 1: 1), and the sum R
4 (n + 1: 1) is output as a product P (n + 1: 1). The proof that the conversion rule 5 can be converted into a circuit equivalent to the original multiplier 221 will be shown below. P = X · A = X · A (1: 0) = X · {A (1) · 2 + A (0)} = X · A (1) · 2 + X · A (0) = R2 (n: 0) · 2 + R1 (n: 0) = R2 (n: 0) · 2 + R1 (n: 1) · 2 + R1 (0) = R2 (n: 0) · 2 + R3 (n: 0) · 2 + R1 (0) (where R3 (N) = 0), R3 (n-1: 0) = R1 (n: 1)) = R4 (n: 0) .2 + R1 (0) Therefore, P (0) = R1 (0) P (n + 1: 1) = R4 (n: 0) When this process is performed, the multipliers 222 and 223 perform the next loop process because the multiplier has a bit width of 1 bit. Is converted into a circuit composed of an AND circuit.

According to the third embodiment, if the bit width of the multiplier of the multiplier is 3 or more, the circuit for obtaining the partial sum of products by dividing the multiplier can be formed in a binary tree. And the multiplication speed can be increased. Further, if the bit width of the multiplier is 2 or less and the multiplier is a constant, a circuit for obtaining a partial product only for bits having a value of 1 in the multiplier can be generated, thereby reducing the number of partial products. The circuit area can be reduced. (Embodiment 4) Step 144 (FIG. 12) in the first embodiment and step 214 (FIG. 2) in the third embodiment
In 2), in the multiplier A, posibibits
(A) = 2 or a multiplier having a bit width of 2
Although the example in which the conversion rule 3 for dividing the most significant bit of the multiplier A is applied has been described, the conversion rule 6 for dividing into the predetermined K-th bit, the higher-order bits, and the lower-order bits may be applied. Good. Also, conversion rule 6 may be applied instead of conversion rule 2 in step 146 (FIG. 12) or step 212 (FIG. 22). In this case, the determination in step 143 or 211 can be omitted.

That is, as shown in FIG. 24, first, in step 311, it is determined whether or not the value of the K-th bit A (K−1) of the multiplier A is 1, and if it is 1, the process proceeds to step 312. The process is shifted to the conversion rule 6 shown in FIG.
While applying (a), if it is 0, step 31
3 and the conversion rule 6 (b) shown in FIG. The value of K may be set, for example, in the same manner as in the first embodiment.

The conversion rule 6 (a) indicates that the multiplier 281 is converted into a circuit composed of multipliers 282 and 283, mixers 284 to 287, and an adder 288. The multiplier 282 calculates the lower K−1 in the multiplier A.
The multiplicand X (n-1: 0) is multiplied by the bit A5 (K-2: 0) = A (K-2: 0) to obtain a partial product P5 (n + K-2: 0) having an n + K-1 bit width. Ask.

The multiplier 283 calculates the upper m−
Multiply the multiplicand X (n-1: 0) by K bits A6 (mK-1: 0) = A (m-1: K) to obtain a partial product P6 (n + m-K- 1: 0). The mixer 284 outputs a signal R1 (n + m−) obtained by sign-extending the partial product P5 (n + K−2: 0) by m−K + 1 bits to the upper side.
1: 0) is output.

The mixer 285 synthesizes a signal R2 (n +
m-1: 0). Mixer 286 provides multiplicand X
A signal R3 (n + K-2: 0) obtained by synthesizing a K-1 bit width signal having a value of 0 is output below (n-1: 0). The mixer 287 outputs the signal R3 (n + K−2: 0).
R4 obtained by sign-extending the upper side by m−K + 1 bits
(N + m-1: 0) is output.

The adder 288 outputs the signal R1 (n + m−
1: 0), a signal R2 (n + m-1: 0), and a signal R4
(N + m-1: 0) and the product P (n + m-1:
0) is output. The conversion rule 6 (b) indicates that the multiplier 2
81, multipliers 282 and 283 and mixers 284 and 28
7 and a circuit composed of an adder 289.

The multipliers 282 and 283 and the mixers 284 and 287 are the same as those shown in the conversion rule 6 (a). The adder 289 outputs the signal R1 (n + m−
1: 0) and the signal R2 (n + m-1: 0) are added to output a product P (n + m-1: 0). Conversion rule 6 above
The proof that (a) and (b) can be converted into a circuit equivalent to the original multiplier 281 will be shown below.

<Conversion Rule 6 (a)> Since A (K−1) = 1, P = X · A = X · ｛A (m−1: K) · 2 ^K + A (K−1) · 2 ^K-1 + A (K-2: 0) ＝ = X · A (m−1: K) · 2 ^K + X · 2 ^K-1 + X · A (K−2: 0) = X · A6 (m− K-1: 0) · 2 K + X · 2 K-1 + X · A5 (K-2: 0) = P6 (n + m-K-1: 0) · 2 K + R3 (n + K-2: 0) · 2 K ^{-1 + P 5 (n + K} -2: 0) = R2 (n + m-1: 0) · 2 K + R4 (n + m-1: 0) · 2 K-1 + R1 (n + m-1: 0) < conversion rule 6 (b )> A (K-1) = 0, then P = XA = X.DELTA.A (m-1: K) ^2K + A (K-1) ^2K-1 + A (K-2 : 0)} = X · A (m-1: K) · 2 K + X · A (K-2: 0) = X · A6 (m-K-1: 0 ^{· 2 K + X · A5 (} K-2: 0) = P6 (n + m-K-1: 0) · 2 K + P5 (n + K-2: 0) = R2 (n + m-1: 0) · 2 K + R1 (n + m -1: 0) (Embodiment 5) In step 144 (FIG. 12) in the first embodiment or step 214 in the third embodiment, a multiplier whose posbits (A) = 2 or the bit width is 2 in the multiplier A Has been described above, the conversion rule 3 shown in FIG. 26 may be applied.

The conversion rule 7 is that the multiplier 271 is connected to the multiplier 2
72, a mixer 273, 274, and an adder 275. The multiplier 272 generates a multiplier A for a digit K (0 ≦ K ≦ m−1) of a bit having a value of 1 in the multiplier A (m−1: 0).
The multiplicand X is multiplied by a multiplier A7 (m-1: 0) having an m-bit width in which the K-th bit of (m-1: 0) is set to 0, and a product P7
(N + m-1: 0) is output.

The mixer 273 combines the multiplicand X with the upper n bits and the K-1 bit width signal having a value of 0 as the lower K-1 bits, and generates an n + K-1 bit width signal R1 (n
+ K-2: 0). The mixer 274 sets the value of each bit to R1 (n + K-2: 0) above the signal R1 (n + K-2: 0).
A signal having a width of (m + K + 1), which is (n + k-2), is synthesized (the signal R1 is sign-extended) to output a signal R2 (n + m-1: 0) having a width of n + m.

The adder 275 calculates the product P7 (n + m−1:
0) and the signal R2 (n + m-1: 0) are added to obtain n + m
The sum of bit widths R3 (n + m-1: 0) is multiplied by the product P (n + m-
1: 0). Proof that the conversion rule 7 can be converted to a circuit equivalent to the original multiplier 271 will be shown below. A7 (m-1: 0) = A (m-1: 0) -2
Since a ^{K-1, P = X ·} A = X · {A7 (m-1: 0) +2 K-1} = X · 2 K + X · A7 (m-1: 0) = R1 (n + K-2 : 0) + P7 (n + m-1: 0) = R2 (n + m-1: 0) + P7 (n + m-1: 0) = R3 (n + m-1: 0) In this case, the multiplier A7 ( m-
The bit width of (1: 0) is equal to the bit width of the multiplier A (m−1: 0) input to the multiplier 271, but the number of bits having a value of 1 decreases, so this process is repeated. Eventually, in step 1008 or 10
10 (FIG. 8) is performed.

FIG. 27 is a configuration diagram showing a configuration for performing the process according to the above conversion rule 7 focusing on its function. The input unit 261 reads circuit information indicating the multiplier 271 as the original functional element from the circuit data storage unit 23,
The information indicating that the input of 71 is an m-bit multiplier A and an n-bit multiplicand X is output to the signal generation means 262. Further, information indicating the multiplicand X and the multiplier 271
Is output to the arithmetic circuit generating means 264, indicating that the output is a product P of m + n bits.

The signal generation means 262 includes information indicating a multiplier A7 in which the value of the K-th bit (0 ≦ K ≦ m−1) whose value in the multiplier A is 1 is set to 0, information indicating a multiplicand X,
The result indicating that the multiplication result is the product P7 is output to the multiplication module generation means 263. Further, the information indicating the value of K and the information indicating the product P7 are output to the arithmetic circuit generating means 264.

The multiplication module generation means 263 generates information indicating the multiplier 272 for obtaining the product P7 of the signal X and the signal A7, and outputs the information to the output means 265. The arithmetic circuit generator 264 outputs information indicating the mixers 276 and 274 and the adder 275 based on information indicating the value of K, information indicating the product P7, information indicating the multiplicand X, and information indicating the product P. Output to means 265.

The output unit 265 stores the circuit information indicating the converted circuit output from the multiplication module generation unit 263 and the arithmetic circuit generation unit 264 in the circuit data storage unit 23.
To be stored. (Embodiment 6) Another example of the conversion rule 4 and a configuration of a multiplier generated by the conversion rule will be described.
Here, for the sake of simplicity, the case where the variable X is a positive number is shown. However, if the variable X can take a positive or negative value, the sign is extended and the logical negation or And then extend the sign.

FIGS. 28A to 28C show the result clauses of the conversion rule and the configuration of the multiplier to be generated. Note that the components in FIG. 28 are the same as those shown in FIG. FIG.
The multiplier of (a) inputs a signal of value 1 as an m-bit signal input to the mixer 173 instead of inputting a signal of value 1 as carry-in of the adder 175. .

The multiplier shown in FIG. 28 (b) replaces the input of the signal of value 1 as the carry-in of the adder 176,
Similarly, a signal having a value of 1 is input as an m-bit signal input to the mixer 173. When the bit width m of the multiplier is 2 or more, as shown in FIG. 28 (c), both adders 175 and 176 input the signal of value 1 to the mixer 173 instead of carry-in input. Alternatively, a signal having a value of 2 may be input as an m-bit signal.

As described above, the operation for correcting the product P0 to obtain the product P can be variously modified. In any of the above multipliers, the multiplier included therein multiplies the multiplier A0 and the multiplicand X by setting the value obtained by logically negating all the bits of the multiplier A as the multiplier A0.
Even when it (A) is greater than m / 2, the partial product number can be reduced to m / 2 or less, so that the circuit area can be reduced and the multiplication speed can be improved.

In each of the above embodiments, the circuit information stored in the circuit data storage unit 23 includes a functional element,
An example in which a data expression representing a circuit is used with an emphasis on an input / output relationship between elements with a focus on an element such as a logic element or a mounting element has been described.
That is, even when a data expression centering on a signal is used, a circuit conversion process based on a similar conversion rule can be performed.

The conversion process is not limited to the circuit conversion process based on the above conversion rules, but may be a process of sequentially generating and registering each part of the circuit data to be generated and registered in a specific order. In addition, although only the case where the product P of the multiplier of m-bit width and the multiplicand of n-bit width is n + m-bit width has been described, more generally, the product of an arbitrary bit width can be easily obtained. For example, if the bit width 1 of the product P is smaller than n + m, it is sufficient to take l bits from the lower order of the multiplication result. Alternatively, it may be extended by 0.

[0122]

As described above, according to the present invention,
Since a partial product operation circuit or the like for obtaining a partial product with the multiplicand is formed only for bits having a value of 1 in the multiplier, the circuit scale can be reduced and the multiplication speed can be easily increased. In addition, since the partial product-sum operation circuit is formed so that the number of bits having the value of 1 is substantially equal to each other and the partial product-sum operation is added, the partial product-sum operation circuit is well-balanced in a binary tree shape. This makes it easy to increase the multiplication speed by reducing the number of logic stages in the circuit.

Further, even when the number of bits having a value of 1 in the multiplier is large, a circuit for multiplying the logical negation of the multiplier is formed. Therefore, a high-speed multiplier or a multiplier having a small circuit size is required. There is an effect that the configuration becomes easy.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a hardware configuration of an automatic design system according to a first embodiment.

FIG. 2 is an explanatory diagram showing a configuration of the storage device.

FIG. 3 is an explanatory diagram showing an example of data representing a circuit stored in a circuit data storage unit.

FIG. 4 is an explanatory diagram showing an example of functional circuit information and functional description information.

FIG. 5 is a flowchart of a main routine showing processing of the logic design system.

FIG. 6 is a flowchart showing a detailed process of step 43 in FIG. 5;

FIG. 7 is an explanatory diagram showing an example of a multiplier as a functional element.

FIG. 8 is a flowchart showing a detailed process of step 85 in FIG. 6;

FIG. 9 shows steps 1002 and 100 in FIG.
FIG. 6 is a circuit diagram illustrating an example of a circuit generated in 6, 1008, and 1010.

FIG. 10 is an explanatory diagram showing a conversion rule 1;

FIG. 11 is a flowchart showing an example of a specific conversion process.

FIG. 12 is a flowchart showing a detailed process of step 1013 in FIG. 8;

FIG. 13 is an explanatory diagram showing a conversion rule 2;

FIG. 14 is a configuration diagram showing the configuration for performing the processing of step 142 in FIG. 12, focusing on its function.

FIG. 15 is a flowchart showing a detailed process of step 144 in FIG. 12;

FIG. 16 is an explanatory diagram showing a conversion rule 3;

FIG. 17 is an explanatory diagram showing an example of an internal expression of a conversion rule 3;

18 is a configuration diagram showing a configuration for performing the processing of step 144 in FIG. 12, focusing on its function.

FIG. 19 is an explanatory diagram showing a conversion rule 4.

FIG. 20 is a configuration diagram showing the configuration for performing the processing of step 147 in FIG. 12, focusing on its function.

FIG. 21 is a configuration diagram showing a modification of the configuration for performing the same processing as steps 141 to 147 of the first embodiment shown in FIG. 12 in the second embodiment.

FIG. 22 is a flowchart illustrating another example of the processing performed in step 1013 of the first embodiment illustrated in FIG. 8 according to the third embodiment.

FIG. 23 is an explanatory diagram showing a conversion rule 5 according to the third embodiment.

FIG. 24 is a flowchart illustrating another example of the processing performed in step 144 of the first exemplary embodiment illustrated in FIG. 12 according to the fourth exemplary embodiment.

FIG. 25 is an explanatory diagram showing a conversion rule 6.

FIG. 26 is an explanatory diagram showing a conversion rule 7 in the fifth embodiment.

FIG. 27 is a configuration diagram showing a configuration for performing processing according to a conversion rule 7, focusing on its function.

FIG. 28 is an explanatory diagram showing another example of the conversion rule 4 in the sixth embodiment and a configuration of a multiplier generated by the conversion rule.

[Explanation of symbols]

 Reference Signs List 11 input device 12 central processing unit 13 output device 14 storage device 21 design processing storage unit 22 element library storage unit 23 circuit data storage unit 231 input unit 232 logical NOT unit 233 multiplication module generation unit 234 logical NOT operation circuit generation unit 235 output unit 241 input means 242 multiplier division means 243 multiplication module generation means 244 division operation circuit generation means 245 output means 251 input means 252 most significant bit separation means 253 bit value determination means 254 multiplication module generation means 255 addition shift operation circuit generation means 256 circuit generation Means 257 Output means 261 Input means 262 Signal generation means 263 Multiplication module generation means 264 Operation circuit generation means 265 Output means 2901 Input means 2902 Logical NOT determination means 2903 Multiplier bit Width determination means 2904 logical negation means 2905 logical negation operation circuit generation means 2906 multiplication module generation means 2907 multiplier division means 2908 division operation circuit generation means 2909 multiplier most significant bit separation means 2910 bit value determination means 2911 addition shift operation circuit generation means 2912 circuit Generation means 2913 Output means

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

Claims (4)

(57) [Claims] 1. A multiplier that receives a signal X representing an n-bit number and a signal A representing an m-bit constant and outputs a product P of n + m bits, wherein a logical NOT signal A0 of the constant A and as the input signal X, a multiplying means for outputting a signal P0 representing the product, as an input the signal P0 and the signals X, X · (2 ^m -
1) a multiplier for calculating -P0 and outputting the signal P. 2. A multiplier for inputting a signal X representing an n-bit number and a signal A representing an m-bit constant, and outputting a product P of n + m bits. A signal P representing the product of the signal X as an input
A multiplying means for outputting 0, a calculating means for receiving the signal X as an input and outputting a signal P01 representing X · (2 ^m -1), and a P01- for receiving the signal P0 and the signal P01 as inputs.
A subtractor for outputting a signal representing the value of P0. 3. A multiplier for receiving a signal X representing an n-bit number and a signal A representing an m-bit constant and outputting a product P of n + m bits, wherein a logical NOT signal A0 of the constant A and A multiplication unit that receives the signal X and outputs a signal P0 representing the product thereof; a logic negation unit that receives the signal P0 and outputs a logical negation signal Q0 of the signal P0; An arithmetic means for outputting a signal Q6 representing X · (2 ^m -1) +1; the signal Q0 having the signal Q0 and the signal Q6 as inputs;
A multiplier that outputs, as the signal P, a signal representing the sum of 0 and the signal Q6. 4. A multiplier which receives a signal X representing an n-bit number and a signal A representing an m-bit constant and outputs a product P of n + m bits, wherein a logical NOT signal A0 of the constant A and Multiplying means for receiving the signal X and outputting a signal P0 representing the product thereof; first logical negating means for receiving the signal X and outputting a logical NOT signal of the signal X; and receiving the signal P0 A second logical negation means for outputting a logical negation signal of the signal P0; a value 0 in each of lower m bits; a signal of n + m bits in which the signal X is connected to upper n bits; An output signal of the first logical negation unit, a signal having a value of 1 connected to each of the upper m bits, a first addition unit having carry-in input of 1, and an output signal of the first logical negation unit And the first processing An output signal of the means, as inputs 1 to the carry-in, a multiplier, characterized in that a second adder means connected to its output to the P.