Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1997-11-05
2001-04-03
Lintz, Paul R. (Department: 2768)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06212669
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to the field of computer-aided design (CAD) systems and methods, and in particular to CAD systems and methods for digital circuit design and verification.
Computer-aided design of digital circuits and other complex digital systems is widely prevalent. In such computer-aided design, circuits and systems are usually designed in a hierarchial manner. The requirements of the circuit or system are defined in an abstract model of the circuit or system. The abstract model is then successively transformed into a number of intermediate stages. These intermediate stages often include a register transfer level model which represents a block structure behavioral design, and a structural model which is a logic level description of the system. Eventually a transistor net list and consequently the physical layout of the circuit or system are derived.
The design of the circuit or system therefore proceeds from the general requirements level to the lower detailed level of a physical design, interposed between which are a number of intermediate levels. Each successive level of the design is tested or verified to ensure that the circuit or system continues to meet the design requirements. It is highly desirable to verify each level in the design as errors in one level of the design that are not corrected until after further levels have been designed drastically increases the cost of correcting such errors. Thus, it is important to test each level of the design against the requirements. As each level of the design is tested against the requirements, this task resolves to the task of comparing each level of the design to the prior level of the design. This testing of succeeding levels against immediately preceding levels can also be intuitively seen when it is realized that each succeeding level is often merely an optimization of the preceding level. Thus, the testing or verification of circuit designs can, to an extent, be viewed as similar to checking the backward compatibility of successive generations of circuits or systems.
Binary decision diagrams (BDDs) have been used to solve CAD related problems. These problems include synthesis problems, digital-system verification, protocol validation, and generally verifying the correctness of circuits. BDDs represent Boolean functions. For example,
FIG. 1
shows a circuit comprising first and second OR gates
11
,
13
, and an AND gate
15
. The first OR gate has inputs N
1
and N
2
. The second OR gate has inputs N
2
and N
3
, with input N
2
being shared by the two OR gates. The outputs of the OR gates are fed into the AND gate. The AND gate has an output N
6
. Thus, the output of the AND gate can be represented by the boolean function N
6
=(N
1
OR N
2
) AND (N
2
OR N
3
).
A BDD for this circuit is shown in FIG.
2
. The BDD is composed of vertices, which may also be called nodes, and branches. Vertices from which no further branches extend are termed terminal vertices. The BDD is an Ordered BDD (OBDD) as each input is restricted to appearing only at one level of the BDD. The BDD may be reduced to a Reduced OBDD (ROBDD) as shown in FIG.
3
. The rules for reducing OBDDs are known in the art. These rules include eliminating redundant or isomorphic nodes, and by recognizing that some nodes can be eliminated by exchanging the branches of a node with a node or its complement. The importance of ROBDDs is that ROBDDs are unique, i.e., canonical. Thus, if two OBDDs reduce to the same ROBDD, the circuits represented by the OBDDs are equivalent.
In most applications, ROBDDs are constructed using some variant of the Apply procedure described in R. E. Bryant, Graph-Based Algorithms For Boolean Function Manipulation, IEEE Trans. Computer C-35(8): 667-691, August 1986, incorporated by reference herein. Using the Apply procedure the ROBDD for a gate g is synthesized by the symbolic manipulation of the ROBDDs of gate g's inputs. Given a circuit, the gates of the circuit are processed in a depth-first manner until the ROBDDs of the desired output gates are constructed.
A large number of problems in VLSI-CAD and other areas of computer science can be formulated in terms of Boolean functions. Accordingly, ROBDDs are useful for performing equivalence checks. A central issue, however, in providing computer aided solutions and equivalence checking is to find a compact representation for the Boolean functions so that the equivalence check can be efficiently performed. ROBDDs are efficiently manipulable, and as previously stated, are canonical. In many practical functions ROBDDs are compact as well, both in terms of size (memory space) and computational time. Accordingly, ROBDDs are frequently used as the Boolean representation of choice to solve various CAD problems.
ROBDDs, however, are not always compact. In a large number of cases of practical interest, many ROBDDs representing a circuit or system described by a Boolean function may require space which is exponential in the number of primary inputs (PIs) to the circuit or system. This makes solving for equivalence an NP-hard problem. The large space requirement, either in terms of memory or computational time, places limits on the complexity of problems which can be solved using ROBDDs.
Various methods have been proposed to improve the compactness of ROBDDs. Some of these methods improve compactness, but do not maintain canonicity and manipulability of the ROBDDs. Such methods reduce the applicability of the use of ROBDDs. Other methods, which maintain canonicity and manipulability, represent the function over the entire Boolean space as a single graph rooted at an unique source. A requirement of a single graph, however, may still result in ROBDDs of such a size that either memory or time constraints are exceeded.
Methods of reducing the size of ROBDDs have been proposed. The size of an ROBDD is strongly dependent on its ordering of variables. Therefore, many algorithms have been proposed to determine variable orders which reduce the size of ROBDDs. For some Boolean functions, however, it is possible that no variable order results in a ROBDD sufficiently small to be useful, or that no such variable order can be efficiently found.
The space and time requirements of ROBDDs may also be reduced by relaxing the total ordering requirement. A Free BDD is an example of such an approach. A Free BDD (FBDD) is a BDD in which variables can appear only once in a given path from the source to the terminal, but different paths can have different variable orderings.
Another approach to obtain a more compact representation for Boolean functions is to change the function decomposition associated with the nodes. Generally, a BDD decomposition is based on the Shannon Expansion in which a function ƒ is expressed as xƒ
x
+{overscore (x)}ƒ
{overscore (x)}
, or methods derived from the Shannon expansion such as the Apply method. Some other decompositions include the Reed-Muller expansion, or the use of expansion hybrids such as Functional Decision Diagrams (FDDs), or through the use of Ordered Kronecker Functional Decision Diagrams (OKFDDs). All of these methods, however, represent a function over the entire Boolean space as a single graph rooted at a unique source. Thus, these methods still face problems of memory and time constraints.
Furthermore, many designs, particularly for sequential circuits, are not adequately verified. Usually a test-suite is prepared to test such designs. The test-suite includes a number of test cases in which the design is subjected to varying combinations of assignments for the primary inputs of the design. A single combination of assignments for the primary inputs forms an input vector. A sequence of input vectors, used to test designs having sequential elements such as flip-flops, forms a test vector.
Test-suites are often prepared by engineers with specialized knowledge of the design being tested. Therefore test-suites are useful test devices. However, test-suites only test a very small portion of a state
Christie Parker & Hale LLP
Do Thuan
Fujitsu Limited
Lintz Paul R.
LandOfFree
Method for verifying and representing hardware by... 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 for verifying and representing hardware by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for verifying and representing hardware by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2472297