One method of reducing the difficulty of test generation for sequential circuits is by the use of full scan design. To overcome the large extra hardware overhead attendant in the full scan design, the concept of partial scan designs has emerged. With the sequential circuit modeled as a directed graph, much effort has been expended to remove the subset of arcs or vertices representing flip-flops (FF). First we describe an efficient algorithm for finding a minimum feedback arc set that breaks all cycles in directed graphs. A sequential ordering technique based on depth-first search and an efficient cut algorithm are discussed. We also introduce an efficient algorithm to find a Minimum Feedback Vertex Set (MFVS) in directed graphs. This algorithm is based on the removal of essential cycles in which no subset of vertices constitutes a cycle. Then cycles whose length are greater than K are removed under the observation that the complexity of test generation in the sequential circuits is often caused by the lengthy cycles (synchronization sequence). A new structure called a totally combinationalized structure is developed to simplify the problems of test generation and fault simulation for sequential circuits to those for combinational circuits. This structure requires less scan FFs than full scan design and totally combinationalizes the sequential problem. The FFs in the sequential circuits are dedicated Test Pattern Generators and Test Response Compressors in Built-In Self-Test. Most of the benchmark circuits are known to be parity-even. However, it is the parity-odd circuits that are likely to detect most of the faults using a parity-bit checker test response compressor. After investigating parity testable faults, a novel technique which imposes linear constraints among primary inputs is described which changes most of the primary outputs to parity-odd and also compacts the test signals. It is shown that high fault coverage can be obtained by combining both MISR and the parity-bit checker.
Identifer | oai:union.ndltd.org:UMASS/oai:scholarworks.umass.edu:dissertations-8501 |
Date | 01 January 1992 |
Creators | Park, Sung Ju |
Publisher | ScholarWorks@UMass Amherst |
Source Sets | University of Massachusetts, Amherst |
Language | English |
Detected Language | English |
Type | text |
Source | Doctoral Dissertations Available from Proquest |
Page generated in 0.0018 seconds