On a new graph theory approach to designing zero-aliasing space compressors for built-in self-testing

Abstract

Built-in self testing (BIST) schemes that compress the test responses from k-output circuit to q signature streams, q << k, are known as space compactors. In this thesis, we use compression techniques in digital core based systems to facilitate deterministic or pseudorandom testing. Our objective is to minimize the storage requirement of the module under test (MUT) and also to obtain the maximum fault coverage. The objective is to achieve the same fault coverage as obtained without the compactors. We use some well known switching theory techniques, like cover table and frequency ordering, to the compression schemes. Clique detection algorithm is used to find out the maximal compatibility classes (MCCs) of the MUT outputs. In designing zero-aliasing space compressors, the concept of strong and weak compatibilities of response approach is considered, and in most cases maximal compaction is achieved. The techniques used in this thesis are simple designs that have high or full fault coverage for single stuck-line faults and acceptable area overhead. We used ISCAS 85 combinational benchmark circuits and ISCAS 89 sequential scan circuits with ATALANTA and FSIM simulation programs to simulate the suggested approaches.