State Minimization - Sequential Circuits

• A synchronous sequential circuit has n states that require at least $lo{g}_{2}n$ flip-flops. 3-state circuit requires at least 2 flip-flops
• Reducing # of states we can reduce the number of flip flops
• If 2 states are equivalent we can combine them into a single state
• 2 states are considered to be equivalent if the following conditions are true
  • Each input the states give exactly same output
  • Each input the states give the same next state or an equivalent next state

State Minimization Through Partitioning §

1. Partition states according to circuit outputs produced
2. For each partition, do the following:
   • For any input pattern if different states in a partition result in a transition to a different partition, then those states are not equivalent and we separate them into smaller partitions
3. Continue Partitioning until all the states in any partition transition to the same other partition for any input pattern
4. Once no further partitioning is required, identification of the equivalent states is complete