Space compactor design in VLSI circuits based on graph theoretic concepts

• Published in: IEEE transactions on instrumentation and measurement 2006-08, Vol.55 (4), p.1106-1118
• Main Authors: Biswas, S., Das, S.R., Petriu, E.M.
• Format: Article
• Language: English
• Subjects: Algorithms; Aliasing-free (zero-aliasing) space compaction; Built-in self-test; built-in self-testing (BIST) in very large scale integration (VLSI); Circuit faults; Circuit synthesis; Circuit testing; Circuits; Compaction; compatibility of response data outputs; Computational modeling; Computer simulation; cores-based system-on-a-chip (SOC); Design engineering; Hardware; Heuristic; Integrated circuits; module under test (MUT); Optimization; Studies; System testing; System-on-a-chip; Very large scale integration
• ISSN: 0018-9456; 1557-9662
• DOI: 10.1109/TIM.2006.876523

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