State Reduction of ASCs
Our state reduction involves two procedures:
- Partitioning of equivalent states.
- Merging of compatible state
Procedure
- Use partitioning to eliminate all but one state for each set of equivalent states
- Construct a merger diagram
- Chose a subset of compatible states that can be merged into a single state
- Try to minimize the number of subsets needed to cover all states
- Each state must be included in only one of the chosen subsets
- Derive the reduced flow table by merging the rows in chosen subsets
- Repeat steps 2 and 4 to see if further reductions are possible
Partitioning
- Equivalent states are identified and grouped together
- For two states (rows in a flow table) to be potentially equivalent, any unspecified entries must be in the same next-state column
Example
Consider the following initial flow table:
After partitioning based on output, we have:
Since none of
But we see that states
So
Which gives us a new flow table:
Merging
After identifying compatible state pairs, we can draw a merger diagram showing relationship among various states, where:
- Each row of the flow table is represented as a point, labeled by the row name
- A line is drawn connecting any two points that correspond to compatible states
Then from the merger diagram we chose the best possibility (fewest states).
Example
Consider the following table:
Compatible pairs with
- (A, H) because the next states in each column either match, or are "don't cares"
- (B, F)
- (B, G) because even though for
the next states don't match, they are both stable - (F, G)
- (G, H)
Compatible pairs with
- (D, E)
We can draw the merger diagram:
Observe that:
- We can merge A and H as long as H is not merged with G
- We can merge F, G, and B into one state
- D and E can be merged
New state table:
Rules
- If one of the states columns of the merged states has a stable state, the new state becomes a stable state as well
- If there are multiple states in the same columns of the merged states, pick the one that will exist post-merge