Finite State Machine Optimization

Nature is as complex as it needs to be . . . and no more.

-A. Einstein

Introduction

We are now ready to complete the finite state machine design process introduced in Chapter 8. The steps of Chapter 8 yield an abstract description of the state machine. This may be a state diagram, an ASM chart, or a hardware description language specification. Deriving a symbolic state transition table from one of these is straightforward. In this chapter, we concentrate on state minimization, state assignment, and choice of flip-flops.

We show why finite state machine "optimization" (improvement might be a better word) is still important, even in today's era of very large scale integrated circuits. We present pencil-and-paper methods, as well as more formal techniques suitable for computer implementation, for reducing the number of states and for choosing a state encoding.

Then we examine the approaches for choosing the machine's flip-flops and how the choice affects the next-state and output combinational functions. The right choice of flip-flop leads to a smaller gate count and thus fewer components to implement the machine.

Finally, we develop techniques for partitioning complex finite state machines into simpler, smaller, communicating machines. You may be forced to partition your state machine because it cannot fit into a given programmable logic component. This could arise, for example, because of limited logic resources, such as input/outputs, product terms, or flip-flops.

In this chapter, we emphasize the following techniques and -concepts:

Procedures for optimizing a finite state machine. You will learn the methods for state minimization and state assignment.
Application of modern computer-aided design tools for state assignment. CAD tools make it possible for you to evaluate the implementation complexity of alternative state assignments very rapidly.
Partitioning methods. You will learn the techniques for breaking finite state machines into smaller, communicating state machines that are well suited for implementation with programmable logic.

1. Motivation for Optimization
2. State Minimization/Reduction
3. State Assignment
4. Choice of Flip-Flops
5. Finite State Machine Partitioning
Chapter Review
Exercises

[Table of Contents] [Next] [Previous]

Finite State Machine Optimization

Introduction

Table of Contents

This file last updated on 07/15/96 at 06:40:56. randy@cs.Berkeley.edu;

This file last updated on 07/15/96 at 06:40:56.
randy@cs.Berkeley.edu;