What is State Minimization?
State minimization is a crucial step in digital design because it helps you optimize both your system analysis and your hardware circuits. By examining your state table, you can easily identify redundant states and combine them into a single, efficient option. If you are analyzing an existing system, this reduction creates a cleaner final state diagram. If you are designing a new circuit, fewer states lead to simpler logic equations, which ultimately means your final hardware uses fewer components and runs much more efficiently.
What are Redundant States?
A redundant state is a state that has the same next state and output values as another state for all possible input combinations.
How to Perform State Minimization?
Follow the following steps to arrive at an optimized state diagram:
- Convert the state diagram into a state table.
- Identify the redundant states in the state table.
- Combine the redundant states into one state.
- Update the state table.
- Repeat the process until no more redundant states can be found.
- Re-draw the state diagram with the combined states.
Example: Extract the Logic Diagram from the State and Output Equations
We begin with the following state diagram:
This sample state diagram features seven distinct states, ranging from stA to stG. Because there are seven total stages, you will need at least three D-type flip-flops to properly represent them. Keeping these states labeled clearly makes it much easier to spot redundant states by comparing their names rather than complex flip-flop binary values. To get started, we assign specific values to every state label listed below.
\begin{align*}
\mathsf{stA }& \mathsf{ =000}\\
\mathsf{stB }& \mathsf{ =001}\\
\mathsf{stC }& \mathsf{ =010}\\
\mathsf{stD }& \mathsf{ =011}\\
\mathsf{stE }& \mathsf{ =100}\\
\mathsf{stF }& \mathsf{ =101}\\
\mathsf{stG }& \mathsf{ =110}
\end{align*}
Step 1: Convert the State Diagram into a State Table
We convert the state diagram into an equivalent state table. Instead of using binary values, we use clear state labels for both the current and next states of our D-type flip-flops, \(\mathsf{A}\), \(\mathsf{B}\), and \(\mathsf{C}\), which makes the whole process much easier to follow. Input signal is labelled as \(\mathsf{x}\), while the output is called \(\mathsf{y}\).
Step 2: Identify the Redundant States in the State Table
We compare each state against every other state to check if they share identical next states and output values for the same inputs. To do this systematically, we start by matching \(\mathsf{stA}\) with \(\mathsf{stB}\) through \(\mathsf{stG}\), and then we move on to match \(\mathsf{stB}\) with \(\mathsf{stC}\) through \(\mathsf{stG}\), continuing down the line. Through this comparison, we discover that \(\mathsf{stE}\) and \(\mathsf{stG}\) produce the exact same next states—\(\mathsf{stA}\) and \(\mathsf{stF}\)—along with matching outputs of \(\mathsf{0}\) and \(\mathsf{1}\) for inputs \(\mathsf{x=0}\) and \(\mathsf{x=1}\). You can easily spot these matches because the equivalent states are highlighted below.
Step 3: Combine the Redundant States into One State
We choose to re-label \(\mathsf{stG}\) as \(\mathsf{stE}\) to simplify our work. To do this, we remove the row entries corresponding to \(\mathsf{stG}\) from the state table entirely. Then, we replace any remaining appearances of \(\mathsf{stG}\) in the table cells with its new \(\mathsf{stE}\) label. Alternatively, we could have chosen to re-labeled \(\mathsf{stE}\) as \(\mathsf{stG}\) instead. Both choices lead to a functionally equivalent circuit, though the alternative approach would simply use a different label and a unique binary value for that specific state.
Step 4: Update the State Table
The state table at the completion of iteration 1 is shown here.
Step 5: Repeat the Process until No More Redundant States can be Found
We repeat this process to track down any other redundant states. Looking closely, we notice that \(\mathsf{stD}\) and \(\mathsf{stF}\) are now redundant, as illustrated in the figure.
To simplify things, we re-label \(\mathsf{stF}\) as \(\mathsf{stD}\), remove its corresponding row, and update any remaining cells that still reference \(\mathsf{stF}\).
After running one final check, we confirm there are no more redundant states left, and the final minimized state table is displayed right here.
Step 6: Re-draw the State Diagram with the Combined States
The final state diagram is re-drawn based on the final optimized version of the state table.
