A system and method for modeling digital circuit elements to enable verification of circuit design by formal proofs using a computerized theorem proving system, is disclosed.

An automatic test pattern generator and process assigns value-strength number to selected nodes representing the electrical characteristic strength of integrated circuits including field effect transistors and the logic state values at those nodes. These value-strength numbers become sensitized to the inputs of the selected node and become propagated to outputs of the selected node for establishing patterns for test signals. The test signals later become used in chip testers for determining good and bad integrated circuit chips. The value-strength numbers also become used in dynamic testing of the integrated circuit nodes by using clock signals of the integrated circuit to establish a transition at a start node of a test path. Within a known clock period later, the transition should become captured at an end node of the test path.

Disclosed is a method and apparatus for generating a test sequence to test a fault in a digital circuit. According to this method and apparatus, when a fault propagation process for a fault, for which a test sequence is generated is not successful, at least a segment of a path to propagate the effects of the fault is memorized as illegal information., And the fault propagation process is restarted for the same fault without selecting the illegal information. Hence, the chance of a successful fault propagation process is increased, which leads to the improvement of the fault coverage. In addition, according to the apparatus and method, it is detected whether a state transition goes into a loop (i.e., two identical states exist) in the state initialization process and then the process is restarted by defining the state caused the loop as an illegal state. Hence, the chance of a successful state initialization process is increased, which leads to the improvement of the fault coverage.

Faster, yet, completely efficient and exhaustive testing is afforded an entity (e.g., protocol, VLSI circuit, software application) represented as finite state machines by employing the present method in which test sequences are generated according to minimum cost function rules. Minimum cost unique signatures are developed for state identification of the finite state machine. Based upon the minimum cost unique signatures, a minimum cost test sequence is generated to cover every state transition of the finite state machine. As a result, every testable aspect of the entity is guaranteed to be tested using a minimum number of steps which represents a considerable cost savings.

An algebraic recursion process is defined to solve test conditions for sequential and combinatorial logic devices. The process is shown to be effective in identifying external pin faults, and is valid for in-circuit test conditions. Since only external pin faults are considered, there is no issue of the correspondence of Boolean products to the internal architecture of the device. Processes to identify the fault detection equation and initialization sequence are described and an effective minimization process presented. Functions simple enough to be implemented by logic networks fall within a range which is computationally tractable by the process of the invention.