Method of finding minimum-cost feedback-vertex sets for a graph

Details Method of finding minimum-cost feedback-vertex sets for a graph Method of finding minimum-cost feedback-vertex sets for a graph

1993-09-27

1996-05-28

Teska, Kevin J.

Boots, shoes, and leggings

364488, 371 223, G06F 1500

Patent

active

055220630

ABSTRACT:
In partial scan testing of integrated circuits, for an arbitrary graph of an integrated circuit, a Boolean function is derived whose satisfying assignments directly correspond to feedback vertex sets of the graph. The Boolean function is then used for determining the minimum cost feedback vertex set. Boolean function representation using Binary Decision Diagrams (BDI)) in logic synthesis is used to solve the problem of representing the Boolean function efficiently, even for large graphs. The determined minimum cost feedback vertex set is used to select those memory elements in the integrated circuit comprising the scan chain.

REFERENCES:
patent: 4493077 (1985-01-01), Agrawal et al.
patent: 4872169 (1989-10-01), Whetsel, Jr.
patent: 4894830 (1990-01-01), Kawai
patent: 5043986 (1991-08-01), Agrawal et al.
patent: 5434794 (1995-07-01), Coudert et al.
Bryant, "Graph-Based Algorithms for Boolean Function Manipulation", IEEE 1986, pp. 677-691.
Madre et al., "Automating the Diagnosis and the Rectification of Design Error with PRIAM", IEEE 1989, pp. 30-33.
Mailhot et al., "Algorithms for Technology Mapping Based on Binary Decision Diagrams and on Boolean Operations", IEEE 1993, pp. 599-620.
Malik et al., "Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment", IEEE 1988, pp. 6-9.
Bennetts et al., "Partial Scan: What Problem does it Solve?" IEEE 1993, pp. 99-106.
Cheng et al., "A Partial Scan Method for Sequential Circuits with Feedback", IEEE 1990, pp. 544-548.
Chickermane et al., "An optimization Based Approach to the Partial Scan Design Problem", IEEE 1990, pp. 377-386.
Park et al., "An Efficient Method for Finding a Minimal Feedback ARC Set in Directed Graphs", IEEE 1992, pp. 1863-1866.
Park et al., "A Graph Theoretic Approach to Partial Scan Design by K-Cycle Elimination", IEEE 1992, pp. 303-311.
Smith et al., "The Identification of a Minimal Feedback Vertex Set of a Directed Graph", IEEE 1975, pp. 9-15.
Akers, "Binary Decision Diagrams", IEEE 1978, pp. 509-516.
Kwang-Ting Cheng et al., "An Economical Scan Design for Sequential Logic Test Generation", FTCA-19, pp. 1-8, Apr. 3, 1989.
D. H. Lee et al., "On Determining Scan Flip-Flops in Partial-Scan Designs", Proceedings of the Int'l Conf on Computer-Aided Design, pp. 322-325.
Proceedings of the Int'l Test Conference, pp. 303-311, Oct. 1992.
Vivek Chickermane et al., "An Optimization Based Approach to the Partial Scan Design Problem", Proceedings of Int'l Test Conference, pp. 377-386, Oct. 1990.
Vivek Chickermane et al., "A Fault Oriented Partial Scan Design Approach", Proceedings of the Int'l Conference on Computer-Aided Design, pp. 400-403, Nov. 1991.
George W. Smith et al., "Vertex Set of a Directed Graph", IEEE Transactions on Circuits and Systems, vol. CAS-22, p. 1, Jan. 1975.
Erwin Trischler, "Incomplete Scan Path with an Automatic Test Generation Methodology", 1980 IEEE Test Conference, Paper 7.1, pp. 153-162.

Affiliated with

Also associated with

Rating

Method of finding minimum-cost feedback-vertex sets for a graph does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of finding minimum-cost feedback-vertex sets for a graph , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of finding minimum-cost feedback-vertex sets for a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-794907