We present new extensions to the EST' algoritlm, which accelerates combinational circuit Redundancy Identification and Automatic Test Pattern Generation (ATPG) algorithms, in particular SOCRATES. EST detects equivalent search states, which are saved. for all faults during ATPG. The search space is reduced by using learned Search State equiualences to detect previously-encountered search states (possibly from prior faults) and to make internal node assignments. We present two extensions to EST. The first ensures that each portion of the ATPG search space is explored only once. The second applies headline objectives in parallel, rather than serially. For the 1965 ISCAS combinational benchmarks, EST accelerates S 0 CRATES by 6.53 times, when all faults are targeted, and by 5.51 times, when used with random pattern generation, f,iult simulation and fault dropping. This acceleration was achieved with minimal memory overhead.

We present a new algorithm, EST, that accelerates any combinatorial circuit Automatic Test-Pattern Generation algorithm. EST detects equivalent search states, which are saved for all faults during ATPG. The search space is reduced by using Binary Decision Diagram fragments to detect previously-encountered search states (possibly from prior faults). Search terminates earlier than before. Redundant fault analysis further accelerates ATPG. ATPG is accelerated 1347 times for hard-to-test faults in the ISCAS '85 benchmarks.

The average number of prime k-cubes and essential k-cubes in an n-variable, single-output Boolean function has already been obtained combinationally. The authors show how the same quantities can be obtained geometrically, using the theory of random clumping and take an initial step in calculating, for k-cubes in the minimized form of a function. The authors compare their results to minimizations produced by ESPRESSO and a cruder algorithm.>