Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-01-05
2001-01-30
Teska, Kevin J. (Department: 2768)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06182268
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of circuit design synthesis, and more particularly to the design of integrated circuits which include state machine circuits.
BACKGROUND OF THE INVENTION
For the design of digital circuits on the scale of VLSI (Very Large Scale Integration) technology, designers often employ computer-aided techniques. Standard languages known as Hardware Description Languages (HDL's) have been developed to describe digital circuits to aid in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general purpose hardware description languages which allow definition of a hardware model at the gate level, the register transfer level (RTL), or the behavioral level using abstract data types. As device technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles.
One important aspect in the field of circuit synthesis and simulation is in the modeling and analysis of finite state machines. A state machine is a generalized type of sequential logic in which the next state of the machine (or circuit) can be written as a function of the current state and the value of the input signals to the machine. Because state machines can be used to represent digital circuits which combine combinational logic and a memory element, state machines are a fundamental building block in the synthesis of large scale digital circuits. The modeling of state machines is especially important given the prevalent use of programmable logic devices to implement sequential logic functions within a circuit. It is desirable to identify a state machine within a logic design because well known optimizations can be performed on the state machine. Further, a state machine may be debugged by using conventional debugging methods. However, designers who use HDL to create circuit designs often do not intentionally include a state machine in a circuit design. That is, a designer may merely write HDL code specifying the circuit design without intending to include a state machine and without realizing that, in fact, a state machine has been unintentionally included in the circuit design. Thus, the optimization and debugging of state machines is not possible when a state machine is included in this manner because the state machine's existence in the design is unrecognized and its definition in a symbolic form (e.g. definition by a next state function or by a state diagram or state table) is not provided by the designer or as a result of a compiler's logic synthesis.
Present methods and products associated with HDL synthesis accommodate the analysis of finite state machines (FSM). These methods, however, require the users to either constrain the style in which the finite state machine is described by following a rigid coding template, or to isolate the finite state machine from other parts of the design and identify the HDL variable representing the current state of the finite state machine. In the first case the restriction allows the finite state machine to be recognized with pattern matching on the original HDL source code. In the second, the state machine is extracted from a netlist with Boolean logic techniques, relying on the user's identification of both the state register and the portion of the design that is to be considered part of the state machine.
The identification of the part of the design and design information that is involved in the state machine is important. Not including enough of the design will lead to an extracted state machine that contains many states that are not reachable (invalid) in the whole design as well as state to state transitions that cannot be activated within the context of the whole design. These invalid states and transitions will both create a larger optimization problem as well as biasing the finite state machine optimization towards getting a good result for states and transitions which are not needed. Including too much of the design yields an analysis problem that can be computationally difficult or impractical, as well as disturbing the optimization of parts of the design that did not need to be included.
One deficiency in these techniques is that only circuits that the user thinks of as state machines and that the user makes the effort to identify are treated as state machines.
A second deficiency is that theses techniques place strong constraints on the way the user can describe state machines, either by requiring a rigid coding template to be followed or by requiring he design to be organized to isolate the state machine (for example, using design hierarchy) from other parts of the design.
It is therefore desirable to provide a system which automatically identifies finite state machines in a circuit.
It is further desirable to provide a system that determines what part of the design should be included in the state machine extraction process.
It is further desirable to provide a system for automatically extracting identified state machines and representing the state machines in symbolic or functional form to facilitate further analysis and optimization.
SUMMARY OF THE INVENTION
The present invention discloses methods and apparatuses which automatically extract finite state machine circuits from a complex digital circuit.
In one example of a method of the invention, a circuit region is defined to include a register and a group of logic gates within a feedback path from the output of the register to the input of the register. This circuit region defines a state machine based on the identified register. For each defined state machine, the next state function is defined. The next state function is derived by determining the next state from each current state of the state machine and the possible input values to the state machine.
In an exemplary embodiment of the present invention, a symbolic representation of an automatically defined state machine is created using next state values determined for all possible current state values and input value combinations. The symbolic representation of the state machine is used to recompile the circuit comprising the state machine into a target library. Further circuit analysis and optimization programs may be performed to improve the area or performance characteristics of the state machine. In one particular embodiment, a method according to the invention may additionally include a filtering of the registers in a synthesized design which has produced an RTL netlist. This filtering attempts to identify only registers which are possible state registers and hence may be part of a state machine. This filtering is performed before identifying circuit regions which include a state register and a group of logic gates within a feedback path from the output of a state register and the input to the state register. Those registers which are not possible state registers are ignored in further processing which defines a circuit region which includes possible state registers.
Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.
REFERENCES:
patent: 5394347 (1995-02-01), Kita et al.
patent: 5517432 (1996-05-01), Chandra et al.
patent: 5537580 (1996-07-01), Giomi et al.
patent: 5594657 (1997-01-01), Cantone et al.
patent: 5706473 (1998-01-01), Yu et al.
patent: 5774370 (1998-06-01), Giomi
patent: 5825644 (1998-10-01), Yeap
patent: 5870590 (1999-02-01), Kita et al.
Logic Synthesis and Verification Algorithms; Hachtel, Gary D., and Somenzi, Fabio; Sections 7.9 and 7.10; pp. 305-312; Klauwer Academic Publishing, 1996.
Camposano, R.; Rosenstiel, W., Syntehsizing Circuits from Behaviorual Descriptions, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, pp. 171-180, Feb. 1989.
Blakely & Sokoloff, Taylor & Zafman
Synplicity, Inc.
Teska Kevin J.
Thompson A. M.
LandOfFree
Methods and apparatuses for automatic extraction of finite... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatuses for automatic extraction of finite..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatuses for automatic extraction of finite... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2554656