System and method for processing logic function and fault diagnosis using binary tree representation

A logic circuit design system for designing a logic circuit on the basis of a logic function representing an on-set of the logic circuit, which is represented in the form of a sum of cubes, by representing the cubes by different binary numbers whose number of digits is equal to the total number of literals constituting the cubes, values 1 and 0 of each digit position of the binary numbers being associated with the presence and absence of each one of the literals, said design system comprising:

• a number table representing correspondence between the cubes and the binary numbers;
• an ordering table providing a fixed order to each one of the literals;
• a node table for storing a binary tree graph consisting of a plurality of intermediate nodes and two types of terminal nodes t0 and t1 representing logic values 0 and 1, respectively, said node table being provided with areas, each of which stores one of said literals associated with each one of the intermediate nodes, and two edges e0 and e1 representing destinations obtained by substituting 0 and 1 into the literal, respectively;
• means for performing an expanding processing that substitutes 0 and 1 into a first literal recorded in the ordering table to obtain a first two subfunctions of the logic function, for performing an expanding processing that substitutes 0 and 1 into a second literal recorded in the ordering table to obtain a second two subfunctions for each of the first two subfunctions, for iterating a similar expanding processing on all the remaining literals in accordance with the order recorded in the ordering table, for generating the binary tree graph by representing expanded results, which are obtained by the expanding processings, by the intermediate nodes and terminal nodes t0 and t1, and for storing the intermediate nodes and terminal nodes t0 and t1 constituting the binary tree graph into the node table;
• means for testing, during the expanding processing and before generating a new intermediate node A and storing it into the node table, whether a node B, which is equivalent to the node A in the sense that the node B has the same literal and the same edges e0 and e1 as the node A, is already present in the node table, and for performing sharing, if the equivalent node B is already present in the node table, of the nodes A and B by not generating the new node A, and by making an edge pointing to the node A point to the node B;
• and
• means for performing, during the expanding processing and if the edge e1 of a new intermediate node A directly points to a terminal node t0, node reduction by not generating the intermediate node A, and by making an edge pointing to the intermediate node A point to a destination of the other edge e0 of the intermediate node A.

A fault diagnosis system for obtaining a set of faults of a logic circuit when a plurality of faults are assumed to take place in the logic circuit, each of the faults fixing a signal on a signal line of the logic circuit at 0 or 1, and having influence on an output signal of the logic circuit, said set of faults, which makes a signal value on a signal line different from a normal value on the signal line, being sequentially calculated from an input terminal to an output terminal of the logic circuit by using set operations in accordance with the logic of the logic circuit, said fault diagnosis system comprising:

• means for associating values 1 and 0 of each digit position of binary numbers, whose number of digits is equal to the total number of faults assumed to take place, with the presence and absence of each one of the faults, thereby representing the set of faults by a logic function;
• an ordering table providing a fixed order to each one of the faults;
• a node table for storing a binary tree graph consisting of a plurality of intermediate nodes and two types of terminal nodes t0 and t1 representing logic values 0 and 1, respectively, said node table being provided with areas, each of which stores one of said faults associated with each one of the intermediate nodes, and two edges e0 and e1 representing destinations obtained by substituting 0 and 1 into a fault, respectively;
• means for performing an expanding processing that substitutes 0 and 1 into a first fault recorded in the ordering table to obtain a first two subfunctions of the logic function, for performing an expanding processing that substitutes 0 and 1 into a second fault recorded in the ordering table to obtain a second two subfunctions for each of the first two subfunctions, for iterating a similar expanding processing on all the remaining faults in accordance with the order recorded in the ordering table, for generating the binary tree graph by representing expanded results, which are obtained by the expanding processings, by the intermediate nodes and terminal nodes t0 and t1, and for storing the intermediate nodes and terminal nodes t0 and t1 constituting the binary tree graph into the node table;
• means for testing, during the expanding processing and before generating a new intermediate node A and storing it into the node table, whether a node B, which is equivalent to the node A in the sense that the node B has the same fault and the same edges e0 and e1 as the node A, is already present in the node table, and for performing sharing, if the equivalent node B is already present in the node table, of the nodes A and B by not generating the new node A, and by making an edge pointing to the node A point to the node B;
• and
• means for performing, during the expanding processing and if the edge e1 of a new intermediate node A directly points to a terminal node t0, node reduction by not generating the intermediate node A, and by making an edge pointing to the intermediate node A point to a destination of the other edge e0 of the intermediate node A.

A logic function data processing method using an ordering table providing a fixed order to a plurality of input variables x constituting logic function data, and a node table for storing a binary tree graph consisting of a plurality of intermediate nodes and two types of terminal nodes t0 and t1representing logic values 0 and 1, respectively, said node table being provided with areas, each of which stores one of said input variables x associated with each one of the intermediate nodes, and two edges e0 and e1 representing destinations obtained by substituting 0 and 1 into the input variable x, respectively, said method comprising the steps of:

• performing an expanding processing that substitutes 0 and 1 into a first input variable x1 recorded in the ordering table to obtain a first two subfunctions of the logic function;
• performing an expanding processing that substitutes 0 and 1 into a second input variable x2 recorded in the ordering table to obtain a second two subfunctions for each of the first two subfunctions;
• iterating a similar expanding processing on all the remaining input variables in accordance with the order recorded in the ordering table;
• generating the binary tree graph by representing expanded results, which are obtained by the expanding processings, by the intermediate nodes and terminal nodes t0 and t1;
• storing the intermediate nodes and terminal nodes t0 and t1 constituting the binary tree graph into the node table;
• testing, during the expanding processing and before generating a new intermediate node A and storing it into the node table, whether a node B, which is equivalent to the node A in the sense that the node B has the same input variable x and the same edges e0 and e1 as the node A, is already present in the node table;
• performing sharing, if the equivalent node B is already present in the node table, of the nodes A and B by not generating the new node A, and by making an edge pointing to the node A point to the node B;
• and
• performing, during the expanding processing and if the edge e1 of a new intermediate node A directly points to a terminal node t0, node reduction by not generating the intermediate node A, and by making an edge pointing to the intermediate node A point to a destination of the other edge e0 of the intermediate node A.

A logic circuit design method for designing a logic circuit on the basis of a logic function representing an on-set of the logic circuit, which is represented in the form of a sum of cubes, by representing the cubes by different binary numbers whose number of digits is equal to the total number of literals constituting the cubes, values 1 and 0 of each digit position of the binary numbers being associated with the presence and absence of each one of the literals, the design method using a number table representing correspondence between the cubes and the binary numbers, an ordering table providing a fixed order to each one of the literals, and a node table for storing a binary tree graph consisting of a plurality of intermediate nodes and two types of terminal nodes t0 and t1 representing logic values 0 and 1, respectively, said node table being provided with areas, each of which stores one of said literals associated with each one of the intermediate nodes, and two edges e0 and e1 representing destinations obtained by substituting 0 and 1 into the literal, respectively, said design method comprising the steps of:

• performing an expanding processing that substitutes 0 and 1 into a first literal recorded in the ordering table to obtain a first two subfunctions of the logic function;
• performing an expanding processing that substitutes 0 and 1 into a second literal recorded in the ordering table to obtain a second two subfunctions for each of the first two subfunctions;
• iterating a similar expanding processing on all the remaining literals in accordance with the other recorded in the ordering table;
• generating the binary tree graph by representing expanded results, which are obtained by the expanding processings, by the intermediate nodes and terminal nodes t0 and t1;
• storing the intermediate nodes and terminal nodes t0 and t1 constituting the binary tree graph into the node table;
• testing, during the expanding processing and before generating a new intermediate node A and storing it into the node table, whether a node B, which is equivalent to the node A in the sense that the node B has the same literal and the same edges e0 and e1 as the node A, is already present in the node table;
• performing sharing, if the equivalent node B is already present in the node table, of the nodes A and B by not generating the new node A, and by making an edge pointing to the node A point to the node B;
• and
• performing, during the expanding processing and if the edge e1 of a new intermediate node A directly points to a terminal node t0, node reduction by not generating the intermediate node A, and by making an edge pointing to the intermediate node B point to a destination of the other edge e0 of the intermediate node A.

A fault diagnosis method for obtaining a set of faults of a logic circuit when a plurality of faults are assumed to take place in the logic circuit, each of the faults fixing a signal on a signal line of the logic circuit at 0 or 1, and having influence on an output signal of the logic circuit, said set of faults, which makes a signal value on a signal line different for a normal value on the signal line, being sequentially calculated from an input terminal to an output terminal of the logic circuit by using set operations in accordance with the logic of the logic circuit, the method using an ordering table providing a fixed order to each one of the faults, and a node table for storing a binary tree graph consisting of a plurality of intermediate nodes and two types of terminal nodes t0 and t1 representing logic values 0 and 1, respectively, said node table being provided with areas, each of which stores one of said faults associated with each one of the intermediate nodes, and two edges e0 and e1 representing destinations obtained by substituting 0 and 1 into a fault, respectively, said fault diagnosis method comprising the step of:

• associating values 1 and 0 of each digit position of binary numbers, whose number of digits is equal to the total number of faults assumed to take place, with the presence and absence of each one of the faults, thereby representing the set of faults by a logic function;
• performing an expanding processing that substitutes 0 and 1 into a first fault recorded in the ordering table to obtain a first two subfunctions of the logic function;
• performing an expanding processing that substitutes 0 and 1 into a second fault recorded in the ordering table to obtain a second two subfunctions for each of the first two subfunctions;
• iterating a similar expanding processing on all the remaining faults in accordance with the order recorded in the ordering table, for generating the binary tree graph by representing expanded results, which are obtained by the expanding processings, by the intermediate nodes and terminal nodes t0 and t1;
• storing the intermediate nodes and terminal nodes t0 and t1 constituting the binary tree graph into the node table;
• testing, during the expanding processing and before generating a new intermediate node A and storing it into the node table, whether a node B, which is equivalent to the node A in the sense that the node B has the same fault and the same edges e0 and e1 as the node A, is already present in the node table;
• performing sharing, if the equivalent node B is already present in the node table, of the nodes A and by not generating the new node A, and by making an edge pointing to the node A point to the node B;
• and
• performing, during the expanding processing and if the edge e1 of a new intermediate node A directly points to a terminal node t0, node reduction by not generating the intermediate node A, and by making an edge pointing to the intermediate node A point to a destination of the other edge e0 of the intermediate node A.