JP2985922B2 - Logic function data processor - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus for processing a logical function having a plurality of input variables or an arbitrary subset of a set consisting of a plurality of elements. The present invention relates to a logical function data processing device that expresses a logical function or a subset using a binary decision diagram and executes simplification of the logical function based on the binary decision diagram.

[0002]

2. Description of the Related Art As one method of expressing a logical function, a method called a binary decision diagram is used (REBrya
nt, "Graph-Based Algorithms for Boolean Function M
anipulation ", IEEE Trans. Comput. Vol. C-35, No.
8, pp 677-691). This expression method includes the following processes.

(1) Ordering processing A fixed order is given to all input variables of a logic function. For example, in FIG. 1, a fixed order of x3, x2, x1 is given to three input variables.

(2) Expansion processing Two partial functions are derived from a logical function by substituting logical values of 0 and 1 into one of the input variables. For example, in FIG. 1, two partial functions are derived by substituting 0 and 1 for an input variable x3.

(3) Binary tree graph generation processing According to the order given by the ordering processing, the above expansion processing is repeated for all input variables.
A binary tree graph as shown in FIG. In FIG.
Circles indicate intermediate nodes, and squares indicate terminal nodes. The intermediate node corresponds to each expansion process, and has two branches indicating two partial functions obtained by the expansion process. The end node represents a logical value of 0 or 1 obtained as a result of a series of expansion processing.

(4) Sharing process As shown in FIG. 2 (a), the 0 branch from the first intermediate node 11 and the 0 branch from the second intermediate node 12 have the same intermediate node 13. And when one branch emanating from these first and second intermediate nodes points to another and the same intermediate node 14, these first and second two intermediate nodes 1
1 and 12 are shared as shown in FIG.
They are combined into one intermediate node 15.

(5) Non-redundancy processing As shown in FIG. 3A, two branches 0 and 1 coming out of the first intermediate node 17 are connected to the same second intermediate node 18.
, The first intermediate node 17 is removed as shown in FIG. 3B, and the branch pointing to the first intermediate node 17 is directly connected to the second intermediate node 18.

By the sharing process and the non-redundancy process, the binary tree graph shown in FIG. 1 is compressed into a binary decision diagram shown in FIG.

As described above, a logical function can be expressed by using a BDD. BDDs can also be used to represent aggregate data.

FIG. 5 is a diagram showing an example of a method of expressing set data using a BDD. In this figure, each element a, b, c, d, of a set of eight elements
e, f, g, and h are numbers 0, 1, 2, 3, 4, 5, 6, and 3 represented by a three-digit binary number in the number table 21.
7, respectively. When the elements b and c in the set data are given as the initial data 22, the elements b and c are encoded according to the number table 21, and encoded data 23 represented by a three-digit binary number is created. If each digit of this binary number is represented by x3, x2, x1 from the top, a binary tree graph 24 is generated from the encoded data 23.

In the binary tree graph 24, {001} corresponding to the element b and {01} corresponding to the element c
Only 0 # is connected to the 1 end node, and the branches corresponding to the other elements are connected to the 0 end node. This indicates that elements b and c are included in a subset of the set having eight elements. The binary tree graph 24 receives the above-described sharing processing and non-redundancy processing,
A binary decision diagram 25 is generated.

As described above, each element of the set is represented by a different integer, and the set is associated with a logical function by considering each digit 0 and 1 when the integer is represented by a binary number as a logical value. be able to. Then, these sets can be simplified by the above-described binary tree graph generation processing, sharing processing, and non-redundancy processing. In this case, in each intermediate node of the binary tree graph, the process of substituting 0 and 1 for input variables to obtain two subgraphs is a set of binary digits indicating an element number in the processing of aggregate data. Has the meaning of classifying all elements into two subsets depending on whether is 0 or 1.

[0013]

By using the above-mentioned binary decision diagram technique, sharing and non-redundancy of intermediate nodes are performed. Therefore, if the method of the BDD is applied to automatic design or the like using a computer, simplification of a logic circuit can be realized, and data can be expressed with a small storage amount. Also, the calculation time is shortened by the reduction of the storage amount.

However, in this type of processing, a subset (sparse set) having a considerably smaller number of elements than the number of elements in the entire set is often processed. In such a case, if a small element number is assigned to an element having a high appearance frequency and the element number is expressed in a binary number, the frequency of occurrence of 0 in each digit of the binary number becomes considerably higher than the frequency of occurrence of 1. . As a result, the possibility that the destinations of the two branches 0 and 1 coming out of the intermediate node coincide with each other is reduced, the frequency of reducing the number of nodes is reduced, and the storage capacity is increased.

Further, in the conventional method using the BDD, even if the data represents the same set, as shown in FIGS. 6A and 6B, the number of binary digits (FIG. 6A shows 3 digits). Since the form of the graph differs depending on the digit data (four-digit data in FIG. 6B), there is also a problem that the number of elements of the whole set must be fixed in advance.

Accordingly, an object of the present invention is to represent a subset (sparse set) having a considerably small number of elements as compared with the number of elements of the whole set in a graph with a small number of nodes, thereby reducing storage capacity and calculation time. To provide a logic function data processing device.

[0017]

According to the present invention, there is provided a logic function data processing apparatus comprising: an order table for giving a fixed order to each of a plurality of input variables x constituting logic function data; A node table for storing a binary tree-like graph composed of a combination of two terminal nodes t0 and t1 representing logical values of 0 and 1, wherein one input variable x relating to each intermediate node and one input variable a node table having an area for storing two branches e0 and e1 representing destinations when 0 and 1 are substituted into x, and 0 and 1 as first input variables x1 recorded in the order table. Is performed to decompose into two partial logical functions, and for each partial logical function,
Substituting 0 and 1 for the second input variable x2 in the order table, and performing expansion processing for decomposing each into two partial logical functions, and thereafter performing the same expansion processing according to the order shown in the order table, The input variable x is repeated, and the expansion obtained by the series of expansion processing is expressed by the intermediate node and the terminal nodes t0 and t1, to generate the binary tree-like graph, and configure the binary tree-like graph. Means for storing the intermediate node and the terminal nodes t0 and t1 in the node table, and the same input as the intermediate node a before generating a new intermediate node a and storing it in the node table during the expansion processing. Variable x and branch e
It is checked whether or not an equivalent intermediate node b having 0, e1 already exists in the node table, and if it already exists, a new intermediate node a is not generated, and
Means for pointing the branch that should point to the intermediate node a to the intermediate node b, and sharing the intermediate node; and, during the expansion processing, one branch e1 of the new intermediate node a directly connects the terminal node t0. If so, the intermediate node a is not generated, and the branch that should point to the intermediate node a is the other branch e.
Means for directly indicating a destination of 0 and performing non-redundancy to prevent generation of redundant intermediate nodes.

The logic function data processing device further comprises:
A number table for associating subset data consisting of arbitrary elements in the aggregate data consisting of a plurality of elements with the logical function data, wherein the number table is assigned to each element of the aggregate data and to each element; And each of the digits when the integer number is represented by a binary number is made to correspond to each of the input variables x, and the logic function data is constituted by each of the input variables x. An element corresponding to the integer number represented by a binary number takes a value 1 when included in the subset data, and takes a value 0 otherwise.

The logic function data processing device according to the present invention comprises:
Further, using a binary number having the same number of digits as the total number of literals constituting the product term of the set data representing the ON set of the logic circuit in the form of the sum of the product terms, 0 and 0 of each digit of the binary number are used. 1
Is associated with the presence or absence of the literal, the product term is represented by a different binary number, the ON set is represented as a logic function, and a logic circuit design device that designs a logic circuit based on the logic function, A number table indicating the correspondence between the product term and the binary number, an order table for giving a fixed order to each of the literals, a plurality of intermediate nodes and two terminal nodes t representing logical values of 0 and 1
In a node table for storing a binary tree-like graph composed of combinations of 0 and t1, one literal relating to each intermediate node and two branches representing destinations when 1 and 0 are substituted into the literals A node table having an area for storing e0 and e1 and a first literal recorded in the order table are subjected to expansion processing for substituting 0 and 1 to decompose them into two partial logical functions. For each partial logical function, 0 and 1 are assigned to the second literal of the order table, and expansion processing for decomposing each of the partial logical functions into two partial logical functions is performed. Thereafter, similar expansion processing is performed in the order shown in the order table. Therefore, for all literals, the expansion obtained by the series of expansion processing is performed on the intermediate node and the terminal nodes t0 and t1.
To generate the above-mentioned binary tree-like graph, and the intermediate node and the terminal node t0,
means for storing t1 in the node table, and the same literals and branches e0 and e1 as the intermediate node a before generating a new intermediate node a and storing it in the node table during the expansion processing. The equivalent intermediate node b is
It is checked whether or not the node already exists in the node table. If the node already exists, a new intermediate node a is not generated, and a branch pointing to the intermediate node a is pointed to the intermediate node b. Means for sharing the intermediate node, and when one branch e1 of the new intermediate node a directly points to the terminal node t0 during the expansion processing, the intermediate node a is not generated and the intermediate node a is not generated. Means for making the branch that should point to node a directly point to the destination of the other branch e0, and performing non-redundancy to prevent generation of redundant intermediate nodes, and including the product term obtained by the sharing and redundancy According to a literal, there are provided means for connecting an input terminal of the logic circuit and an input terminal of an AND element on a circuit diagram, and means for connecting each output of the AND element to one OR element on the circuit diagram. That And butterflies.

The logic function data processing device further comprises:
After generating a circuit in which the AND element and the OR element are combined, by performing equivalent replacement on the circuit,
It is characterized by generating a circuit using a NAND element and a NOR element.

According to the fault diagnosis apparatus of the present invention, when it is assumed that a fault in which a signal is fixed to 0 or 1 occurs on a signal line of a logic circuit at a plurality of locations, a signal on the signal line A set of faults whose values differ from the normal value is sequentially calculated from the input terminal of the logic circuit to the output terminal using a set operation according to the logic of the circuit, and the influence on the signal value of the output of the logic circuit is affected. In the fault diagnosis apparatus for obtaining a set of faults to be given, the set data of the faults is represented by a binary number having the same number of digits as the total number of assumed faults, and 1 and 0 of each digit of the binary number are used to determine whether each fault exists. Means for expressing the set data of the faults as a logical function, an order table for giving a fixed order to each fault, and a plurality of intermediate nodes and two end points representing logical values of 0 and 1. No In node table for storing the binary tree-like graph, which consist of a combination of de t0, t1,
One fault related to each of the intermediate nodes, and two branches e0 and e representing destinations when 1 and 0 are substituted into the fault.
A node table having an area for storing 1 and an expansion process of substituting 0 and 1 into the first fault recorded in the order table to decompose the first fault into two partial logical functions. With respect to the logic function, 0 and 1 are substituted for the second fault in the order table, and expansion processing is performed to decompose the logic function into two partial logical functions. It repeats for all the faults, and deploys the deployment obtained by the series of deployment processing to the intermediate node and the terminal nodes t0, t0,
The binary tree-like graph is generated by expressing the binary tree-like graph by t1, and the intermediate node and the terminal node t constituting the binary tree-like graph
Means for storing 0, t1 in the node table, and the same faults and branches e0, e1 as the intermediate node a before generating a new intermediate node a and storing it in the node table during the expansion processing. An equivalent intermediate node b with
It is checked whether or not the node already exists in the node table. If the node already exists, a new intermediate node a is not generated, and a branch pointing to the intermediate node a is pointed to the intermediate node b. Means for sharing the intermediate node, and when one branch e1 of the new intermediate node a directly points to the terminal node t0 during the expansion processing, the intermediate node a is not generated and the intermediate node a is not generated. Means for directing the branch to point to the node a to the destination of the other branch e0, and for performing non-redundancy to prevent generation of redundant intermediate nodes
It is characterized by the following.

[0022]

According to the present invention, the number of nodes is reduced by using a technique using a zero suppression binary decision diagram (hereinafter simply referred to as a zero suppression method). In the zero suppression method, when the branches representing the assignment of 0 and 1 to the input variables are e0 and e1, respectively, at each intermediate node, if the branch e1 indicates the terminal node of 0, This is a non-redundant method in which the branch e1 and the terminal node of 0 are removed, and the branch indicating the intermediate node is directly connected to the branch e0.

[0023]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings, but before that, the principle of the present invention will be described with reference to FIGS.

FIG. 7 is the same as the conventional example of FIG. 5 up to the point where the binary tree graph 24 is generated. The method of generating the zero suppression binary decision diagram 30 from the binary tree graph 24 is the main point of the present invention.

FIG. 8 is a diagram showing a new non-redundancy process used in the present invention. This method is used in place of the conventional non-redundancy process (see FIG. 3). This non-redundancy processing is executed before the intermediate node 33 is generated and stored in the node table described later.

In FIG. 8, 33 is an intermediate node, e0 and e1 are branches indicating branch destinations when 0 and 1 are substituted for input variables, and t0 is a terminal node of 0. The zero suppression method of the present invention uses one branch e of the intermediate node 33.
It is checked whether or not 1 directly points to the terminal node t0. If it does, the intermediate node 33 is not generated. The branch 31 that should point to the intermediate node 33 is the intermediate node 3
The other branch e0 of 3 directly points to the node 32 to which it points. As a result, FIG. 8A is made non-redundant as shown in FIG.

FIG. 9 is a diagram showing a process in which the binary tree graph 24 of FIG. 7 is simplified to a zero suppression binary decision diagram 30. The binary tree graph 24 in FIG. 9A is compressed as shown in FIG. 9B by the sharing process of the end node. Further, as shown in FIG. 8C, the intermediate nodes B, C, and D are deleted by the non-redundancy processing of FIG. This is because the 1 branch of these intermediate nodes directly points to the 0 end node. Further, when the non-redundancy processing by the zero suppression method is repeated, the intermediate node F in which one branch directly points to the end of 0 is deleted as shown in FIG. Finally, as shown in FIG.
The intermediate node G is deleted, and the simplification results in a zero-suppressed binary decision diagram 30.

This zero suppression binary decision graph 30 is
The one-to-one correspondence with the conventional BDD 25 (FIG. 5) can be understood as follows. That is, in the conventional binary decision diagram, the original complete binary tree graph can be restored by applying the simplification rules of FIGS. 2 and 3 in the opposite direction. Similarly, if the rules of FIGS. 2 and 8 are applied to the zero suppression binary decision diagram in the opposite direction, the original binary tree graph can be restored. That is, it can be seen that the zero suppression binary decision diagram 30 has the same information as the conventional binary decision diagram.

When the non-redundancy processing by the zero suppression method of the present invention is applied to the binary decision diagram shown in FIG.
The intermediate node x4 is deleted, and the BDD shown in FIG. 6B is obtained. That is, as shown in FIG. 10, even if the binary numbers of the element numbers are different, if the elements are the same, the shape of the graph is the same. As a result, the number of elements and the number of binary digits of the whole set need not be fixed first, but can be changed during processing. Therefore, flexible processing becomes possible.

Further, when handling set data in which the appearance frequency of 0 in each digit of the element number is much larger than the appearance frequency of 1, such as set data of product terms in the simplification processing of a logic circuit, The destination of the branch e1 of each intermediate node is 0
Is more likely to point to the end node t0. Therefore, there are many opportunities for performing the new non-redundancy processing of the present invention, and the number of nodes can be further reduced as compared with the conventional case.

FIG. 11 is a graph showing the results of an experiment performed to show the effect of the zero suppression non-redundancy processing of the present invention. 100 combinations are randomly selected to select k from 100, and a set of combinations having the 100 elements is represented by a conventional BDD and a zero-suppressed BDD of the present invention. The numbers were compared. FIG. 11 shows the results when k is changed from 1 to 99. The number of nodes is obtained by averaging 100 experiments. As this experimental result shows, the zero suppression method gives a more compact expression, and the difference is
This is particularly noticeable when k is small. The effect decreases as k increases, but when k exceeds half, k can be reduced by using a complement. For example, 1
A combination of selecting 90 to 90 pieces is equivalent to selecting the remaining 10 pieces.

The conventional non-redundancy processing shown in FIG.
When the zero suppression non-redundancy processing according to the present invention shown in FIG. 8 is used together, as can be seen by comparing FIGS. 3 and 8, starting from different patterns as shown in FIG. The same pattern as shown in b) is obtained. That is, the uniqueness of the graph is lost.
To avoid this, the present invention does not use the conventional non-redundancy processing.

The zero suppression method according to the present invention described above
The present invention can be applied to a logic circuit design device, a fault diagnosis device, a collective data processing device, and the like. Hereinafter, examples thereof will be described.

Embodiment 1 FIG. 12 is a block diagram showing an embodiment in which the zero suppression method according to the present invention is applied to a logic circuit design apparatus.

In the figure, reference numeral 50 denotes a logic synthesis processing device, and 60 denotes an aggregate data processing device. The logic synthesis processing device 50 includes a control device 51 and a product-sum storage table 52. The control device 51 stores the logical expression data 54 input through the input device 53, and issues a command to the aggregate data processing device 60 based on the logical expression data 54. The logical expression data 54 is given, for example, as logical expression data 54a shown in FIG. Product-sum storage table 52
Is a table that records where the product term and the product-sum term start from a node table described later.

The aggregate data processing device 60 executes the instruction from the logic synthesis processing device 50 and returns the calculation result to the logic synthesis processing device 50. The logic synthesis processing device 50 stores the calculation result in the product-sum storage table 52. Control device 51
Configures a circuit based on the calculation results. This circuit is output from the output device 55 as a circuit diagram 56. The circuit diagram 56 is given, for example, by a circuit diagram 56a shown in FIG.

The aggregate data processing device 60 includes a control device 61
, An ordering table 62, and a node table 63. As shown in FIG. 13, the ordering table 62 gives a fixed order to the literals representing each character of the input variable and its negation. On the other hand, as shown in FIGS. 14A to 14C, the node table 63 includes, for each node (ie, an intermediate node and a terminal node), a literal related to the node and two nodes exiting from the node. It is a table for storing nodes indicated by branches e0 and e1. For example, FIG.
The node table corresponding to the zero-suppression binary decision diagram shown in FIG. 7 (c) is that shown in FIGS. 14 (a) to 14 (c).

Next, with reference to FIGS. 12 to 19, a description will be given of the logic circuit design processing according to the present embodiment.

First, the specifications of the circuit are expressed by a logical expression 54 in FIG.
As shown in a, it is described as a combination of logical expressions including logical operations such as logical sum and logical product, and is given as an input file. This logical expression is developed into a two-stage product-sum logical expression, that is, a form of a sum of a plurality of product terms.

The two-stage sum of products form can be treated as set data of product terms. The logical expression is converted into a two-stage product-sum form as follows. First, each element appearing in the logical expression is represented by 1
It is a set of product terms consisting of product terms. Next, two-stage sum-of-products data is obtained by repeating the operation of the plurality of product terms according to the structure of the given logical expression. Specifically, it is executed as follows.

In step S1 of FIG. 15, the control device 51 of the logic synthesis processing device 50 reads the logic expression data 54 from the input file. This data is stored in the controller 51
Is temporarily stored in the internal storage device. For example, the logical expression data 54a shown in FIG. 16 is read and stored in the internal storage device.

In step S2, the control device 51
Each element of the logical expression is sum-of-products form 71-7 consisting of one product term
4 (FIG. 16). Next, the control device 51 supplies the set data processing device 60 with the literals constituting the sum-of-products form 71-74 and the method of operation between the literals (in this case, the product), and outputs them to the aggregate data processing device 60 as shown in FIGS. Command to calculate a zero-suppressed binary decision diagram as shown in b). The aggregate data processing device 60 generates the zero suppression binary decision diagram by the zero suppression method of the present invention described above. As a result, the contents of the node table 63 are as shown in FIG.
14A and FIG. 14B, the product terms 71 and 72 and their start addresses N0 and N2 are returned from the set data processing device 60 to the logic synthesis processing device 50 as calculation results. The logic synthesis processing device 50 stores these calculation results in the product-sum storage table 52.

When the sum-of-products forms 71 and 72 are represented by a conventional BDD, they are as shown in FIGS. 20 (a) and 20 (b). That is, each product term is represented by a binary number by associating whether or not ten literals relating to five input variables are included in the product term with each digit 0 and 1 of the binary number. A set of terms can be represented by a conventional BDD. For details, see "Logic Sy" edited by Tsutomu Sasao.
nthesis and Optimization "Kluwer Academic Publishe
rs, 1993, Chapter 2, pages 36-38.

If the same sum-of-products 71 and 72 are expressed by the zero suppression method of the present invention, FIGS.
The expression is compact as shown in FIG. This is an effect of the above-described zero suppression non-redundancy processing of the present invention, and the processing is executed by the aggregate data processing device 60.

In step S3 in FIG. 15, the control device 51 determines the sum 75 of the product terms 71 and 72, the sum 76 of the product terms 73 and 74, and the sum of the product terms 75 and 76 according to the structure of the logical expression. An instruction to calculate the product 77 is sent to the aggregate data processing device 60.

In response, the aggregate data processing device 60
Calculates the sum of the product term sets represented by the zero-suppression binary decision diagram and the product. The specific method is described, for example, in the above-mentioned Bryant's dissertation, pp. 681-687. In this operation method, a given operation is decomposed into operations of the divided cases by dividing the case into 0 and 1 in order from the upper variable. This operation is repeated for each variable to generate a graph of the operation result. Simplified processing of sharing and zero suppression non-redundancy is applied for each operation.

FIG. 17 (c) and FIG. 18 (a) show a zero-suppression binary decision diagram obtained by the zero-suppression method of the present invention. FIG. 14C shows a node table 63 corresponding to the graph of FIG. Based on the contents of this node table,
The start address N3 of No. 5 is supplied from the collective data processing device 60 to the logic synthesis processing device 50 as a calculation result.
Similarly, for the sum of products 77, the node table 6
3 is generated, and the calculation result is sent to the logic synthesis processing device 50. FIGS. 20 (c) and 21 (a) show a BDD obtained using the conventional de-redundancy. FIG. 18A shows a final product-sum expression representing the logic of the circuit according to the present embodiment, and FIG. 21A shows a final product-sum expression representing the logic of the circuit according to the prior art. .

In step S4 of FIG. 15, the control unit 51 determines that the product-sum form 77 is simplified by the set data processing unit 6
Command 0. Control device 61 of aggregate data processing device 60
According to the procedure instructed by the control device 51, the simplification is performed by examining the inclusion relation between the product terms, and FIG.
A simplified zero suppression binary decision diagram 80 is created as shown in FIG. This simplification operation is a well-known technique. For example, RK Brayton et al., "Logic Minimizat
ion Algorithms for VLSI Synthesis ", KluwerAcademic
Publishers, 1990. According to the conventional simplification, the binary decision diagram of FIG. 21B is obtained. However, it is understood that this is considerably complicated as compared with the zero suppression binary decision diagram 80 of the present embodiment.

In step S5, the control device 51
A circuit diagram is created based on the simplified zero suppression binary decision diagram 80. Specifically, the control device 51 causes the aggregate data processing device 6 to follow the path of the graph 80.
Command 0. Control device 61 of aggregate data processing device 60
Traverses the node table 63 in response to this instruction,
A path from the upper node to one terminal node t1 is found. In this case, two passes are found. Here, the control device 51 converts the literal in the middle of the path to AN.
The outputs of the two AND gates are combined by the OR gate 83, and are combined by the D gates 81 and 82. Inverters 84 and 85 are provided for the literals indicating negation. Finally, the input removes one AND gate 81. Thus, the circuit diagram 56a of FIG. 16 is finally obtained.

Finally, in step S6, the control device 51 causes the output device 55 to output the circuit diagram data 56.

In this embodiment, AN is used as a logic element.
Although the D element and the OR element are used, these elements can be replaced with a NAND element and a NOR element by local equivalent replacement.

As described above, in this embodiment, by employing the zero suppression non-redundancy processing, it is possible to realize a significant reduction in storage capacity and a reduction in calculation time. This can be easily understood by comparing FIGS. 17 (a) and 18 (b) according to the present embodiment with FIGS. 20 (a) and 21 (b) according to the related art.

Embodiment 2 Embodiment 2 is an example in which the present invention is applied to a failure diagnosis device. Before describing this embodiment, the concept of fault propagation will be described with reference to FIG.

In FIG. 22, when a certain test vector is input to a logic circuit 90, and an output different from a normal value is obtained at a certain output terminal 92, this logic circuit 90
Is known to have a fault. Going further,
When a certain test vector is input, a problem of which fault at which point propagates to which output signal line is raised.
For example, when a certain test vector is input, a certain output terminal 9 is generated due to a fault 91 fixed to 0 or 1.
If an abnormal output is obtained in No. 2, it is said that the fault 91 has propagated to the output signal line 92 with respect to this test vector.

For example, the AND gate 95 in FIG.
Consider a case where a test vector (0, 1) is input.
A fault whose first input terminal of the AND gate 95 is fixed to 0 is denoted by a0, and a fault whose first input terminal is fixed to 1 is denoted by a1. Similarly, A
A failure in which the second input terminal of the ND gate 95 is fixed to 0 is represented by b
A fault fixed to 0 or 1 is represented by b1. In this case, the normal output is 0 and the abnormal output is 1. Therefore, when the first input terminal is fixed at 1 and the second input terminal is not fixed at 0, an abnormal output is obtained. Thus, a set 96 of faults is obtained.

By calculating such a set of faults for each logic element from the input terminal to the output terminal of the logic circuit 90, each output signal line of the logic circuit 90 is
A set of faults is obtained for each test vector.
It is known to represent this set of faults in a BDD, for example, see N. Takahashi, et al, "Fault Simulati
on for Multiple Faults Using Shared BDD Representa
tion of Fault Sets ", Processing of IEEE / ACM ICCAD'9
1, pp. 550-553, 1991. In this embodiment, a set of faults is obtained by using the above-described zero-suppression binary decision diagram of the present invention instead of the conventional binary decision diagram.

The fault diagnosis device of this embodiment has the same configuration as the logic circuit design device shown in FIG. In this embodiment, a binary number having the same number of digits as the number of assumed failures is used.
A combination of a plurality of faults is expressed by associating each digit 1, 0 with the presence or absence of each fault. In this case, the order table 62 gives the binary numbers 0 and 1 a fixed order. Further, circuit diagram data and input signal data of the logic circuit 90 are provided instead of the logic expression data 54 in FIG. 12, and simplified failure set data is provided instead of the circuit diagram data 56.

FIG. 24 is a flowchart showing the operation of the failure diagnosis device.

At step S11, the controller 51
Reads circuit diagram data and input signal data. This circuit diagram data corresponds to the logic circuit 90, and the input signal data corresponds to the test vector described above.

In step S12, the controller 51
The control unit 61 calculates a normal signal flow for each element from the input terminal to each output terminal.
To order. The control device 61 outputs the result to the control device 51.
To return. By repeating this procedure, the logic circuit 9
A normal output of 0 for each input signal data is obtained.

At step S13, the controller 51
Instructs the controller 61 to calculate the propagation of the fault for each element from the input terminal to each output terminal. The control device 61 returns the result to the control device 51. By repeating this procedure, the logic circuit 90
Is calculated for each input signal data. In other words, failure aggregate data is obtained. In this step, the zero suppression non-redundancy processing according to the present invention is used.

In step S14, the controller 51
Causes the output device 55 to output aggregated data of failures.

The control device 51 can make a fault diagnosis using the set of faults. For example, when a fault is detected for a plurality of test vectors, the location of the fault occurrence can be limited by calculating the product of the faults obtained by the present method.

The zero-suppression binary decision diagram according to the present embodiment is greatly simplified than the conventional binary decision diagram. This is because, among the faults assumed in the logic circuit, the number of simultaneously occurring faults is relatively small, so that a binary digit representing a set of faults that takes 0 is far more than a binary digit that takes 1 In many cases, the zero suppression of the present invention works effectively. As a result, the storage capacity is greatly reduced and the processing time is reduced as compared with the conventional binary decision diagram.

[0065]

As described above, according to the present invention,
A set with a smaller number of elements (sparse set) than the number of elements in the whole set can be represented by a graph with a smaller number of nodes than in the past. As a result, it becomes possible to automate the design of a logic circuit larger than before. Further, it is possible to reduce the amount of processing data, improve the processing speed, and shorten the design time.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating an example of a binary tree graph obtained by expanding a logical function.

FIG. 2 is a diagram showing a conventional sharing process in generating a BDD.

FIG. 3 is a diagram showing a conventional non-redundancy process in generating a BDD.

FIG. 4 is a diagram showing a binary decision diagram generated by simplifying the binary tree graph of FIG. 1 by a conventional sharing process and a non-redundancy process.

FIG. 5 is a block diagram showing an example of expressing set data using a conventional BDD.

FIG. 6 is a diagram showing an example in which, when the same set of data is expressed using a BDD, the shape of the graph differs depending on the number of binary digits representing the set of data.

FIG. 7 is a block diagram showing a principle of generating a zero suppression binary decision diagram according to the present invention.

FIG. 8 is a diagram showing zero-suppress non-redundancy processing according to the present invention.

FIG. 9 is a diagram showing a process for simplifying the binary tree graph of FIG. 7 using zero-suppress non-redundancy processing according to the present invention.

FIG. 10 is a diagram showing that the shape of the zero-suppressed binary decision diagram according to the present invention does not change depending on the number of binary digits representing the set data.

FIG. 11 is a graph comparing the number of nodes in a zero-suppression binary decision diagram according to the present invention with a conventional binary decision diagram.

FIG. 12 is a block diagram showing a configuration of an embodiment of a logic circuit designing apparatus according to the present invention.

FIG. 13 is a diagram showing an example of an ordering table in the embodiment.

FIG. 14 is a diagram showing a change in a node table in the embodiment.

FIG. 15 is a flowchart for explaining the operation of the embodiment.

FIG. 16 is a block diagram showing an outline of simplification of a logic circuit in the embodiment.

FIG. 17 is a diagram showing an example of a sum-of-products zero suppression binary decision diagram generated in the embodiment.

FIG. 18 is a diagram showing an example of a product-sum zero-suppression binary decision diagram generated in the embodiment.

FIG. 19 is a diagram illustrating a method of converting a finally obtained product-sum representation into a circuit diagram in the embodiment.

FIG. 20 is a diagram expressing the product-sum form shown in FIG. 17 by a conventional binary decision diagram.

FIG. 21 is a diagram expressing the product-sum form shown in FIG. 18 by a conventional BDD.

FIG. 22 is a diagram for explaining propagation of a fault in an embodiment of the fault diagnosis device according to the present invention.

FIG. 23 is a diagram illustrating an example of a set of faults in an AND gate;

FIG. 24 is a flowchart for explaining the operation of the embodiment in FIG. 22;

[Explanation of symbols]

 Reference Signs List 50 logic synthesis processing device 51 control device 52 sum-of-products storage table 53 input device 54, 54a logical expression data 55 output device 56, 56a circuit diagram 60 aggregate data processing device 61 control device 62 order table 63 node table

Claims (5)

(57) [Claims] 1. An order table for giving a fixed order to each of a plurality of input variables x constituting logic function data, a plurality of intermediate nodes and two terminal nodes t0, A node table for storing a binary tree-like graph composed of a combination of t1 and one input variable x relating to each of the intermediate nodes, and a destination 2 when 0 and 1 are assigned to the input variable x. Branches e0, e
And a first input variable x1 recorded in the order table.
Is decomposed into two partial logical functions by substituting 0 and 1 for each of the partial logical functions. For each of the partial logical functions, 0 and 1 are substituted for the second input variable x2 of the order table, and 2 Performing expansion processing for decomposing into two partial logic functions, and thereafter repeating the same expansion processing for all input variables x according to the order shown in the order table,
The expansion obtained by the series of expansion processing is expressed by the intermediate node and the terminal nodes t0 and t1 to generate the binary tree-like graph, and the intermediate node and the terminal node t0 constituting the binary tree-like graph , T1 in the node table, and before the new intermediate node a is generated and stored in the node table during the expansion processing, the same input variable x and branch e0, It is checked whether or not an equivalent intermediate node b having e1 already exists in the node table. If an existing intermediate node b already exists, a new intermediate node a should not be generated and the intermediate node a should be pointed to. Means for causing a branch to point to the intermediate node b and sharing the intermediate node; and one branch e1 of a new intermediate node a during the expansion processing.
Directly points to the end node t0, the intermediate node a is not generated, and the branch pointing to the intermediate node a is directly pointed to the destination of the other branch e0, thereby preventing generation of a redundant intermediate node. A logic function data processing device, comprising: means for performing non-redundancy. 2. The logical function data processing device further comprises a number table for associating subset data composed of arbitrary elements in the aggregate data composed of a plurality of elements with the logical function data. The table includes each element of the set data and different integer numbers of 0 or more assigned to each element, and associates each digit when the integer number is represented by a binary number with each of the input variables x. , The logic function data takes the value 1 when the element corresponding to the integer number represented by the binary number which each input variable x constitutes is included in the subset data, and takes the value 0 otherwise. 2. The logic function data processing device according to claim 1, wherein: 3. Each set of binary digits of a set of data representing an ON set of a logic circuit in the form of a sum of product terms, using a binary number of digits equal to the total number of literals constituting the product terms Of 0
And 1 are associated with the presence or absence of the literal, the product term is represented by different binary numbers, the ON set is represented as a logical function, and a logic circuit designing apparatus that designs a logical circuit based on the logical function , A number table indicating a correspondence between the product term and the binary number, an order table for giving a fixed order to each of the literals, a plurality of intermediate nodes and two terminations representing logical values of 0 and 1 In a node table for storing a binary tree-like graph composed of a combination of nodes t0 and t1, two literals representing one literal relating to each of the intermediate nodes and a destination when 1 and 0 are substituted into the literals A node table having an area for storing the branches e0 and e1, and a first literal recorded in the order table,
An expansion process of substituting 0 and 1 to decompose into two partial logical functions is performed, and for each of the partial logical functions, 0 and 1 are substituted into the second literal of the order table to obtain two partial logical functions. The same expansion processing is repeated for all the literals in the order shown in the order table, and the expansion obtained by the series of expansion processing is performed on the intermediate node and the end nodes t0 and t1. Means for generating the above-mentioned binary tree-like graph, and storing intermediate nodes and terminal nodes t0 and t1 constituting the binary-tree-like graph in the node table; Before generating the node a and storing it in the node table, an equivalent intermediate node b having the same literals and branches e0 and e1 as the intermediate node a Checks whether the node already exists in the node table. If the node already exists, a new intermediate node a is not generated, and a branch pointing to the intermediate node a points to the intermediate node b. Means for sharing the intermediate node, and one branch e1 of a new intermediate node a during the expansion processing.
Directly points to the end node t0, the intermediate node a is not generated, and the branch pointing to the intermediate node a is directly pointed to the destination of the other branch e0, thereby preventing generation of a redundant intermediate node. Means for performing non-redundancy; and an input terminal of the logic circuit and an AND according to a literal including a product term obtained by the sharing and redundancy.
A logic function data processing device comprising: means for connecting an input terminal of an element on a circuit diagram; and means for connecting each output of the AND element to one OR element on the circuit diagram. 4. The logic function data processing device further uses a NAND element and a NOR element by generating a circuit in which the AND element and the OR element are combined and performing equivalent replacement on the circuit. The logic function data processing device according to claim 3, wherein the logic function data processing device generates a circuit. 5. A signal having a value of 0 or 1 on a signal line of a logic circuit.
When it is assumed that a fault fixed at a plurality of locations occurs at each of the signal lines, a set of faults that makes the signal value on the signal line different from a normal value is output from the input terminal to the output terminal of the logic circuit. In the fault diagnosis apparatus, which sequentially calculates using a set operation in accordance with the logic of the circuit and obtains a set of faults that affect the signal value of the output of the logic circuit, Using a binary number of digits equal to the total number of 1's and 0's in each digit of the binary number
Means for expressing the set data of the faults by a logical function, an order table for giving a fixed order to each of the faults, a plurality of intermediate nodes and logical values of 0 and 1 Is a node table for storing a binary tree-like graph consisting of a combination of two terminal nodes t0 and t1 representing a fault, one fault relating to each of the intermediate nodes, and one fault when 1 and 0 are substituted into the fault. A node table having an area for storing two branches e0 and e1 representing a destination; and substituting 0 and 1 into the first fault recorded in the sequence table to decompose the two faults into two partial logic functions Expansion processing is performed, and for each of the partial logical functions, 0 and 1 are substituted for the second fault in the order table, and expansion processing is performed to decompose each of the partial logical functions into two partial logical functions. According to the order indicating the of the sequence table, repeated for all faults, the deployment obtained by the series of development processing intermediate node and the terminating node t
Means for expressing the binary tree-like graph by expressing the binary tree-like graph with 0, t1 and storing intermediate nodes and terminal nodes t0, t1 constituting the binary tree-like graph in the node table; Before generating a new intermediate node a and storing it in the node table, an equivalent intermediate node b having the same fault and branches e0 and e1 as the intermediate node a
Checks whether the node already exists in the node table. If the node already exists, a new intermediate node a is not generated, and a branch pointing to the intermediate node a points to the intermediate node b. Means for sharing the intermediate node, and one branch e1 of a new intermediate node a during the expansion processing.
Directly points to the end node t0, the intermediate node a is not generated, and the branch that should point to the intermediate node a directly points to the destination of the other branch e0, thereby preventing generation of a redundant intermediate node. A failure diagnosis device comprising: means for performing non-redundancy.