State Minimization
We sometimes get more states than we actually need. Two states are equivalent if:
- they have the same next states (given the same input)
- they have the same output (given the same input)
We use two techniques:
- Implication charts and merger diagrams
- Partitioning
1. Implication Chart and Merger Diagrams
Step 1. Mark the states where the outputs are different
Step 2. Where States have the same output, put equalities in the box
Ex: (S0, S1) cannot happen because there is already an X on there, so rule out those possibilities.
Step 3 (optional). You can stop earlier, but now that we have the implication chart, we can build a merger diagram which allows us to see geometrically and see bigger rules for compatibility.
2. Partitioning
Intuition is just dividing group into smaller and smaller groups until we don’t need to anymore.
Example:
Encoding for Outputs
One-Hot Encoding
What about Asynchronous circuits?
Same thing, there are lots of don’t cares usually so it will be easier to minimize.