State Assignment Heuristic

for Sequential Machine Design

This heuristic deals with determining a good way of assigning sequential machine state names to the state variables (i.e., the flip-flop names) used to implement the machine.

There are two approaches to using this heuristic, depending upon how many states there are in the sequential machine to be built. Approach 1 works best when the number of states in the sequential machine is low (usually 4 or less). Approach 2 is used when there is a large number of states in the sequential machine. In either case the rules given in the table below and their associated guidelines (following the table) direct one's efforts in determining a possible good state assignment.

One's starting point is the next state table for the sequential machine being designed and one or more blank Karnaugh maps that have the state variables (the flip-flip names) as inputs.

Approach 1

Initially one needs to use as many blank Karnaugh maps as there are distinct ways to assign the states to the state variables. Apply Rule 0 to place the initial state in all the maps. Then place the remaining states according to each distinct assignment, one distinct way per Karnaugh map. (For both 3- and 4-next-state tables, there will be three distinct assignments; thus three different Karnaugh maps.) For each Karnaugh map count the number of times Rule 1 is satisfied. The Karnaugh map that has the highest count generally is your best assignment. If there is a tie, then draw another set of blank Karnaugh maps, one for each distinct assignment in the tie. Fill in each of these Karnaugh maps with the same distinct state assignment as the original Karnaugh map that resulted in a tie under Rule 1. For each of these maps count the number of times Rule 2 is satisfied. The map with the highest count is generally your best distinct assignment choice. If there is still a tie, repeat drawing another set of blank Karnaugh maps (as above) and apply Rule 3 to determine how many times it is satisfied for each map. The highest count is usually the best choice.

If Rule 3 is more important (see the guidelines), then one should reverse the tiebreaker process given above and first try to break the tie by checking Rule 3 before checking the count associated with the Karnaugh maps and Rule 2.

Approach 2

List the sets of adjacent states specified by Rule 1, by Rule 2, and by Rule 3 noting the number of duplicate pairs that occur. On a blank Karnaugh map, apply Rule 0 to place the initial state. Try to arrange the remaining states on the map to satisfy the adjacency requirements of as many pairs of states from your list for Rule 1 as possible giving a higher priority of placement to those pairs of states that have the highest frequency of occurrence on your adjacency list for Rule 1. If there are states that still have not been placed on your Karnaugh map because there is no adjacency requirement from Rule 1 or because there are conflicting requirements, use the list from Rule 2 to place these states, once again giving higher priority of placement to those pairs of states that have the highest frequency of occurrence on your adjacency list for Rule 2. Use the Rule 3 list to settle any remaining ties and to place any unplaced states, as before. (Reverse the order of using Rule 2 and Rule 3 if Rule 3 is more important.)

Generally you may find several equally good possible ways to place the states on the Karnaugh map in order to meet the adjacencies specified by the rules. In such cases you should draw additional Karnaugh maps showing each different way to make the state placement, and then proceed with placing the remaining states on each of the Karnaugh maps. Select from among your completed Karnaugh maps those that satisfy the most adjacency rules.

Rules for Determining a State Assignment

Rule

Details

Name

0
Assign the initial (starting, reset) state to map cell 0

1
If states p and q have the same next state r for a given input value, p and q should be adjacent.
into rule

2
If state p and q are the next states of state s for adjacent input values, then p and q should be adjacent.
from rule

3
States p and q that have the same output for a given input should be adjacent.
output rule

**Rules for Determining a State Assignment**
Rule	Details	Name
0	Assign the initial (starting, reset) state to map cell 0
1	If states p and q have the same next state r for a given input value, p and q should be adjacent.	into rule
2	If state p and q are the next states of state s for adjacent input values, then p and q should be adjacent.	from rule
3	States p and q that have the same output for a given input should be adjacent.	output rule

Guidelines

Adjacent conditions from Rule 1 come before Rule 2
Adjacent conditions required more often come first.
Rule 3 less important if only a single output; more important with more output functions.

Beginning of heuristic