Construction of the Tests of Combinational Circuit Failures by Analyzing the Orthogonal Disjunctive Normal Forms Represented by the Alternative Graphs

摘要

A method to design tests for the bit-stuck and arbitrary failures of the elements of combinational circuits was proposed. It is based on a graphical description of the orthogonal disjunctive normal forms of the functions realized by the circuit. The graphical description of the circuit by an alternative graph, which was later named the structurally synthesized binary decision diagram graph, carries, along with information about the circuit structure, the orthogonal disjunctive normal forms of the functions of this circuit. The properties of the structurally synthesized binary decision diagram graph allow one, on the one hand, to use it for construction of tests of various circuit failures and, on the other hand, to reduce enumeration at determination of the tests owing to the use of the orthogonal disjunctive normal forms realized by the circuit and its subcircuits. A full structurally synthesized binary decision diagram graph that features the potential of the structurally synthesized binary decision diagram graph and does not differ so much from the traditional binary decision diagram graphs was introduced to facilitate explanation of the method. The proposed method of test design enables one to determine the entire set of test patterns by determining successively the conjunctions representing these test.