Topology-based computer-aided design system for digital circuits

Details Topology-based computer-aided design system for digital circuits Topology-based computer-aided design system for digital circuits

Filed on

1995-03-03

Date issued

1997-07-15

Examiner

Teska, Kevin J.

Patent Class

Boots, shoes, and leggings

Other Related Categories

364491, 371 671, G06F 1750, G06F 9455

Type

Patent

Status

active

Patent number

056491654

Description

ABSTRACT:
A computer-aided design system and method thereof for performing logic design analysis for determining logical interdependencies between points in a digital circuit topology. Such a topology comprises a set of primary outputs and a set of primary inputs, both interconnected with logic gates. The logic gates are interconnected by wires. Each such point comprises a location on a wire carrying a signal asserted into or from one of the logic gates. A representation of such topology is stored in a storage device in the computer-aided design system. A cutset in the topology is selected comprising the logic gates falling in a fan-in of the logic gates leading to a target one of the logic gates. A decision diagram is built for logic gates in the cutset leading from the target logic gate. The logic gates in a potential learning area in the topology are marked. Justification vectors are extracted from the decision diagram for a predetermined Boolean value of the target logic gate. Such logical interdependencies are determined and a representation of the logical interdependencies is stored in a storage device in the computer-aided design system. Boolean operations are performed between the decision diagram and a plurality of other decision diagrams for the logic gates in the potential learning area.

REFERENCES:
patent: 5243538 (1993-09-01), Okuzawa et al.
patent: 5349659 (1994-09-01), Do et al.
patent: 5377201 (1994-12-01), Chakradhar et al.
patent: 5379231 (1995-01-01), Pillage et al.
patent: 5481473 (1996-01-01), Kim et al.
patent: 5485471 (1996-01-01), Bershteyn
patent: 5497334 (1996-03-01), Russell et al.
patent: 5522063 (1996-05-01), Ashar et al.
patent: 5526514 (1996-06-01), Pradhan et al.
patent: 5528508 (1996-06-01), Russell et al.
patent: 5541849 (1996-07-01), Rostoker et al.
patent: 5544066 (1996-08-01), Rostoker et al.
patent: 5553002 (1996-09-01), Dangelo et al.
patent: 5557531 (1996-09-01), Rostoker et al.
patent: 5572436 (1996-11-01), Dangelo et al.
patent: 5572437 (1996-11-01), Rostoker et al.
S. Malik et al., Logic Verification Using Binary Decision Diagrams in a Logic Synthesis Environment, Int'l Conf. on Computer-Aided Design, pp. 6-9 (1988).
M. Fujita et al., Evaluation and Improvements of Boolean Comparison Methods Based on Binary Decision Diagrams, Int'l Conf. on Computer-Aided Design, pp. 2-5 (1988).
C.L. Berman & L.H. Trevyllian, Functional Comparison of Logic Designs for VLSI Circuits, Int.'Conf. on Computer-Aided Design, pp. 456-459 (1989).
D. Brand, Verification of Large Synthesized Designs, Int'l Conf. on Computer-Aided Design, pp. 534-537 (1993).
E. Cerny & C. Mauras, Tautology Checking Using Cross-Controllability and Cross-Observability Relations, Int'l Conf. on Computer-Aided Design, pp. 34-37 (1990).
W. Kunz, HANNIBAL: An Efficient Tool for Logic Verification Based on Recursive Learning, Int'l Conf. on Computer-Aided Design, pp. 538-543 (1993).
Schulz et al., SOCRATES: A Highly Efficient Automatic Test Pattern Generation System, Int'l Test Conf., pp. 1016-1026 (1987).
K. Karplus, Using If-Then Else DAGs For Multi-Level Minimization, Decennial Caltech Conference on VLSi (May 1989).
M. Abramovici et al., Digital Systems Testing and Testable Design, Computer Science Press pp. 101-117 (1990).
R.E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, vol. C-35, No. 8, pp. 677-691 (Aug. 1986).
Schulz et al., Advanced Automatic Test Pattern Generation and Redundancy Identification Techniques, Fault Tolerant Computing Symposium-18, pp. 30-35 (1988).
R. Rudell, Dynamic Variable Ordering for Ordered Binary Decision Diagrams, Int'l Conf. on Computer-Aided Design, pp. 42-47, (1993).
R. Drechsler et al., Efficient Representation and Manipulation of Switching Functions Based on Ordered Kronecker Functional Decision Diagrams, 31st ACM/IEEE Design Automation Conference, pp. 415-419, (1994).
S.T. Chakradhar et al., A Transitive Closure Algorithm for Test Generation, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, No. 7, pp. 1015-1027, (Jul. 1993).
R.E. Bryant, Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams, ACM Computing Surveys, vol. 24, No. 3, pp. 293-318, (Sep. 1992).
O. Coudert et al., A Unified Framework for the Formal Verification of Sequential Circuits, Int'l Conf. on Computer-Aided Design, pp. 126-129 (1990).
W. Kunz et al., Recursive Learning: An Attractive Alternative to the Decision Tree for Test Generation in Digital Circuits, Int'l Test Conf., pp. 816-825, (1992).
R. Mukherjee et al., Functional Learning: A New Approach to Learning in Digital Circuits, Technical Report 94-020, Dept. of Computer Science, Texas A&M University, pp. 1-15, (1994).

Affiliated with

Also associated with

Rating

Topology-based computer-aided design system for digital circuits does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Topology-based computer-aided design system for digital circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topology-based computer-aided design system for digital circuits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1499743