Space compactor design in VLSI circuits based on graph theoretic concepts

The realization of a space-efficient support hardware for built-in self-testing (BIST) is of immense significance in the synthesis of very large scale integration (VLSI) circuits. This paper presents a new zero-aliasing compaction approach of test data outputs with an application specifically targeted to digital embedded cores-based system-on-chips (SOCs), which facilitates the design of such space-efficient BIST support hardware. The suggested technique takes advantage of some well-known concepts of conventional switching theory, together with those of strong and weak compatibilities of response data outputs in the selection of specific gates for merger of an arbitrary but optimal number of output bit streams from the module under test (MUT), 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 realized without any modification of the MUT, 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 ISCAS 85 combinational benchmark circuits using simulation programs ATALANTA, FSIM, and COMPACTEST, confirming the usefulness of the approach for its simplicity, resulting low area overhead, and full fault coverage for single stuck-line faults, thereby making it suitable in a VLSI design environment. With advances in computational resources in the future, the heuristics adopted in the design algorithm may be further improved upon to significantly lower the simulation CPU time and storage