Designing Zero-Aliasing Space Compressors - Graph Theory Approach

S.R. Das, A. Hossain, A.R. Nayak, E.M. Petriu (Canada), S. Biswas, and M. Sahinoglu (USA)


Aliasingfree space compactor, coresbased systemon chip (SOC), maximal compatibility classes (MCCs), maximal minimally strongly connected (MMSC) subgraphs, nonminimally strongly connected (NMSC) pairs of vertices.


The design of space-efficient support hardware for built in self-testing (BIST) is of great significance in the synthesis of VLSI circuits. An approach based on graph theory to designing zero-aliasing space compression hardware for single stuck-line faults is proposed in this paper, extending some of the well-known concepts in switching theory, specifically the notion of compatibility relation as employed in the minimization of incomplete sequential machines, based on optimal generalized sequence mergeability, developed and utilized by the authors in previous works. The suggested compaction technique possesses several advantages over earlier ones, viz. zero-aliasing is achieved here without any modification of the module under test (MUT), and the area overhead and signal propagation delay are relatively low. Besides, the method is suitable for application with both deterministic compacted and pseudorandom test vectors. The paper furnishes details of the algorithms required in the implementation, based on the criteria of merger for an optimal number of outputs of the MUT to realize maximal compaction in the design, along with results of experiments conducted on ISCAS 85 combinational benchmark circuits, with simulation programs ATALANTA and FSIM.

Important Links:

Go Back