Moore state machine solver and optimizer

A Moore machine is a finite-state machine whose output values are determined solely by its current state, in contrast to a Mealy machine. A state machine has a number of states, which are usually conveniently labeled 0, 1, 2, etc.. Below you can find a utility that can help you design and implement a state machine in hardware.

When you have to implement the state machine in hardware you have to find a way to map these abstract states into logical signals. There are a lot of possibilities. Two of the most common are:

  • Use one signal for each state, e.g. if there are 3 states you must use 3 signals (S0, S1, S2). Each signal requires its own electrical path so this method becomes quickly inefficient as the number of states increases. On the other hand, it is quite easy to derive the transition (next state) functions and the output functions because you don’t have to deal with any special encoding of states, e.g. OUTPUT_A = STATE_1 OR STATE_2 can be easily implemented in hardware with a 2-input OR gate, because every state has its one signal.
  • Encode states in binary, e.g. state 0 is encoded as 00, state 1 as 01, state 2 as 10. Each binary digit requires its own electrical path. That way we minimize the number of signals required but we increase the complexity of the transition and output functions.

The utility presented here has two features that can help designers implement their state machines in hardware:

  • For a given mapping of abstract states to state encodings, it uses the Quine-McCluskey algorithm in order to find the minimum two-level logic functions that implement the state machine.
  • It can try all permutations of state encodings for a given state word length in order to find the one that minimizes the total complexity of all the required functions for the implementation of the state machine. Be aware, that this mode of operation has exponential complexity so it can only be used for relatively small state machines.

You can find the Moore state machine solver and optimizer here: optistate.py

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: