On-line partitioning for sequential circuit test generation

Abstract

A method of solving a test generation problem for sequential circuits is disclosed. The method comprises recursively dividing an original test generation problem into smaller problems, wherein said sub-problems may be dependent while one or more of said dependent sub-problems may have solution-specific independence, finding solutions for said sub-problems, reusing solutions for dependent sub-problems, whenever the dependent sub-problems enjoy solution-specific independence; and identifying a minimal subset of conflicting objectives if a sub-problem that has to be solved to achieve multiple objectives has no solution. A test generation system comprising a computer, said computer having a cpu and memory, said memory comprising instructions capable of implementing components of said system. The components comprise a test generation problem solver that recursively solves test generation problems wherein solutions for sub-problems are reused, a problem partitioner that receives test generation problems and partitions said test generation problems into sub-problems wherein said sub-problems may be dependent and wherein said sub-problems may have solution-specific dependence, a consistent label checker that receives the test generation problem from the problem solver and determined if there is consistent labeling, a partition merger that merges a subset of sub-problems if no solution exists for said subset of sub-problems and if said subset of sub-problems are dependent and a conflict set generator that generates a conflict set of objectives that prevents a specific sub-problem from having a solution.