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:

1. Implication charts and merger diagrams
2. 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.