Circuit partitioning for efficient logic BIST synthesis

A divide-and-conquer approach using circuit partitioning is presented, which can be used to accelerate logic BIST synthesis procedures. Many BIST synthesis algorithms contain steps with a time complexity which increases more than linearly with the circuit size. By extracting sub-circuits which are almost constant in size, BIST synthesis for very large designs may be possible within linear time. The partitioning approach does nor require any physical modifications of the circuit under test. Experiments show that significant performance improvements can be obtained at the cost of a longer test application time or a slight increase in silicon area for the BIST hardware.