Further Studies on Zero-Aliasing Space Compression Based on Graph Theory

The design of space-efficient support hardware for built-in self-testing (BIST) is of great significance in the realization of present day very large scale integration (VLSI) circuits and systems, particularly in the context of design paradigm shift from system-onboard to system-on-chip (SOC). This paper revisits the problem of designing zero-aliasing space compression hardware in relation to embedded cores-based SOC for single stuck-line faults in particular, extending the well-known concepts of switching theory, and of incompatibility relation to generate maximal compatibility classes (MCCs) utilizing new graph theory concepts, based on optimal generalized sequence mergeability as developed by the authors in earlier works. The paper briefly presents the mathematical basis of selection criteria for merger of an optimal number of outputs of the module under test (MUT) for realizing maximal compaction ratio in the design, along with some experimental results on ISCAS 89 full-scan sequential benchmark circuits, with simulation programs ATALANTA and FSIM.