Comparative Study on Space Compaction by Using Minimal Logic Gate in a Graph Theoretical Approach

Abstract

We try to improve space compaction one stage or multistage use logic gate implementation through graph Theory. We implement Brute Force & Brone Kerbosch theory at this thesis for improve space compaction. The technological development is enabling production of increasingly complex electronic systems. All those systems must be verified and tested to guarantee correct behavior. The established low-level methods for space compaction are not any more sufficient and more work has to be done at abstraction levels higher than the logic gate. This thesis reports on one such work that space compaction techniques. The contribution of this thesis is twofold. First, we investigate the possibilities of space compaction. We have try to developed space compaction for this purpose Brute Force & Brone Kerbosch algorithm. The second part of the thesis concentrates on efficienry & compaction time at space compaction & compeer at another method. We investigate which method is perfect or sufficient at space compaction. We have also developed methods for space compaction implementation graph theory and efficienry of the proposed technique. This thesis presents a new technique for merging output test vectors and compares different types of compacfion methods. The proposed technique takes advantage of some well- known concepts of conventional switching theory, together with the selection of specific gates for merger of an arbitrary but optimal number of output bit streams from the circuit under test. This is a new technique as it is implemented without any modification of the original circuit. But the maximum compaction is achieved in almost all cases within a reasonable time span. The proposed technique is illustrated with design details of space compactors for ISCAS flnternational Symposium on Circuits and Systems) 85 combinational benchmark circuits using simulation programs ATALANTA. The simulation result confirms 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.