On a New Graph Theory Approach to Designing Zero-Aliasing Space Compressors for Built-In Self-Testing

The realization of space-efficient support hardware for built-in self-testing (BIST) is of great significance in the design of present-day very large scale integration (VLSI) circuits and systems, particularly in the context of the recent paradigm shift from system-on-board to system-on-chip (SOC). A new approach in designing zero-aliasing space-compaction hardware, specifically in relation to embedded core-based SOC, is proposed in this paper for single stuck-line faults, extending the well-known concepts of conventional switching theory and of incompatibility relation to generate the maximal compatibility classes using graph theoretic concepts, based on optimal generalized sequence mergeability, as developed and applied by the authors in earlier works. This is novel in the sense that zero-aliasing is obtained without any modification of the original module under test, while a maximal compaction is achieved in almost all cases in reasonable time utilizing some simple heuristics. The method is illustrated with design details of space compactors for the international symposium on circuits and systems (ISCAS) 85 combinational and ISCAS 89 full-scan sequential benchmark circuits using simulation programs ATALANTA and FSIM, attesting to the usefulness of the technique for its relative simplicity, resulting in low area overhead, and full fault coverage for single stuck-line faults, thus making it suitable in a VLSI synthesis environment. With advances in computational resources in the future, the heuristics applied in the design algorithm may be further improved upon to significantly lower the simulation CPU time and storage.