Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-10-06
2001-06-26
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C703S013000
Reexamination Certificate
active
06253365
ABSTRACT:
BACKGROUND OF THE INVENTION
Problem
Digital circuits are classified as being either combinational or sequential. A combinational type circuit consists only of logic gates (INVERTER, AND, OR) to implement a truth table or a Boolean equation. A combinational circuit has no memory or feedback paths. Its output state (logic 0 or logic 1) is completely defined by the state of its inputs regardless of the sequence of input state changes. Numerous algorithms have been developed to simplify Boolean equations. For example, the Quine-McKluskey method deals with the problem of minimizing the number of terms in a Boolean expression. See “Minimization of Boolean Functions”, by E. J. McCluskey, Jr.: Bell System Tech J. Vol. 35, No. 6, 1956.
In contrast, a sequential type circuit has memory elements, generally in the form of flip-flops. Since a flip-flop can store either a logic 0 or a logic 1, a sequential circuit can have up to 2
n
states where n is the number of flip-flops. Normally a sequential circuit also has combinational logic gates to support operation of its flip-flops. In addition, a sequential circuit may also have feedback paths that result in a circular flow of control. Any circuit with flip-flops must be designed to satisfy flip-flop timing requirements such as pulse width, setup time and hold time, and may require signal synchronization, flip-flop initialization and self-clearing functions. Because of all these additional considerations, a sequential circuit has many more possible implementations than a purely combinational circuit of a similar size, and is generally much more difficult to design and analyze.
In reference to synchronous control logic, which is a mix of combinational and clocked sequential circuits with feedback, M. Morris Mano writes: “The process of logic design is a complex undertaking. This task requires a considerable amount of experience and ingenuity on the part of the designer. See “Digital Logic and Computer Design”, by M. Morris Mano: page 407, 1979. Compared to synchronous control logic, asynchronous (unclocked) control logic is yet more difficult to design and analyze, to the extent that asynchronous designs are often avoided altogether even though they offer higher speed operation than synchronous logic. See “An Engineering Approach to Digital Design”, by William I. Fletcher: Chapter 6, Traditional Approaches to Sequential Design and Analysis, p. 652, 1980.
Current Techniques
Although there are many published methods to accomplish sequential logic design, there are no generalized minimization algorithms for sequential logic. “So complicated is the state assignment problem that at present there is no general technique guaranteed to yield an optimal state assignment without some sort of exhaustive search.” For sequential logic design, exhaustive search approaches are generally considered impractical due to the length of time required to compute all possible circuit configurations. “If it were possible to try a new state assignment once every 100 microseconds, it would take approximately 66 years to try all the possible state assignments for a simple 16 state machine.” See “An Engineering Approach to Digital Design”, by William I. Fletcher: Chapter 6, Traditional Approaches to Sequential Design and Analysis, p. 367, 1980.
In practice, sequential logic design is usually done “by the seat of the pants” based on past experience. Once the designer has a good understanding of the requirements, he iterates design and analysis steps until he has a circuit that “works”. The circuit is documented in the form of Boolean equations, schematic diagrams, flow charts or software-like code such as the Verilog or VHDL Hardware Description Language (HDL). For control logic, a popular design technique is to construct control flow diagrams called state diagrams to define all circuit state transitions and input/output signal dependencies. The completed state diagram is then mapped to gates and flip-flops resulting in what is referred to as a finite state machine (FSM). The state diagram approach is often helpful in mapping the requirements to a control flow model since it provides an additional level of abstraction from the schematic diagram or HDL code. However, without adequate designer discipline, state diagrams themselves can become very complex and unwieldy, and often result in extremely inefficient gate/flip-flop circuits.
Note that while there are numerous computer tools available for text editing, state diagram entry and schematic diagram capture, designing digital circuits is a manual process that requires experience, skill and a working knowledge of the integrated circuits being used.
Shortcomings
There arc a number of serious shortcomings with the above-discussed digital design process. First, the designer must have experience and skill commensurate with the complexity of the circuit being designed. Next the designer must be willing to perform as many design iterations as required to achieve satisfactory results. For control logic with numerous feedback paths, even a small circuit design may take hours to complete.
Because of the lack of minimization algorithms, and the additional time and skill needed to manually simplify a circuit, there is generally little effort spent trying to minimize a control logic design. This often results in extremely complex code or schematics that are difficult (if not impossible) to fully analyze, even for the original designer. In addition, a design that is not minimal tends to have poorer performance due to longer propagation delays or additional clock periods and uses more gates and flip-flops. Unnecessary design complexity also tends to mask both functional errors and timing hazards which, unless detected by simulation or hardware prototype testing, will result in poor product producibility and reliability. Even the most careful and skilled designer can forget or overlook one or more important requirements and may not catch a dangerous race-condition glitch or a signal-synchronizing problem.
Design complexity also increases the cost of product maintenance efforts such as repair or future design changes. Design complexity can be somewhat offset by thorough design documentation of control logic implementation and requirements. In practice, however, detailed documentation of the original driving requirements and the theory of operation for the corresponding control logic are seldom written.
Need
Accordingly, there is a serious need for an automated computer tool that can support the digital design process, especially in the task of control logic design. The tool should automatically design a minimal circuit from the specified requirements. As part of its automatic circuit design process, the tool should test for functional correctness (including synchronization, flip-flop initialization and self-clearing), eliminate all timing hazards, and support rules to ensure conformance with digital design best practices. Based on the specified requirements, the tool should be able to design any logic type or mix of types: combinational, sequential, synchronous or asynchronous.
SUMMARY OF THE INVENTION
The present invention implements automatic design for all types of digital circuits (combinational, synchronous sequential, or asynchronous sequential) using basic logic-gate and flip-flop functions. A user specifies circuit requirements by defining the states of the input and output signals as either a truth table or as waveforms. A user may also specify additional circuit features such as part types and quantities, flip-flop synchronization and initialization, and glitch filtering. Guided by these user inputs and a built-in digital-design knowledge base, the invention performs a constrained exhaustive search for one or more circuit solutions that meet all the requirements (user's specifications).
Generally, exhaustive-search approaches are impractical due to the length of time required to complete a search. However, the present invention combines two synergistic features, a Start-Small-and-Increment approach and Circuit-Constraint fi
Garbowski Leigh Marie
Hamilton Brook Smith & Reynolds P.C.
Smith Matthew
LandOfFree
Automated 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 Automated design system for digital circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automated design system for digital circuits will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2460395