US5452215A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for designing a finite state machine to reduce power dissipation
Assignee: International Business Machines Corp
•
Filing: 1994-08-24
•
Granted: 1995-09-19
•
Expires: 2014-08-24
Abstract
Abstract Accordingly, a digital logic circuit in the form of a finite state machine (FSM) is implemented in a semiconductor structure such as complementary metal oxide silicon (CMOS) with reduced power dissipation by determining transition probabilities for transitions between states in the FSM, producing a constraint matrix to identify constraints to producing a minimum area implementation consistent with minimum power dissipation, constructing one or more state chains having transitions with highest probability and implementing each of these state chains in order of probability to achieve the implementation of the FSM having minimum power dissipation.
Inventors
- 👤 Scott T. Washabaugh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 02:32
CPC Classifications
G; G06; G06F; G06F7/00; G06F30/00; G06F30/30
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
88 words
A system for designing a finite state machine to achieve minimum power dissipation, comprising: means for determining one or more state table transition probabilities for transitions between states of said finite state machine; means for producing a constraint matrix to identify constraints to producing a minimum area design; means for constructing one or more state chains having state table transitions with highest probability; and means for implementing design of each of said state chains in the order of probability to produce a minimum power dissipation finite state machine.
Claim 2
Independent Claim
88 words
A system for designing a finite state machine to achieve minimum power dissipation, comprising: means for determining one or more state table transition probabilities for transitions between states of said finite state machine; means for producing a constraint matrix to identify constraints to producing a minimum area design; means for constructing one or more state chains having state table transitions with highest probability; and means for implementing design of each of said state chains in the order of probability to produce a minimum power dissipation finite state machine.
Claim 3
Dependent Claim
41 words
A system for designing a finite state machine to achieve minimum power dissipation, according to claim 1, further comprising: means for assigning a predetermined probability value to one or more transitions having a probability value less than a first threshold value.
Claim 4
Dependent Claim
35 words
A system for designing a finite state machine to achieve minimum power dissipation, according to claim 2, wherein said predetermined probability value is zero to enable a more efficient design of said finite state machine.
Claim 5
Dependent Claim
35 words
A system for designing a finite state machine to achieve minimum power dissipation, according to claim 1, wherein said means for producing a constraint matrix further comprises: means for symbolic minimization of a logic design.
Claim 6
Dependent Claim
52 words
A system for designing a finite state machine to achieve minimum power dissipation, according to claim 1, wherein said means for constructing one or more state chains further comprises: means for connecting states having a transition probability greater than a second threshold value to an end of one of said state chains.
Claim 7
Independent Claim
122 words
A method implemented in a computer system for designing a finite state machine to achieve minimum power dissipation, comprising the steps of: determining one or more state table transition probabilities for transitions between states of said finite state machine by simulating a high level language version of said finite state machine in a processor of said computer system; producing a constraint matrix to identify constraints to producing a minimum power dissipation design; constructing one or more state chains having state table transitions with highest probability; implementing design of each of said constructed state chains in the order of probability, wherein said step of implementing includes coding said state chains; and performing logic synthesis of said finite state machine based on said design.
Claim 8
Independent Claim
122 words
A method implemented in a computer system for designing a finite state machine to achieve minimum power dissipation, comprising the steps of: determining one or more state table transition probabilities for transitions between states of said finite state machine by simulating a high level language version of said finite state machine in a processor of said computer system; producing a constraint matrix to identify constraints to producing a minimum power dissipation design; constructing one or more state chains having state table transitions with highest probability; implementing design of each of said constructed state chains in the order of probability, wherein said step of implementing includes coding said state chains; and performing logic synthesis of said finite state machine based on said design.
Claim 9
Dependent Claim
42 words
A method for designing a finite state machine to achieve minimum power dissipation, according to claim 6, further comprising the steps of: assigning a predetermined probability value to one or more transitions having a probability value less than a first threshold value.
Claim 10
Dependent Claim
35 words
A method for designing a finite state machine to achieve minimum power dissipation, according to claim 7, wherein said predetermined probability value is zero to enable a more efficient design of said finite state machine.
Claim 11
Dependent Claim
39 words
A method for designing a finite state machine to achieve minimum power dissipation, according to claim 6, wherein said step of producing a constraint matrix further comprises: minimizing a logic design to reduce area of said finite state machine.
Claim 12
Dependent Claim
50 words
A method for designing a finite state machine to achieve minimum power dissipation, according to claim 6, wherein said step of constructing one or more state chains further comprises: connecting states having a transition probability greater than a second threshold value to an end of one of said state chains.
Claim 13
Dependent Claim
17 words
A finite state machine with reduced power dissipation, manufactured in accordance with the method of claim 6.
Claim 14
Independent Claim
77 words
A system for minimizing power dissipation in a digital logic system, comprising: means for determining one or more state table transition probabilities for transitions between states of said digital logic system; means for producing a constraint matrix to identify constraints to minimizing area of said finite state machine; means for simulating one or more logic circuits having state table transitions with highest probability; and means for implementing each of said logic circuits in the order of probability.
Claim 15
Independent Claim
77 words
A system for minimizing power dissipation in a digital logic system, comprising: means for determining one or more state table transition probabilities for transitions between states of said digital logic system; means for producing a constraint matrix to identify constraints to minimizing area of said finite state machine; means for simulating one or more logic circuits having state table transitions with highest probability; and means for implementing each of said logic circuits in the order of probability.
Claim 16
Dependent Claim
39 words
A system for minimizing power dissipation in a digital logic system, according to claim 12, further comprising: means for assigning a predetermined probability value to one or more transitions having a probability value less than a first threshold value.
Claim 17
Dependent Claim
33 words
A system for minimizing power dissipation in a digital logic system, according to claim 13, wherein said predetermined probability value is zero to enable a more efficient design of said digital logic system.
Claim 18
Dependent Claim
33 words
A system for minimizing power dissipation in a digital logic system, according to claim 12, wherein said means for producing a constraint matrix further comprises: means for symbolic minimization of a logic design.
Claim 19
Dependent Claim
48 words
A system for minimizing power dissipation in a digital logic system, according to claim 12, wherein said means for producing a constraint matrix further comprises: means for connecting states having a transition probability greater than a second threshold value to an end of one of said state chains.
Claim 20
Independent Claim
90 words
A method implemented in a computer system for minimizing power dissipation in a digital logic system, comprising the steps of: determining one or more state table transition probabilities for transitions between states of said digital logic system; producing a constraint matrix to identify constraints to producing a minimum power dissipation design; constructing one or more logic circuits having state table transitions with highest probability as determined in said determining step; and implementing design of each of said logic circuits in the order of probability, as determined in said determining step.
Claim 21
Independent Claim
90 words
A method implemented in a computer system for minimizing power dissipation in a digital logic system, comprising the steps of: determining one or more state table transition probabilities for transitions between states of said digital logic system; producing a constraint matrix to identify constraints to producing a minimum power dissipation design; constructing one or more logic circuits having state table transitions with highest probability as determined in said determining step; and implementing design of each of said logic circuits in the order of probability, as determined in said determining step.
Claim 22
Dependent Claim
40 words
A method for minimizing power dissipation in a digital logic system, according to claim 17, further comprising the steps of: assigning a predetermined probability value to one or more transitions having a probability value less than a first threshold value.
Claim 23
Dependent Claim
33 words
A method for minimizing power dissipation in a digital logic system, according to claim 18, wherein said predetermined probability value is zero to enable a more efficient design of said digital logic system.
Claim 24
Dependent Claim
29 words
A method for minimizing power dissipation in a digital logic system, according to claim 17, wherein said step of producing a constraint matrix further comprises: minimizing a logic design.
Claim 25
Dependent Claim
48 words
A method for minimizing power dissipation in a digital logic system, according to claim 17, wherein said step of constructing one or more logic circuits further comprises: connecting circuits having a transition probability greater than a second threshold value to an end of one of said logic circuits.
References Cited (Backward Citations)
US4580228A
Cited
US5119314A
Cited
US5267175A
Cited
US5140402A
Cited
US5212653A
Cited
US5225991A
Cited
US5283753A
Cited
US5311079A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-09-18 | 1999-03-20 | 1999-09-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-18 | 2003-03-20 | 2003-09-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-18 | 2007-03-20 | 2007-09-19 | $7700.00 | Window Closed / Lapsed |