Single-pass methods for generating test patterns for combinational circuits

A single-pass method for automatic test pattern generation in a combinational circuit, the method comprising:

• a step for providing a description of a combinational circuit;
• a step for sorting the description into a circuit-level order;
• a step for providing initial Boolean functions corresponding to circuit primary inputs;
• a step for providing rules for combining Boolean functions;
• a step for applying the rules to the sorted circuit description, in an ascending circuit-level order, beginning from the circuit level of the primary inputs, and proceeding circuit-level-by-circuit-level through the sorted circuit description;
• and
• a step for deriving the test patterns from the results of the applying step for each primary output signal,
• eliminating conditional behavior, and generating all test patterns for all detectable single stuck-at faults in a single pass through the circuit description.

A computer program product for use with a computer system, comprising:

• a computer readable medium;
• means provided on the medium for directing the computer system to perform the following steps, defining a method for generating test patterns for combinational circuits during a single pass through the circuit:
• providing a netlist defining the circuit in terms of circuit signals;
• sorting the netlist into a circuit level order;
• providing initial Boolean functions corresponding to circuit primary input signals;
• providing rules for manipulating Boolean functions and corresponding to netlist defined logic elements;
• determining the highest circuit level at which a signal is used as an input to a circuit logic element;
• processing Boolean functions corresponding to the circuit signals, in an ascending circuit level order, from the circuit level of the primary input signals through the circuit level of the highest-level primary output signal;
• storing the results of the processing;
• releasing storage for the Boolean function corresponding to the signal after Boolean function processing is complete at that highest circuit level use;
• and
• deriving the test patterns from the stored results for the primary output signal(s), such that
• all tests for all detectable single stuck-at faults are generated in a single pass through the netlist.