JPH1063709A - Function extraction method for combinational circuits - Google Patents

Abstract

(57) [Summary] [Problem] Binary decision diagram, that is, BDD (Binary
By using Decision Diagram, a function extraction method for obtaining a truth table of the entire circuit can cope with a case where the number of inputs is large, and is intended to provide a function extraction method capable of processing at high speed. Is represented by one merged BDD (Merged BDD), and a function extraction method is provided which can handle a circuit including a partial circuit having an output value other than 0 or 1. SOLUTION: A BDD (Binary Decisio) is provided.
n Diagram) operation is a function extraction method for obtaining a truth table of the entire combinational circuit, in which the output of the combinational circuit is represented by one BDD by merging BDDs (Merge). This is done until both the values of the two terms of the variable reach the leaf, at which point the recursion is terminated, and if necessary,
A process of creating a leaf with an increased number of bits by the operation of the leaves is performed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to verification of LSI operation, and more particularly to extraction of circuit function (logic).

[0002]

2. Description of the Related Art In recent years, various LSIs represented by ASICs have been required to have higher integration and higher functions due to the trend toward higher performance and lighter and smaller electronic devices. That is, there is a demand for an IC such as an ASIC to realize a high function by minimizing the chip size as much as possible. The production of ICs such as the ASICs described above is based on functions, logic design,
After a circuit design, layout design, etc., a pattern for a photomask pattern is produced, a photomask is produced using the pattern, and the pattern of the photomask is transferred onto a wafer by a reduced projection exposure or the like, thereby performing a semiconductor production process. Is what you do. Conventionally, when there is a design change at the stage of layout design, the operation is returned from the transistor level to the logic circuit, and the operation is verified here. In this operation verification, a verification method of performing processing paying attention to a data signal and a control signal entering a circuit at a logic level has been adopted. And
The LSI operation (circuit function) is obtained from a series of input data signals and output data signals, that is, (of the input data signals)
Although the operation (circuit function) of the LSI was obtained from the process of fitting the shape, as the number of inputs increases with the advancement of higher functions and higher densities, an enormous amount of input data signals is gradually required. The processing takes a lot of time, and has become a practical problem.

Under such circumstances, as a method of quickly obtaining a function for obtaining a truth table of a combinational circuit even in a large-scale circuit, a binary decision diagram, that is, a BDD (Binary Decision D) is used in a data representation of a logical function.
Attention has been paid to a method of performing a BDD operation by using iagram). BDD is a graphical representation of a logical function. The result of applying Shannon expansion of a logical function (a procedure of substituting 0 and 1 values for a certain input variable to obtain two partial functions) recursively for all variables is divided into two. It is represented by a tree graph. Processing using BDD is excellent in terms of storage efficiency and calculation speed.

Here, BDD will be briefly described. The truth table of the logical function in FIG. 16 is as shown in FIG. 17, and FIG. 18 shows the Y in BDD. A, B, and C surrounded by circles represent input variables and are called nodes. A branch extending from the lower left of each node is called a zero branch, meaning that the variable is 0, and extends to the lower right of each node. A branch is called one branch, which means that the variable is 1. The 0s and 1s enclosed by squares represent logical values, which are called leaves, and represent paths to reach them, that is, output values with respect to input values. Since all the routes R1 in FIG. 18 pass through 0 branches, A = 0, B = 0, C
It means that the output value when = 0 is 0. The route R2 in FIG. 18 indicates that the output value is 1 when A = 0, B = 1, and C = 0. Note that the direction of the route proceeds from top to bottom as indicated by the arrow.

In BDD, a regular graph can be obtained by fixing the order of BDD input variables, deleting redundant nodes, and sharing equivalent subtrees (also called subgraphs) as much as possible. , Logical functions can be represented compactly and uniquely. Hereinafter, sharing of the BDD and deletion of redundant nodes will be described. The subtrees surrounded by the dotted circles in FIG. 19 are the same and can be shared as shown in FIG.
At this time, one branch of the node B points to the same graph. In other words, this means that the node B is the same regardless of whether it is 0 or 1. Since the node B is a redundant node, this is deleted, and FIG. Can be expressed as The BDD shown in FIG. 18 is standardized to the BDD shown in FIG. In this way, a standard BDD can be obtained.

However, if the BDD obtained from the truth table is directly standardized, there is little advantage in using the BDD. In practice, the BDD is obtained by a binary operation to obtain a new logical function obtained by performing a logical operation on a logical function. Build. To generate a BDD that represents the logic of a given Boolean expression (from a truth table), first generate a BDD that represents each input variable, and perform a binary (logical) operation between the BDDs according to the syntax of the Boolean expression. By repeatedly applying the processing, a BDD representing the logic of the entire expression is constructed. Since the algorithm of the binomial (logical) operation processing is known, the BDDs of the logical function are hereinafter referred to as f and g,
A BDD calculation method for obtaining the BDD of f (op) g will be briefly described. Note that (op) is an operator such as and or or, and the BDD operation is also called a BDD binary operation.
Focusing on a certain input variable v, classification is performed for v = 0 and 1, and calculations are performed on each of them. Specifically, B
The operations of the graphs are recursively executed by expanding the variables in order from the higher order of the DD. Here, the order of the variables is determined in advance, and expansion is performed based on the order. When the graph becomes a leaf and becomes a trivial operation, the recursion is terminated and the result is returned. The two input variables A and B shown in FIG.
The following describes an example of a logic circuit in which AND (logical product) is used as an output Y. BDDf and g of the input variables A and B are as shown in FIG. The BDD binomial operation on the and of f and g first consists of the BDD binomial operations (1) and (2). FIG.
As shown in, if the variable order is A and B, first,
In the graph of A = 0, that is, a binary operation of leaves 0 and (2), and the operator is and, the leaf 0 is returned. next,
The graph of A = 1, that is, a binary operation of leaves 1 and (2), and (2), ie, g is returned. As a result, the BDD of the output Y shown in FIG. 25 is generated.

[0007]

As described above, a binary decision diagram, that is, a BDD is used as a data representation of a logic function as a method for quickly extracting a function for obtaining a truth table of a combinational circuit even in a large-scale circuit. Processing methods are known, but these are B for each output when there are multiple outputs.
DD is generated and processed. When a part of the combinational circuit has a partial circuit whose characteristics are represented by a truth table and its output value is other than 0 or 1, ie, ternary It is not possible to cope with the case where the above partial circuit is provided. Under such circumstances, the present invention provides a binary decision diagram, that is, a BDD (Binary Decision D).
iagram), a function extraction method for obtaining a truth table of the entire circuit can cope with a large number of inputs and provides a function extraction method capable of processing at high speed. One merged BDD
(Merged BDD) and the output value is 0, 1
It is an object of the present invention to provide a function extracting method that can handle a circuit including a partial circuit having a value other than the above.

[0008]

According to the present invention, there is provided a method for extracting a function of a combinational circuit, comprising the steps of: BDD (Binary Decision);
This is a function extraction method for obtaining a truth table of the entire combinational circuit by applying an on-diagram operation, in which the output of the combinational circuit is represented by one BDD by merging BDDs (Merge). Variable 2
The process is performed until both the values of the terms reach the leaf, and when the value reaches the leaf, the recursion is terminated.If necessary, a process of creating a leaf with an increased number of bits by the operation of the leaves is performed. It is characterized by having. And the output in the above is 2 or more. In addition, in the above, when there is a partial circuit in the combinational circuit to which only the truth table is given, the partial circuit is created by developing it into a corresponding logic circuit, and the entire combinational circuit including the partial circuit is created. for,
Creating an output BDD,
From the truth table having the output value yi 'of the partial circuit, a logical expression f of a product-sum expression of a row for the value 1 of yi' in the truth table is created, and the output value yi 'of the partial circuit is 0, 1 Xj other than
When (j = 1 to m), a logical expression gj (j = 1 to m) of a product-sum expression of a row with respect to the value xj of yi ′ in the truth table
And a mark Mj corresponding to xj is added to the top of the logical expression, and the obtained logical expression f and j = 1 to j
= M is connected to the logical expression gj up to m by OR, and a logical expression of the entire circuit is created. Then, the output yi of the entire circuit is obtained by BDD conversion from the logical expression of the entire circuit by an extended BDD operation. Is the mark Mj
If there is, the BDD conversion is performed by replacing the leaf 1 converted to BDD with xj.

[0009]

The function extracting method of the combination circuit according to the present invention can cope with the case where the number of inputs is large, can perform the function processing which can be processed at a high speed, and has a multi-output function. Merged BDD (Merged BD
D), and it is possible to provide a function extraction method that can be applied to a circuit including a partial circuit having an output value other than 0 or 1. For details, see BDD (Binary
This is a function extracting method for obtaining a truth table of the entire combinational circuit by applying a Decision Diagram operation, wherein the output of the combinational circuit is merged with a BDD (Merg).
e) is represented by one BDD, and the BDDing is performed until both values of the two terms of the input variable reach the leaf, and when the value reaches the leaf, the recursion is terminated. This is achieved by performing a process of creating a leaf with an increased number of bits by the operation of the leaves, and in particular, it is possible to cope with a case where the output is two or more and a large number. Specifically, if there is a partial circuit in the combinational circuit to which only the truth table is given, the partial circuit is created by expanding it into a corresponding logic circuit, and the entire combinational circuit including the partial circuit is created. By creating the BDD of the output pin, it is possible to cope with the case where a partial circuit is included. From the truth table in which the output value yi 'of the partial circuit is used, the value 1 of yi' in the truth table is obtained.
Is created, and if the value yi 'of the output of the partial circuit takes a value xj other than 0 or 1 (j = 1 to m), the logical expression f A logical expression gj (j = 1 to m) of a product sum expression of a row with respect to the value xj is created, and a mark Mj corresponding to xj is attached at the top of the logical expression, and the obtained logical expressions f and j = 1 After ORing the logical expressions gj to j = m with OR to create a logical expression for the entire circuit,
The output yi of the entire circuit is obtained by converting it into a BDD by the extended BDD operation from the logical expression of the entire circuit. In the case of the BDD, if the logical expression to be operated has a mark Mj,
Since the BDD conversion is performed by replacing the BDD-converted leaf 1 with xj, it is possible to cope with the case where there is a partial circuit whose output takes a value other than 0 or 1.

[0010]

DESCRIPTION OF THE PREFERRED EMBODIMENTS A method for extracting functions of a combinational circuit according to the present invention will be described with reference to the drawings. FIG. 1 is a flowchart of a method for extracting a function of a combinational circuit according to the present invention, which will be described below with reference to FIG. In FIG. 1, S10 to S50 indicate processing steps (processes). First, it is determined whether or not the combinational circuit to be processed has a partial circuit (see FIG. 1 (S1
0)) If there is no partial circuit, the BDD of the output value yi of the whole circuit is obtained as it is. (FIG. 1 (S40)) When there is a partial circuit, the logical expression f of the product-sum expression of the row for the value 1 of yi 'in the truth table is obtained from the truth table in which the output value yi' of the partial circuit is used. create. (FIG. 1 (S20)) Next, the value yi ′ of the output of the partial circuit is a value x other than 0 and 1.
j (j = 1 to m) is determined. (FIG. 1 (S
30)) When the value yi 'of the output of the partial circuit is a value xj (j =
When 1 to m) is not taken, the output yi of the entire circuit is obtained by BDD conversion using the obtained logical expression of the entire circuit. (FIG. 1 (S40)) When the value yi 'of the output of the partial circuit is a value xj (j = j) other than 0 and 1
1 to m), a logical expression gj (j = 1 to m) of a sum-of-products expression in a row with respect to the value xj of yi 'in the truth table is created, and the logical expression corresponds to xj at the top. A circuit in which a mark Mj is added (FIG. 1 (S31)), and the logical expression f obtained in step S20 and the logical expressions gj from j = 1 to j = m obtained in step S31 are connected by OR. An overall logical expression is created (FIG. 1 (S32)), and the output yi of the entire circuit is converted to BDD and obtained from the obtained logical expression of the entire circuit by an extended BDD operation. (FIG. 1 (S40))

In step S40, the logical expression of the entire circuit is represented by B
In this step, the logical expression having the output yi of the entire circuit at the top is subjected to NBDD processing from the bottom up, and the BDD conversion operation of the logical expression is repeated from the bottom up. Mark M on the logical expression
If j exists, the BDD-forming leaf 1 is replaced with xj to perform the BDD-forming.

Next, FIG. 2 shows the algorithm, and an extended BDD operation shows n outputs yi (i = 1 to 1).
n) Merge the BDDs into one BDD. (FIG. 1 (S50)) FIG. 2 (a) shows the entire flow, and simply shows that the merging is performed sequentially one by one. FIG. 2B is a flowchart of merging (Merge). FIG. 2 shows merging of output BDDs (Merg).
The feature of e) is that, in short, in the conventional BDD operation, the recursion is terminated when one of the two terms becomes a leaf, but here the recursion is repeated until both reach the leaf, The point is that a leaf whose number of bits is increased by calculation is created. These two points are different from the conventional BDD calculation. Such a BDD operation is referred to herein as an extended BDD operation.

A specific example will be described according to the algorithm shown in FIG. Output is y1 and y2, BDD
Will be described with reference to FIG. 11 when merging is performed as shown in FIGS. 10 (a) and 10 (b). In FIG. 10, nodes are distinguished by numbers. In FIG. 11, merging is performed.
(A), (b),
Calls occur in this order as (c), (d) and (e). The upper part in this call block is shown as a node (corresponding to Y and yi in FIG. 2), and the lower part is shown as a variable name.
Hereinafter, the processing will be described in order. First, in the call (a), the two terms to be operated on are and are both nodes, and because they are the same variable of x1, S204 in FIG. 2 is executed, and a recursive call is made for each child of 0, 1 branch. Occur. ((B) and (e)) At first, the call (b) of the 0 branch occurs, and the child of the 0 branch is leaf 0, so that (b) is obtained.
In (b), is a variable x2 and is higher than leaf 0, so S203 in FIG. 2 is executed and recursive call (c),
(D) occurs in sequence. In (c), a binary operation is performed with the child of the zero branch with leaf 0, that is, with leaf 0.
1 is executed, a new leaf 00 is created, and the process returns. (R
1) Here, returning to (b), (d) is executed. In (d), leaf 01 is similarly created and the process returns. (R2) Here, returning to (b), S205 of FIG. 2 is executed. That is, the results R1, R2 from the variable names x2, (c), (d)
, And returns. (R3) Here, returning to (a), (e) is executed. In (e), the leaf 11 is similarly created and the process returns. (R4) Then, returning to (a), S205 in FIG. 2 is executed to create a node with the variable name x1, the child of the zero branch as R3, and the child of the one branch as R4, and return. (R5) Here, (a) is the highest recursive call, and as a result, the BDD of R5 is obtained. That is, the BD of y1
The merged version of DDD and y2 BDD is
This is the BDD of R5.

Next, the case where the output value of the partial circuit is only 1 or 0 in step S30 shown in FIG. 1 will be described more specifically. If the truth table of the partial circuit is converted into a logical expression and expanded, the original circuit becomes B
Although the form can be handled by DD, it can be converted into a product-sum logical expression. Explaining the conversion method, the following processing is performed for each output of the truth table. For each row of which the output of interest is 1, if each input xi is 1, xi; if 0, inv (x
i) and? And do a ricketeral that does nothing
And connect each other with or. Further, taking FIG. 12 as an example, a row, a row is a processing target, a row is and (inv (x1), x2), and a row is x1. (X
1), x2), and x1) are logical expressions to be obtained. Expand based on this.

Next, step S40 shown in FIG. 1 will be described based on a specific example. As shown in the truth table of FIG. 13B, a partial circuit having two inputs x1 and x2 and one output y as shown in FIG. An example of a case having x and three values will be described. still,
Here, AND (0, x) = 0, AND (1, x) =
A logical operation is defined as x, OR (0, x) = x, OR (1, x) = 1. What includes this is called an extended BDD operation here. Here, (x1, x2) =
In the case of (0,1), it means that y takes a value of x other than 0,1. Since this circuit becomes a part of the whole circuit,
In order to obtain the BDD of the entire circuit, the BDD of the partial circuit is first determined. The partial circuit represented by the truth table shown in FIG. First, the sum-of-products expression of a row with respect to the value 1 of y is x1, which is converted into a BDD as shown in FIG.
BDD conversion is performed as shown in FIG. This is f. Then, the product-sum expression of the row for the value x of y is and (in
v (x1), x2), the data is converted to BDD as shown in FIG. This is g. Further, if the leaf 1 of the BDD is replaced with x and reconstructed to form a BDD, and this is newly set as g, g becomes as shown in FIG. 14C.
Next, for the obtained BDDf and BDDg, OR
When the binomial operation of (f, g) is performed, the BDD as shown in FIG.
Is obtained. This is h. If a truth table is created from the obtained BDDh, it is found that the truth table is correct. In this way, when the output of the partial circuit has a value x other than 1 and 0, a BDD is created.

[0016]

More specifically, the BD of the combination circuit of the present invention will be described.
A function extraction method using the D operation will be described. FIG. 3 (a)
Represents a combinational circuit having a partial circuit, which is handled in this embodiment. The combinational circuit has two inputs A and B and one output y. FIG. 3B is a truth table of the partial circuit shown in FIG. 3A, and the output y (also the output of the partial circuit) has other values x of 0 and 1. First, since there is a partial circuit in the combinational circuit to be processed, the product sum expression of the row for the value 1 of y in the truth table and the value of y in the truth table are obtained from the truth table (FIG. 3B). Since the sum-of-products expression of a row with respect to x is x1, and (inv (x1), x2), the combinational circuit is represented by a logical expression as shown in FIG. At this time, the mark Mj corresponding to xj is placed at the top of the logical expression of the product-sum expression of the row for xj.
Is attached. In FIG. 4, D1, D2, D3, and D4 are logic elements, and a and b indicate outputs from the elements D2 and D3.

Next, the BDD of x1 and and (in
v (x1), x2), that is, the BDD of b
OR operation of DD and BD of output y of combinational circuit
D is obtained, but the logical expression of y is processed from the bottom up.
The BDDs of the inputs A and B are respectively shown in FIGS.
This is shown in FIG. x1 is and (A, B), and the BDD of x1 is the product (and) of the two BDDs shown in FIG. 6 (a).
Is obtained. To determine and (inv (x1), x2), the BDDs of inv (x1), x2 are determined in advance. The BDD of inv (x1) is shown in FIG.
This is the BDD inv shown in (b), which is subjected to arithmetic processing to obtain the BDD of FIG. The BDD of x2 is the BDD of the input B shown in FIG. 5B, and after all, and (inv (x
1), x2), that is, the BDD of b is the product (and) of the BDD shown in FIG. 7 and the BDD shown in FIG. 5 (b), and is subjected to arithmetic processing to convert the BDD shown in FIG. obtain. This B
At the time of DD conversion, leaf 1 has x
Substitute with Thus, the BD of the output y of the combinational circuit
D is the OR of both BDDs, as shown in FIG. 9A, and is subjected to arithmetic processing to obtain the BDD of FIG. 9B.

[0018]

The function extraction method using the BDD operation of the combinational circuit according to the present invention enables the extraction of the function of the expression combining multiple outputs in the combinational circuit as described above. It is assumed that a circuit including a partial circuit provided only with a value table can be handled. As a result, the present invention uses BDD, enables high-speed processing, and can cope with multiple inputs.

[Brief description of the drawings]

FIG. 1 is a schematic process diagram showing a method of extracting a function of a combinational circuit according to an embodiment.

FIG. 2 is a flowchart for explaining merge of output BDDs when there are many outputs (Merge);

FIG. 3 is a diagram showing a combinational circuit having a partial circuit according to an embodiment and a truth table of the partial circuit;

FIG. 4 is a diagram in which the combinational circuit of the embodiment is developed by using logic elements.

FIG. 5 is a diagram showing BDDs of inputs A and B;

FIG. 6 is a diagram showing a calculation process for obtaining a BDD of x1.

FIG. 7 is a diagram showing a calculation process for obtaining an inv (x1) BDD;

FIG. 8 is a diagram showing a calculation process for obtaining a BDD of b.

FIG. 9 is a diagram showing a calculation process for obtaining a BDD of an output y of the combinational circuit;

FIG. 10 is a diagram showing BDDs of an output y1 and an output y2.

FIG. 11 is a diagram for explaining a recursive call process of a merge procedure;

FIG. 12 is a diagram for explaining how to convert a truth table of a partial circuit into a logical expression in a product-sum expression.

FIG. 13 is a diagram showing a partial circuit having two inputs x1, x2 and one output y and a truth table thereof;

FIG. 14 is a diagram for explaining a method of creating a BDD from a multiply-accumulate expression of a truth table.

FIG. 15 shows OR (f, BDDf and BDDg).
The figure which showed BDD by the binary operation of g)

FIG. 16 is a diagram of a logical function.

FIG. 17 shows a truth table.

FIG. 18 is a diagram expressing Y in BDD.

FIG. 19 is a diagram for explaining a shared graph.

FIG. 20 is a diagram for explaining sharing and redundant point deletion.

FIG. 21 is a diagram showing a standardized BDD

FIG. 22 is a logic circuit diagram

FIG. 23 is a diagram showing BDDf and g of input variables A and B;

FIG. 24 is a diagram for explaining a binary operation of BDD.

FIG. 25 is a diagram showing a BDD obtained by a binomial operation.

[Explanation of symbols]

 S10 to S50 Step S201 to S205 Step D1 to D4 Logic element

Claims (4)

[Claims] 1. A BDD (Binary Decisio)
n Diagram) operation is a function extraction method for obtaining a truth table of the entire combinational circuit, in which the output of the combinational circuit is represented by one BDD by merging BDDs (Merge). This is done until both values of the two variables reach the leaf, at which point the recursion is terminated and, if necessary,
A method for extracting a function of a combinational circuit, which performs a process of creating a leaf having an increased number of bits by an operation between leaves. 2. The method for extracting a function of a combinational circuit according to claim 1, wherein the output is two or more. 3. A combination circuit according to claim 1, wherein when the combinational circuit includes a partial circuit to which only the truth table is given, the partial circuit is developed by expanding the partial circuit into a corresponding logic circuit.
A function extracting method for a combinational circuit, wherein an output BDD is created for the entire combinational circuit including a partial circuit. 4. The partial circuit according to claim 3, wherein a logical expression f of a product-sum expression of a row for a value 1 of yi ′ in the truth table is created from the truth table with the output value yi ′ of the partial circuit. Takes a value xj (j = 1 to m) other than 0 or 1 when the output value yi ′ is a logical expression gj (j = 1 To m), and a mark Mj corresponding to xj is added to the top of the logical expression.
The obtained logical expression f and the logical expression gj from j = 1 to j = m
Are connected by OR to create a logical expression of the entire circuit, and then the output yi of the entire circuit is converted into a BDD by the extended BDD operation from the logical expression of the entire circuit. If there is a mark Mj, BD
A method for extracting a function of a combinational circuit, wherein BDD conversion is performed by replacing the D-converted leaf 1 with xj.