How to Encode FSMs into Binary Transition Tables

This article outlines the systematic process of converting any finite state machine (FSM) into binary-encoded state transition tables for digital hardware implementation. The procedure involves calculating the required number of binary bits for states, inputs, and outputs, assigning unique binary codes to each symbolic element, translating the conceptual state transitions into a binary truth table, and handling unused binary states. This conversion bridges high-level algorithmic state diagrams and low-level digital logic circuits such as flip-flops and combinational logic gates.

Step 1: Quantify States, Inputs, and Outputs

To represent an FSM in binary, first determine the minimum number of binary digits (bits) required to uniquely identify all discrete states, input conditions, and output symbols.

• State Bits (\(n\)): If an FSM has \(N\) total states, the number of required state variables (flip-flops) \(n\) is calculated using the ceiling function: \[n = \lceil \log_2(N) \rceil\]
• Input Bits (\(k\)): If the machine responds to \(M\) distinct input conditions, the number of binary input lines \(k\) is: \[k = \lceil \log_2(M) \rceil\]
• Output Bits (\(m\)): If the system generates \(P\) distinct outputs, the number of binary output lines \(m\) is: \[m = \lceil \log_2(P) \rceil\]

Step 2: Assign Binary Codes (State Assignment)

Assign a unique \(n\)-bit binary string to every named state in the FSM. While different encoding schemes exist (such as Gray code or One-Hot encoding), standard binary encoding assigns sequential binary values to each state: * State \(S_0 \rightarrow 00\dots0_2\) * State \(S_1 \rightarrow 00\dots1_2\) * State \(S_{N-1} \rightarrow \text{binary representation of } (N-1)\)

The same sequential assignment is applied to inputs (\(I_0, I_1, \dots\)) and outputs (\(O_0, O_1, \dots\)).

Step 3: Construct the Symbolic Transition Table

Before full binary conversion, document the FSM’s behavior in a standard tabular format based on its state diagram. The symbolic table contains four primary columns: 1. Present State (\(S\)): The current state of the machine. 2. Input (\(X\)): The active external condition. 3. Next State (\(S'\)): The state to which the machine transitions. 4. Output (\(Y\)): The generated control signals (dependent on Present State and Input for a Mealy machine, or Present State only for a Moore machine).

Step 4: Map Symbolic Values to Binary Vectors

Replace all symbolic entries in the transition table with their corresponding binary representations: * Replace the Present State with \(n\) state variables: \(Q_{n-1}, Q_{n-2}, \dots, Q_0\). * Replace the Input with \(k\) input variables: \(X_{k-1}, X_{k-2}, \dots, X_0\). * Replace the Next State with \(n\) next-state variables: \(D_{n-1}, D_{n-2}, \dots, D_0\) (or \(Q^+_{n-1}, \dots, Q^+_0\)). * Replace the Output with \(m\) output variables: \(Y_{m-1}, Y_{m-2}, \dots, Y_0\).

Step 5: Complete the Binary State Transition Table

Combine the binary inputs and present state variables to form the table’s inputs (left side), and the next state variables and output variables to form the table’s outputs (right side).

For example, an FSM with 3 states (\(S_0, S_1, S_2\)) requiring \(n=2\) bits (\(Q_1, Q_0\)) and 1 input bit (\(X\)) produces a binary transition table like the following:

Step 6: Handle Unused States (Don’t-Care Conditions)

If the total number of states \(N\) is not a power of 2, there will be \(2^n - N\) unused binary combinations. * Add the unused state combinations (e.g., \(Q_1 Q_0 = 11\) in a 3-state machine) to the binary table. * Assign Don’t-Care conditions (\(X\)) to their corresponding Next State and Output entries.

These don’t-care entries provide flexibility to simplify the final Boolean equations during circuit synthesis.

Step 7: Derive Boolean Functions

Once the binary state transition table is complete, it acts as a standard truth table. Each Next State bit (\(Q^+\)) and Output bit (\(Y\)) is treated as a separate Boolean function of the Present State and Input variables. These functions can be directly extracted via Karnaugh Maps (K-maps) or automated logic minimization algorithms to implement the hardware using flip-flops and logic gates.