Circuit activity driven state assignment of FSMS implemented in CMOS for low power reliable operations
First Claim
1. A method for optimizing a finite state machine (FSM) by minimizing a unit number of transitions per unit time (transition density) comprising the steps of:
- a. assigning a first state assignment for each of said states, said first state assignment consisting of a Boolean number of given length;
b. determining a first transition density characteristic associated with the first state assignment;
c. assigning a second state assignment, different from said first state assignment for each state of said FSM, said second state assignment consisting of Boolean number of said given length;
d. determining a second transition density characteristic associated with the second state assignment;
e. assigning the first state assignment equal to the second state assignment if second transition density characteristic is less than a predetermined amount greater than said first transition density characteristic;
f. repeating steps c through e until there is no second state assignment having a second transition density characteristic less than said first transition density characteristic.
3 Assignments
0 Petitions
Accused Products
Abstract
A method for optimizing a circuit containing a finite state machine (FSM) based on transition density. A first state assignment is assigned for each state. Then, a first transition density characteristic associated with the first state assignment is determined and a second state assignment, different from said first state assignment is assigned for each state. A second transition density characteristic associated with the second state assignment is then determined and the first state assignment is set equal to the second state assignment if second transition density characteristic is less than a predetermined amount. The process is repeated until the transition density has been minimized.
-
Citations
14 Claims
-
1. A method for optimizing a finite state machine (FSM) by minimizing a unit number of transitions per unit time (transition density) comprising the steps of:
-
a. assigning a first state assignment for each of said states, said first state assignment consisting of a Boolean number of given length; b. determining a first transition density characteristic associated with the first state assignment; c. assigning a second state assignment, different from said first state assignment for each state of said FSM, said second state assignment consisting of Boolean number of said given length; d. determining a second transition density characteristic associated with the second state assignment; e. assigning the first state assignment equal to the second state assignment if second transition density characteristic is less than a predetermined amount greater than said first transition density characteristic; f. repeating steps c through e until there is no second state assignment having a second transition density characteristic less than said first transition density characteristic. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for optimizing state assignments for a finite state machine (FSM) having a plurality of states, comprising the steps of:
-
a. determining a state transition probability for each of a plurality of state transitions; b. creating a first state assignment for each of said states, said first state assignment consisting of a number of binary bits; c. determining the hamming distance for each state transition; d. determining y1 for the first state assignments, using said state transition probabilities; e. changing the state assignment for at least one but no more than two states such that no two states have the same state assignment to create a second state assignment for each of said states; f. determining the hamming distance for each state transition using the second state assignments; g. determining y2 for the second state assignment; h. assigning the first state assignment equal to the second state assignment if y2 is less than a predetermined amount greater than y1; i. repeating steps c through h until there is no second state assignment having a y2 less than y1. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A method for optimizing a CMOS circuit having a finite state machine (FSM) and multilevel combinational logic, comprising the steps of:
-
a. assigning an initial state assignment to each state of said FSM, said initial state assignment consisting of a Boolean number of a given length; b. modifying said initial state assignments to cream an optimized state assignment for each state that minimizes a unit number of transitions per unit time (transition density), by performing the following steps; i. creating an intermediate state assignment equal to the initial state assignment; ii. determining the state transition probability for each transition possibility of each state; iii. determining a Hamming distance for each transition possibility associated with the intermediate state assignments; and iv. determining y1 associated with the intermediate state assignments using said state transition probability; v. determining a temporary state assignment; vi. determining the Hamming distance for each output possibility using the temporary state assignments; vii. determining y2 for the temporary state assignment; viii. assigning the intermediate assignment equal to the temporary assignment if y2 is less than a predetermined amount greater than y1; ix. repeating steps c through h until there is no temporary assignment having a y2 less than y1; and x. assigning the optimized state assignment equal to the intermediate state assignment; and c. optimizing the multilevel combination logic for area and power.
-
Specification