Skip to main content Accessibility help
Internet Explorer 11 is being discontinued by Microsoft in August 2021. If you have difficulties viewing the site on Internet Explorer 11 we recommend using a different browser such as Microsoft Edge, Google Chrome, Apple Safari or Mozilla Firefox.

Chapter 17: Factoring finite-state machines

Chapter 17: Factoring finite-state machines

pp. 375-397

Authors

, Stanford University, California, , Google Inc., New York, , University of British Columbia, Vancouver
Resources available Unlock the full potential of this textbook with additional resources. There are Instructor restricted resources available for this textbook. Explore resources
  • Add bookmark
  • Cite
  • Share

Summary

Factoring a state machine is the process of splitting the machine into two or more simpler machines. Factoring can greatly simplify the design of a state machine by separating orthogonal aspects of the machine into separate FSMs where they can be handled independently. The separate FSMs communicate via logic signals. One FSM provides input control signals to another FSM and senses its output status signals. Such factoring, if done properly, makes the machine simpler and also makes it easier to understand and maintain – by separating issues.

In a factored FSM, the state of each sub-machine represents one dimension of a multidimensional state space. Collectively the states of all of the sub-machines define the state of the overall machine – a single point in this state space. The combined machine has a number of states that is equal to the product of the number of states of the individual sub-machines – the number of points in the state space. With individual sub-machines having a few tens of states, it is not unusual for the overall machine to have thousands to millions of states. It would be impractical to handle such a large number of states without factoring.

We have already seen one form of factoring in Section 16.3 where we developed a state machine with a datapath component and a control component. In effect, we factored the total state of the machine into a datapath portion and a control portion. Here we generalize this concept by showing how the control portion itself can be factored.

In this chapter, we illustrate factoring by working two examples. In the first example, we start with a flat FSM and factor it into multiple simpler FSMs. In the second example we derive a factored FSM directly from the specification, without bothering with the flat FSM. Most real FSMs are designed using the latter method. A factoring is usually a natural outgrowth of the specification of a machine. It is rarely applied to an already flat machine.

About the book

Access options

Review the options below to login to check your access.

Purchase options

eTextbook
US$95.00
Hardback
US$95.00

Have an access code?

To redeem an access code, please log in with your personal login.

If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.

Also available to purchase from these educational ebook suppliers