JPH083819B2 - Logic circuit manufacturing system - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a logic circuit manufacturing system, and in particular, in a logic design of a digital system, a logic circuit having a minimum number of gate stages and a minimum number of gates is automatically calculated from a Boolean function. TECHNICAL FIELD The present invention relates to a manufacturing system of a logic circuit that can be manufactured mechanically.

[Prior art]

In the logic design at the gate level, when the circuit configuration of the Boolean function is performed, in order to reduce the circuit cost, it is necessary to automatically generate the gate logic from the functional logic at the Boolean expression level, and to minimize the number of gates. It is necessary and various methods have been proposed.

For example, in the method described in JP-A-59-201143,
After performing a Boolean multi-tree structure conversion, the gate logic is generated by allocating parts without deforming the multi-tree structure, but the number of gate stages and the number of gates increase compared to the case of performing manually. Points are not taken into consideration.

[Problems to be solved by the invention]

In the above conventional technique, a Boolean expression is converted into a binary tree structure,
Furthermore, the same logical operators consecutive on the binary tree are grouped in the order of appearance for each number of fines peculiar to the circuit system to be realized,
It was probably converted to a tree structure. However, during this conversion,
The number of gate stages of the generated gate logic is not taken into consideration, and there is a problem that the gate logic is not always generated with the minimum number of gate stages.

An object of the present invention is to improve such a problem, and under the condition of the minimum number of gate stages, a logic circuit capable of automatically generating a gate logic of an arbitrary circuit system having a minimum number of gates from a Boolean expression. To provide a manufacturing system of.

[Means for solving problems]

In order to achieve the above-mentioned object, the logic circuit manufacturing system of the present invention is a processing means (processing device) that unifies the output of a Boolean expression given together with circuit designating information and the polarity of a variable into positive or negative logic by logic parts. ), And logical functions such as logical product and logical sum, and physical constraints such as the number of fan-ins and input polarity, and means (gate table) for accumulating components that are manufacturing units of an arbitrary circuit system, In the binary tree structure, the output polarity of the Boolean expression is used as a key to refer to the storage means, and the processing means is used to search for a component satisfying the matching of the logical function and the output polarity, and the fan-in number of the component. In accordance with the above, the multi-branch tree structure is converted so that the number of gate stages of the realized combinational circuit is minimized and the number of gates is minimized, and the number of gate stages is sequentially managed, and each node in the multi-branch tree structure is managed. The part By mapping, it is characterized in that to produce a combinational circuit satisfying the Boolean expression.

[Action]

The processing device first converts the Boolean expression into a binary tree structure and then generates the same logic operator that is continuous in the binary tree structure by 1 to generate the gate logic of the arbitrary circuit from the given Boolean expression together with the arbitrary circuit information. Convert to a multi-branch tree structure that is put together. From the node on the most output side of this multi-branch structure to the input side, physical gates are sequentially assigned using the output polarity as a key. The physical gate to be assigned is searched in the gate table, the multi-tree structure is modified so that the selected physical gate can be assigned, the number of gate stages is managed, and the physical gate is assigned. That is, the gate allocation is tried to the multi-branch tree structure, the number of gate stages of the generated gate logic is calculated, and the result is that the number of gate stages is the minimum and the number of gates is the minimum.
The multi-tree structure is transformed and then converted into a physical gate structure.

Further, in this physical gate structure, the physical gate is blocked for each corresponding basic gate, and converted into the basic gate structure to obtain the logic circuit of the designated circuit system.

〔Example〕

An embodiment of the present invention will be described below with reference to FIGS.

FIG. 1 is a block diagram of a system for manufacturing a logic circuit according to an embodiment of the present invention.

The logic circuit manufacturing system according to the present embodiment includes an input / output device 12
・ 16, processor 14, design master file (functional logic) 13,
Design master file (gate logic) 17, gate table 1
Composed of 5.

The input / output device 12 inputs a Boolean expression, its output, and a functional logic diagram 11 expressing the polarities of variables, etc., and passes it to a design master file (functional logic) 13, and from this design master file (functional logic) 13. The processor 14 receives the functional logic information.
Output to.

The processing unit 14 uses this design master file (functional logic).
Functional logic information such as Boolean expressions and circuit specification information from 13,
Logic gate structure conversion and physical gate structure conversion are performed based on a group of circuit system parts to be realized, which are prepared in advance in the gate table 15, and the basic gate allocation of the Boolean logic circuit to be the target of logic design is determined. .

The input / output device 16 outputs the gate logic diagram 18 based on the basic gate allocation and the gate logic information of the design master file (gate logic) 17.

FIG. 2 is an operation flowchart of the logic circuit manufacturing system in the embodiment of the present invention.

First, the input / output device 12 transmits the input information from the logic circuit diagram 11 to the design master file (functional logic) 13, and from the design master file (functional logic) 13, the Boolean expression and the circuit to be the target of the logic design. The designated information is obtained and output to the processing device 14 (201).

The processing unit 14 receives the information (202) and performs logic gate structure conversion on the Boolean expression to be the target of logic design (203). That is, the Boolean expression is converted into a binary tree structure, and is converted into a multi-tree structure in which the same logical operators continuous on the binary tree are combined into one. Next, the physical gate structure conversion is performed on the Boolean expression converted into the multi-tree structure by the logical gate structure conversion (204). That is,
For each node of the multi-tree structure obtained by the physical gate structure conversion, polar propagation is sequentially performed from the output side, and if necessary, the multi-tree structure is transformed and the physical gate satisfying the design control is searched from the gate table 15. Then, allocation such as connection logic allocation, composite gate allocation, normal gate allocation, and fan-in allocation with priority order is performed (see FIG. 3). Further, the physical gates thus assigned are blocked for each corresponding basic gate and converted into a basic gate structure to obtain a logic circuit configuration of a designated circuit system having a minimum number of gate stages and a minimum number of gates (205). . The logic circuit of the designated circuit system thus obtained is output to the input / output device 16 (206).

The input / output device 16 designs its logic circuit as a master file.
17, or output to logic circuit diagram 18 (207).

FIG. 3 is a flow chart showing the procedure of physical gate structure conversion in the present invention.

As shown in FIGS. 1 and 2, the processing unit 14 converts a Boolean expression to be logically designed into a multi-tree structure by the logic gate structure conversion, and then, is located at the most output side on this multi-tree. From the node to the input side, using the output polarity as a key,
Parts group of each circuit system prepared in the gate table 15 (6th
The physical gate of the specified circuit system that satisfies the design control is searched from among (see the figure) and assigned to each node. If the physical gate searched and selected in this way cannot be assigned, the multi-tree structure is transformed and assigned. The types of physical gates are roughly classified into wired logic gates, compound gates, and normal gates, and their search order is to minimize the number of gate stages and the number of gates under that condition. > Perform in the order of normal gates.

Regarding the search procedure, a connection logic search is first performed from the parts group of the gate table 15 as shown in FIG. 6 (301). The connection logic allocation condition is that the above-mentioned node and the physical gate on the output side of the above-mentioned node have the same logical operator type (logical operator type condition), similarly their output polarities (output polarity condition), The number of outputs of the child node is within the fan-in number of the above node (fan-in number condition), the physical gate at the latter stage of the node is not a connection logic (secondary condition), and all the child nodes are not input variables. (First stage condition). These conditions are checked (302), if all of them are satisfied, connection logic allocation is performed (309), and if only the fan-in number condition is not satisfied, pre-priority ordered fine distribution is performed (308).

For fan-in distribution with priority order, physical gate allocation is tried for each node in the sub-tree structure whose root is each child node targeted for fan-in distribution, and each node in the sub-tree structure is tried. Obtain the number of gate stages, prioritize these child nodes in descending order of the number of gate stages, make the child node with many gate stages as the child node of the original node, and set the child node with few gate stages as the child of the original node. It is distributed as a child node of a node of the same logical operator type as the original node inserted as a node.

Otherwise, a composite gate search is next performed (303). The compound gate allocation condition is that the logical operator type of the node and the output side physical gate of the compound gate match (logical operator type condition), the output polarity matches (output polarity condition), and the number of fan-ins of the node is the compound gate. Is less than or equal to the number of physical gates on the input side (fan-in number condition), and if all of its child nodes are not input variables, the type of logical operator between the child node and the physical gate on the input side of the composite gate matches (pre-condition 1). , And its child nodes are equal to or less than the fan-in number of the input-side physical gate of the composite gate (precondition 2).
These conditions are checked (304), and if all are satisfied, composite gate allocation is performed (309), and pre-condition 2
If the above condition is not satisfied and at least one of the logical operator types of the child nodes matches in the previous-stage condition 2, composite gate extension allocation is performed (305).

Regarding the expanded allocation of the composite gate, first, when the condition 1 in the preceding stage is not satisfied, a 1-input 1-output node having the same logical operator type as the input side physical gate of the composite gate to be allocated is inserted, All the logical operator types of the child node are prepared. Next, if the above fan-in condition is not satisfied, the fan-in distribution with priority order is performed so that the number of fan-ins of the node satisfies the condition. After distributing the fan-in,
Adjust the fan-in number of the child node. Further, the expanded form in which the composite gate assignment is made based on the adjusted tree structure is compared with the expanded form starting from other than the composite gate assignment based on the tree structure initially given. The expanded type with a smaller number of gate stages is adopted. If the number of gate stages is the same, the expanded type with a smaller number of gates is used. Adopt the expanded form starting from.

In all other cases, a normal gate search is performed (306). Ordinary gate allocation conditions are the logical operator type match (logical operator type condition) between the above node and a physical gate on the output side of the above node, the same output polarity match (output polarity condition), and the child node of the above node. The number of outputs is within the fan-in number of the above node (fan-in number condition). Check these conditions,
If all are satisfied, the normal gate allocation is performed (30
9) If the number of fan-ins is over (307), the fan-in distribution with priority is performed (308). If the output polarity condition is not satisfied, a polarity matching amplifier for matching the output polarity is inserted in the subsequent stage (output side).

FIG. 4 is an example of gate expansion in which fan-in distribution with priority order occurs in the present invention, and FIG. 6 is an example of a group of circuit system components stored in the gate table of the present invention.

In FIG. 4, the processor 14 (see FIG. 1) first converts the Boolean expression (a) to be logically designed into the binary tree structure (b), and then the node of this binary tree structure (b). 409 ~ 4
In the case of 16, since the logical operator type is '・' (AND),
These are combined into a single tree structure as shown in (c).

A multi-tree structure (c) thus converted into a logic gate structure
Of the gate assigned to the most output node 416 of the
It is selected from the parts group of the gate table 15 in the figure. Since this node 416 has the logic operator type “·”, the output polarity N, and the fan-in number 8, the connection logic search is performed and the gate
Although the No. 1 gate (WAND) is selected, it does not satisfy the fan-in number condition (fan-in number 6) and the fan-in occurs, so fan-in sorting with priority order is performed.

In this fan-in distribution with priority order, each node'- 'and B to B are child nodes of the node 416 as in (c) (case 1), and each node B to B as in (d). For the case where B is a child node of the insertion node '.' (Case 2), physical gate allocation is tried and the number of gate stages is compared.

Comparing the number of gate stages of nodes '・' 417, Case 1
Is 1 stage, and case 2 is 2 stages including the insertion node.

For nodes BB, case 1 has one stage. In case 2, the subsequent gate is WAND and the input variable node B
Since ~ B is an input variable node, when an amplifier gate is inserted in B for satisfying the condition of the preceding stage at the time of wire connection logic allocation, the number of stages is one.

As described above, in Case 1, the number of gate stages of all child nodes is one, and in Case 2, the number of gate stages of the node “−” is two and the number of gates of the other child nodes is one. In case 2, the priority order of the node “−” is set to 1, the priority order of the other child nodes is set to 2, and the fan-in distribution is performed.

Therefore, regarding the fan-in distribution pattern in case 2, as shown in (d), the node '-' 417 having the priority order of 1 is a child node of the node 416, and the nodes BB
Is a child node of the node 416, one amplifier gate is generated for each node. Therefore, the nodes' and 420 are inserted, and the nodes B to B are its child nodes. The node B is a child node of the node 416. Sort as.

Further, a WAND is assigned to the node 416 in the multi-tree structure of (d), and since the input polarity of the WAND is the N pole, the N pole is made the output polarity of the nodes 417, 420, and B, and these child nodes are Search and assign physical gates. Also, search for physical gates for node 418
Make an assignment.

In this way, the physical gate structure conversion is performed, the physical gate is assigned to (d), and the physical gate structure as shown in (e) is obtained. Since the connection logic is assigned to the node 416 in (d), the amplifier gate 423 is inserted in the node B in (e), and the inverter 42 is connected to the node 417 in (e).
4 is assigned.

Finally, each gate of the physical gate structure shown in (e) is replaced with a basic gate to generate a basic gate structure as shown in (f). In this basic gate structure, the inverter 424 in (e) is omitted.

FIG. 5 is a development example diagram in which expansion allocation of the composite gate occurs, and FIG. 6 is a component example diagram of the circuit system stored in the gate table.

As shown in FIGS. 1 and 2, the processing unit 14 performs a Boolean logic gate structure conversion which is a target of logic design,
A multi-branch tree structure (b) is obtained from the Boolean expression (a) in the figure.

Next, with respect to this multi-branch tree structure (b), the parts group of the circuit system of the table 15 as shown in FIG. 6 is searched and assigned,
Perform physical gate structure conversion.

First, in (b), a physical gate to be assigned to the most output node 525 is searched. The logical operator type of the node 525 is '.', The output polarity is P pole, and the fan-in number is 2. In the connection logic search, since the output polarity of the connection logic WAND is N pole and the polarities do not match, a composite gate search is performed next. Since the node 525 and its child nodes 526 and 527 satisfy the allocation condition of the composite gate, the expanded allocation of the composite gate is performed. The gates that are candidates for allocation are No. 2 in Figure 6.
It is a compound gate.

Child node 527 of node 525 has logical operator type'- '
Since it does not match the operator type '+' on the input side of the composite gate, a node with one input and one output '+' 529 is inserted and all the logical operator types of the child nodes 526 and 529 are inserted as shown in (c). Align with "+". Further, since the maximum fan-in number of the input side physical gate is 3 with respect to the fan-in number 8 of the node 526 in (c), fan-in distribution with priority order is performed so that this number is obtained, and (d) To obtain a tree structure like. Then, based on the tree structure (d), physical gate allocation starting from composite gate allocation is performed to obtain a physical gate structure as shown in (e).

Furthermore, for the multi-tree structure in (b), physical gate allocation starting from normal gate allocation is tried,
The multi-tree structure is modified to allow this physical gate assignment to obtain a tree structure as shown in (g). Then, based on this tree structure, a physical gate structure as shown in (h) is obtained.

Comparing the gate development diagrams of (e) and (h) obtained in this way, since the gate has two stages in (e) and the gate has three stages in (h), the developed form of (e) is adopted.

Finally, basic gate structure conversion is performed to obtain a basic gate structure as shown in (f) from the physical gate structure in (e). When the basic gate structure conversion is performed on (g), the result is (i).

According to this embodiment, a logic circuit having the minimum number of gate stages and the minimum number of gates can be automatically manufactured from a Boolean expression that is the target of logic design.

〔The invention's effect〕

According to the present invention, by managing the number of gate stages and selecting the minimum number of stages in a Boolean circuit system that is a target of logic design, the minimum number of gate stages in an arbitrary circuit system can be calculated from the Boolean formula. It is possible to automatically generate the logic circuit that it has, which is effective in improving the logic design quality and reducing the logic design man-hours.

[Brief description of drawings]

FIG. 1 is a block diagram of a logic circuit manufacturing system according to an embodiment of the present invention, FIG. 2 is an operation flowchart of a logic circuit manufacturing system according to an embodiment of the present invention, and FIG. 3 is a physical gate structure according to the present invention. FIG. 4 is a flow chart showing a conversion procedure, FIG. 4 is an example of gate expansion in which fan-in distribution with priority order occurs in the present invention, and FIG. 5 is an example of gate expansion in which expansion allocation of a composite gate in the present invention occurs, FIG. FIG. 3 is an example diagram of a group of circuit system components stored in the gate table of the present invention. 11: Functional logic diagram, 12/16: Input / output device, 13: Design master file (functional logic), 14: Processing device, 15: Gate table, 1
7: Design master file (gate logic), 18: Gate logic diagram, 409 to 418/420/525 to 529: Node, 423: Amplifier gate, 424: NOT gate (inverter).

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Takashige Kubo 1099, Ozenji, Aso-ku, Kawasaki-shi, Kanagawa Inside the Hitachi, Ltd. system development laboratory (56) Reference JP-A-59-201143 (JP, A) JP Sho 59-168545 (JP, A)

Claims (2)

[Claims] 1. A combinational logic circuit comprising means for inputting a functional logic expressed by a Boolean expression as an object of logic design, satisfying the Boolean expression given by said means, and represented by a connection of a group of logic parts. In the manufacturing system of the logic circuit to be manufactured, for each logic component that can be adopted, the type of logic function, physical constraints such as input / output polarity and fan-in number, and the division of connection logic, composite gate and normal gate are shown. An accumulation means for accumulating data, and an operator for functional logic based on the given Boolean expression.
The binary tree structure of the variables is converted, the same logical operators continuous on the binary tree structure are combined into one and converted into the first multi-branch tree structure, and the first multi-branch tree structure is further converted with reference to the storage means. Transform it to create a second multi-tree structure,
The processing apparatus includes: a processor that maps each node of the second multi-branch tree structure to the logic component to determine the combinational logic circuit; and a unit that outputs the determined combinational logic circuit. When transforming the multi-branch tree structure of No. 2 into the second multi-branch tree structure, 1) the parts are sequentially assigned from the output side node of the first multi-branch structure, and 2) the parts are assigned by the connection logic. 3) If the parts cannot be assigned because the fan-in number of the node is over, the fan-in distribution is tried according to the priority order according to the number of gate stages of each node, and the child generated by the distribution is tried. A logic circuit manufacturing system characterized by selecting fan-in distribution that minimizes the number of gate stages of a node. 2. The system for manufacturing a logic circuit according to claim 1, wherein the processing device is configured to transform the first multi-branch tree structure into a second multi-branch tree structure. When allocating, a logic circuit characterized by first allocating a composite gate, comparing the number of gate stages and the number of parts with the case of allocating the normal gate, and selecting the multi-branch tree structure with the smaller number. Manufacturing system.