US6182268B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatuses for automatic extraction of finite state machines
Assignee: Synopsys Inc
•
Filing: 1998-01-05
•
Granted: 2001-01-30
•
Expires: 2018-01-05
Abstract
Abstract A method and apparatus which automatically extract finite state machine circuits from a circuit design. Typically, the circuit design is specified by a hardware description language which is compiled to a level of description which shows logic and interconnections in the circuit. A circuit region which includes a register is automatically defined from this description. The circuit region is defined as the register and the group of logic gates within a feedback path from the output of the register to the input of the register. The circuit region is analyzed to define a finite state machine. For each finite state machine, the next state function of the state machine is determined. The next state function is derived by determining a next state from a current state of the state machine and a set of possible input values to the state machine. A symbolic representation of the state machine may be generated from the next state function, and state machine may be optimized and/or debugged in its symbolic representation. The state machine may then be recompiled from the symbolic representation. In one example, the state machine may be recompiled into a target architecture.
Inventors
- 👤 Kenneth S. McElvain
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 07:23
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
125 words
A method of identifying a finite state machine within a circuit, the method comprising: compiling a description of a circuit, which is described in a hardware description language (HDL), to create a circuit representation; automatically defining an extraction circuit region from said circuit representation in order to identify said finite state machine, said extraction circuit region comprising a register of a first register type having associated therewith a feedback path, and one or more logic devices included within the feedback path associated with said register; and determining a next state function for said finite state machine which is included within said extraction circuit region, said next state function being derived by determining a next state from a current state and a set of input signals.
Claim 2
Independent Claim
125 words
A method of identifying a finite state machine within a circuit, the method comprising: compiling a description of a circuit, which is described in a hardware description language (HDL), to create a circuit representation; automatically defining an extraction circuit region from said circuit representation in order to identify said finite state machine, said extraction circuit region comprising a register of a first register type having associated therewith a feedback path, and one or more logic devices included within the feedback path associated with said register; and determining a next state function for said finite state machine which is included within said extraction circuit region, said next state function being derived by determining a next state from a current state and a set of input signals.
Claim 3
Dependent Claim
22 words
A method as in claim 1 further comprising creating a symbolic representation of said next state function for said finite state machine.
Claim 4
Dependent Claim
12 words
A method as in claim 2 further comprising analyzing said symbolic representation.
Claim 5
Dependent Claim
18 words
A method as in claim 3 wherein said symbolic representation is analyzed to optimize said finite state machine.
Claim 6
Dependent Claim
18 words
A method as in claim 3 wherein said symbolic representation is analyzed to debug said finite state machine.
Claim 7
Dependent Claim
16 words
A method as in claim 3 further comprising recompiling said state machine from said symbolic representation.
Claim 8
Dependent Claim
16 words
A method as in claim 6 wherein said state machine is recompiled into a target architecture.
Claim 9
Dependent Claim
49 words
A method as in claim 6 further comprising identifying one or more registers of said first register type prior to said automatically defining step and wherein said automatically defining is performed for only those regions in said circuit which are coupled to a register of said first register type.
Claim 10
Dependent Claim
22 words
A method as in claim 1 wherein said extraction circuit region is augmented to minimize invalid input combinations of said state machine.
Claim 11
Dependent Claim
142 words
A computer readable medium having stored thereon sequences of instructions which are executable by a digital processing system, and which, when executed by the digital processing system, cause the system to perform a method comprising: compiling a description of a circuit, which is described in a hardware description language (HDL), to create a circuit representation; automatically defining an extraction circuit region from said circuit representation in order to identify a finite state machine, said extraction circuit region comprising a register of a first register type having associated therewith a feedback path, and one or more logic devices included within the feedback path associated with said register; and determining a next state function for said finite state machine which includes said register, said next state function being derived by determining a next state from a current state and a set of input signals.
Claim 12
Dependent Claim
142 words
A computer readable medium having stored thereon sequences of instructions which are executable by a digital processing system, and which, when executed by the digital processing system, cause the system to perform a method comprising: compiling a description of a circuit, which is described in a hardware description language (HDL), to create a circuit representation; automatically defining an extraction circuit region from said circuit representation in order to identify a finite state machine, said extraction circuit region comprising a register of a first register type having associated therewith a feedback path, and one or more logic devices included within the feedback path associated with said register; and determining a next state function for said finite state machine which includes said register, said next state function being derived by determining a next state from a current state and a set of input signals.
Claim 13
Dependent Claim
27 words
A computer readable medium as in claim 10 wherein said method further comprises: creating a symbolic representation of said next state function for said finite state machine.
Claim 14
Dependent Claim
20 words
A computer readable medium as in claim 11 wherein said symbolic representation is analyzed to optimize said finite state machine.
Claim 15
Dependent Claim
20 words
A computer readable medium as in claim 11 wherein said symbolic representation is analyzed to debug said finite state machine.
Claim 16
Dependent Claim
21 words
A computer readable medium as in claim 11 , said method further comprising recompiling said state machine from said symbolic representation.
Claim 17
Dependent Claim
18 words
A computer readable medium as in claim 14 wherein said state machine is recompiled into a target architecture.
Claim 18
Dependent Claim
61 words
A computer readable medium as in claim 14 , said method further comprising identifying one or more registers of said first register type prior to said automatically defining said first circuit region and wherein said automatically defining said first circuit region is performed for only those regions in said circuit which are coupled to a register of said first register type.
Claim 19
Dependent Claim
27 words
A computer readable medium as in claim 10 wherein said method further comprises augmenting said extraction circuit region to minimize invalid input combinations of said state machine.
Claim 20
Dependent Claim
146 words
A computer system comprising: a bus; a data storage device coupled to said bus; and a processor coupled to said data storage device, said processor operable to receive instructions which, when executed by the processor, cause the processor to perform a method comprising: compiling a description of a circuit, which is described in a hardware description language (HDL), to create a circuit representation; automatically defining an extraction circuit region including a register from said circuit representation in order to identify a finite state machine, said register having associated therewith a feedback path, said extraction circuit region comprising said register, and one or more logic devices included within said feedback path; and determining a next state function for said finite state machine which includes said register, said next state function being derived by determining a next state from a current state and a set of input signals.
Claim 21
Dependent Claim
146 words
A computer system comprising: a bus; a data storage device coupled to said bus; and a processor coupled to said data storage device, said processor operable to receive instructions which, when executed by the processor, cause the processor to perform a method comprising: compiling a description of a circuit, which is described in a hardware description language (HDL), to create a circuit representation; automatically defining an extraction circuit region including a register from said circuit representation in order to identify a finite state machine, said register having associated therewith a feedback path, said extraction circuit region comprising said register, and one or more logic devices included within said feedback path; and determining a next state function for said finite state machine which includes said register, said next state function being derived by determining a next state from a current state and a set of input signals.
Claim 22
Dependent Claim
26 words
A computer system as in claim 18 wherein said method further comprises creating a symbolic representation of said next state function for said finite state machine.
Claim 23
Dependent Claim
16 words
A computer system as in claim 19 wherein said method further comprises analyzing said symbolic representation.
Claim 24
Dependent Claim
19 words
A computer system as in claim 20 wherein said symbolic representation is analyzed to optimize said finite state machine.
Claim 25
Dependent Claim
19 words
A computer system as in claim 20 wherein said symbolic representation is analyzed to debug said finite state machine.
Claim 26
Dependent Claim
17 words
A computer system as in claim 19 wherein said state machine is recompiled from said symbolic representation.
Claim 27
Dependent Claim
17 words
A computer system as in claim 19 wherein said state machine is recompiled into a target architecture.
Claim 28
Dependent Claim
111 words
A computer implemented method of determining a reset state of a finite state machine, the method comprising: determining whether an asynchronous reset state of said finite state machine (FSM) exists or whether a synchronous reset state for said FSM exists wherein said FSM has more than two states and more than one output and wherein, if said FSM does not have said asynchronous reset state, said method comprises: determining a next state function for said FSM; determining a common state based on said next state function for said FSM, wherein said common state is a state of said FSM which said FSM reaches regardless of a current state of said FSM.
Claim 29
Dependent Claim
111 words
A computer implemented method of determining a reset state of a finite state machine, the method comprising: determining whether an asynchronous reset state of said finite state machine (FSM) exists or whether a synchronous reset state for said FSM exists wherein said FSM has more than two states and more than one output and wherein, if said FSM does not have said asynchronous reset state, said method comprises: determining a next state function for said FSM; determining a common state based on said next state function for said FSM, wherein said common state is a state of said FSM which said FSM reaches regardless of a current state of said FSM.
Claim 30
Dependent Claim
135 words
A computer implemented method as in claim 25 , said method further comprising: compiling a description of a circuit, which is described in a hardware description language (HDL), to create a circuit representation; automatically defining an extraction circuit region from said circuit representation in order to identify said finite state machine, said extraction circuit region comprising a register of a first register type having associated therewith a feedback path, and one or more logic devices included within the feedback path associated with said register; and wherein said FSM includes said register, said next state function being derived by determining a next state from a current state and a set of input signals, and wherein said synchronous reset state and said next state function are used to create a symbolic representation of said next state function.
References Cited (Backward Citations)
US5394347A
Cited
US5870590A
Cited
US5594657A
Cited
US5517432A
Cited
US5537580A
Cited
US5706473A
Cited
US5774370A
Cited
US5825644A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-30 | 2004-07-31 | 2005-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-30 | 2008-07-31 | 2009-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-30 | 2012-07-31 | 2013-01-30 | $7700.00 | Window Closed / Lapsed |