A pattern ordering algorithm for reducing the size of fault dictionaries

Determining the relation between defects and faults (fault diagnosis) in digital circuits is a key concept for semiconductors production yield improvement. Nowadays, fault diagnosis requires heavy computations and large data structures. This paper proposes a novel technique for reducing fault dictionary size for combinational and scanned circuits by means of pattern-ordering. The proposed algorithm manipulates conventional tree-based fault dictionaries. In such structures, faults are diagnosed by traversing the tree from its root to a leaf; we aim at globally reducing the length of such paths by a modified patterns order, thus also reducing the dictionary size. This approach does not cause any loss of information, since it is demonstrated for combinational circuits that the ability of a pattern set in diagnosing faults remains unaltered when modifying the patterns order. The effectiveness of the proposed approach is demonstrated for a set of sequential benchmarks equipped with scan chains