An efficient, unified algorithm,Advanced Two-Phase Cluster Partitioning, is proposed for automated synthesisof pseudo-exhaustive test generator for Built-In Self-Test (BIST) design. A prototype of the algorithm,Two-Phase Cluster Partitioning, has been proposed and the hierarchical design procedure is computationally efficientand produces test generation circuitry with low hardware overhead. However, in certain worst case, the algorithmmay generate a sub-optimal design which requires more test patterns and/or hardware overhead. In order togenerate a globally optimal design, further improvement of two-phase algorithm can be achieved by expandingthe design space for the formation of linear sum so that the number of test signals required for pseudo-exhaustivetesting can be reduced. We demonstrate the effectiveness of our approach by presenting detailed comparisons ofour results against those that would be obtained by existing techniques.
展开▼