# US 2018/0025101 A1 · Systems and method for optimizing state encoding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0025101 A1
- Document ID: US20180025101A1
- Status: Published application
- Kind: A1
- Application number: 15/216,302
- Filed: 2016-07-21
- Published: 2018-01-25
- Earliest claimed: 2016-07-21
- Assignees: King Fahd University of Petroleum and Minerals
- Applicants: King Fahd University of Petroleum and Minerals
- Inventors: Aiman Helmi EL-MALEH
- Web page: https://patentgrep.com/patent/US20180025101A1

## CPC

- G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
- G06F 30/30: Circuit design
- G06F 30/337: Design optimisation
- G06F 2119/06: Power analysis or power optimisation
- G06F 2119/12: Timing analysis or timing optimisation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and system for optimizing state assignments for a finite state machine. The method generates a random initial state assignment for each of a plurality of states of the finite state machine, determines an initial cost associated with the random initial state assignments, identifies a code swap to explore as a function of a code swap probability. Further, the method calculates a cost for the code swap when one or more criteria is satisfied, updates the code swap probability as a function of the cost of the code swap and a best cost, performs the code swap when the cost of the swap is smaller than the best cost and/or a current cost to optimize the state assignments, and outputs optimized state assignments.

## Claims

### Claim 1

A method for optimizing state assignments for a finite state machine, the method comprising:
generating a random initial state assignment for each of a plurality of states of the finite state machine;
determining, using processing circuitry, an initial cost associated with the random initial state assignments;
identifying, using the processing circuitry, a code swap to explore as a function of a code swap probability;
calculating a cost for the code swap when one or more criteria is satisfied;
updating, using the processing circuitry, the code swap probability as a function of the cost of the code swap and a best cost;
performing the code swap, when the cost of the swap is smaller than the best cost and/or a current cost, to optimize the state assignments; and
outputting optimized state assignments.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
synthesizing a circuit based on the optimized state assignments.

### Claim 3 (depends on 1)

The method of claim 1, wherein the one or more criteria includes one or more of:
an indication of whether the code swap has not been explored in a current round,
a solution associated with the code swap was not previously generated,
a round is not repeated wherein the round is an iteration where all pairs of code swaps are considered, and
a maximum predetermined number of code swaps by round is not exceeded.

### Claim 4 (depends on 3)

The method of claim 3, wherein the maximum predetermined number of code swaps by round is a function of a number of hill climb taken in a period, the period starting when a current solution does not improve after finishing a round and ending when a best solution is found.

### Claim 5 (depends on 1)

The method of claim 1, wherein the code swap having a higher code swap probability is explored before other code swaps having a lower code swap probability.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
exploring code swaps in a first probability range; and
exploring code swaps in a second probability range different from the first probability range when code swaps having a probability in the first probability range are all explored and a maximum predetermined number of code swaps by round has not been reached.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
updating a first list when the code swap is performed, the first list storing a predetermined number of performed code swaps.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
repeating the steps of exploring, calculating, updating, and performing until the number of explored swaps is equal to a predetermined maximum number of swaps allowed.

### Claim 9 (depends on 8)

The method of claim 8, further comprising:
performing a hill climb when the current cost is not improved after a round; and
updating a second list, the second list storing indices of code swaps performed due to hill climbing.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
exploring all code swaps in a first round.

### Claim 11

A computer system for optimizing state assignments for a finite state machine, the system comprising:
processing circuitry configured to
generate a random initial state assignment for each of a plurality of states of the finite state machine,
determine an initial cost associated with the random initial state assignments,
identify a code swap to explore as a function of a code swap probability,
calculate a cost for the code swap when one or more criteria is satisfied,
update the code swap probability as a function of the cost of the code swap and a best cost,
perform the code swap when the cost of the swap is smaller than the best cost and/or a current cost, to optimize the state assignments, and
output optimized state assignments.

### Claim 12 (depends on 11)

The computer system of claim 11, wherein the processing circuitry is further configured to:
synthesize a circuit based on the optimized state assignments.

### Claim 13 (depends on 11)

The computer system of claim 11, wherein the one or more criteria includes one or more of:
an indication of whether the code swap has not been explored in a current round,
a solution associated with the code swap was not previously generated,
a round is not repeated wherein the round is an iteration where all pairs of code swaps are considered, and
a maximum predetermined number of code swaps by round is not exceeded.

### Claim 14 (depends on 13)

The computer system of claim 13, wherein the maximum predetermined number of code swaps by round is a function of a number of hill climb taken in a period, the period starting when a current solution does not improve after finishing a round and ending when a best solution is found.

### Claim 15 (depends on 11)

The computer system of claim 11, wherein the code swap having a higher code swap probability is explored before other code swaps having a lower code swap probability.

### Claim 16 (depends on 11)

The computer system of claim 11, wherein the processing circuitry is further configured to:
explore code swaps in a first probability range; and
explore code swaps in a second probability range different from the first probability range when code swaps having a probability in the first probability range are all explored and a maximum predetermined number of code swaps by round has not been reached.

### Claim 17 (depends on 11)

The computer system of claim 11, wherein the processing circuitry is further configured to:
update a first list when the code swap is performed, the first list storing a predetermined number of performed code swaps.

### Claim 18 (depends on 11)

The computer system of claim 11, wherein the processing circuitry is further configured to:
repeat the steps of exploring, calculating, updating, and performing until the number of explored swaps is equal to a predetermined maximum number of swaps allowed.

### Claim 19 (depends on 18)

The computer system of claim 18, wherein the processing circuitry is further configured to:
perform a hill climb when the current cost is not improved after a round; and
update a second list, the second list storing indices of code swaps performed due to hill climbing.

### Claim 20

A non-transitory computer readable medium storing computer-readable instructions therein which when executed by a computer cause the computer to perform a method for optimizing state assignments for a finite state machine, the method comprising:
generating a random initial state assignment for each of a plurality of states of the finite state machine;
determining a cost associated with the random initial state assignments;
identifying a code swap to explore as a function of a code swap probability;
calculating a cost for the code swap when one or more criteria is satisfied;
updating the code swap probability as a function of the cost of the cost swap and a best cost;
performing the code swap when the cost of the swap is smaller than the best cost and/or a current cost, to optimize the state assignments; and
outputting optimized state assignments.