[Top] [Next] [Prev]

Chapter Review

This chapter has concentrated on the optimization of finite state machines. We have emphasized the methods for state reduction, state assignment, choice of flip-flops, and state machine partitioning. For state reduction, we introduced the row matching and implication chart methods. These can be used to identify and eliminate redundant states, thus reducing the number of flip-flops needed to implement a particular finite state machine.

We then examined heuristic methods for state assignment, aimed at reducing the number of product terms or literals needed to implement the next-state and output functions. Since paper-and-pencil methods are not particularly effective, we introduced computer-aided design tools for state assignment that do a much better job in a fraction of the time: nova, mustang, and jedi.

The latter part of the chapter focused on choosing flip-flops for implementing the state registers of the finite state machine. J-K flip-flops tend to be most effective in reducing the logic, but they require logical remapping of the next-state functions and more wires than the simpler D flip-flops.

Finally, we discussed state machine partitioning methods, in particular partitioning based on inputs and outputs and partitioning by introducing idle states. These techniques are needed when we cannot implement a finite state machine with a single programmable logic component.

In the next chapter, we will examine implementation strategies in more detail. In particular, we will look at the methods for implementing finite state machines based on structured logic methods, such as ROM, programmable logic, and approaches based on MSI components.

Further Reading

The traffic light controller example used extensively in this chapter is borrowed from the famous text by C. Mead and L. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, MA, 1979. C. Roth's book, Fundamentals of Logic Design, West Publishing, St. Paul, MN, 1985, has an extensive discussion of state assignment guidelines that formed the basis of our Section 9.3.2. Modern Logic Design by D. Green, Addison-Wesley, 1986, has a highly readable, short, direct description of state assignment (pp. 40-43).

Nova's approach to state assignment is described in T. Villa and A. Sangiovanni-Vincentelli's paper "NOVA: State Assignment of Finite State Machines for Optimal Two-Level Logic Implementations," given at the 26th Design Automation Conference, Miami, FL (June 1989). A revised and expanded version of the paper appeared in IEEE Transactions on Computer-Aided Design in September 1990 (vol. 9, no. 9, pp. 1326-1334). Mustang's method is described in "MUSTANG: State Assignment of Finite State Machines Targeting Multi-level Logic Implementations," by S. Devadas, B. Ma, R. Newton, and A. Sangiovanni-Vincentelli, in IEEE Transactions on -Computer-Aided Design, vol. 7, no. 12 (December 1988). Jedi's method for symbolic assignment is described by Lin and Newton in "Synthesis of Multiple Level Logic from Symbolic High-Level Description Languages," which appeared in the Proceedings of the VLSI'89 Conference, Munich, West Germany, in August 1989.

These tools (along with espresso and misII) are available for a very modest charge from the Industrial Liaison Program Office of the Electrical Engineering and Computer Science Department, University of California, Berkeley. Detailed descriptions of how to invoke the tools, as well as examples of their use, can be found in the most current OCTTOOLS Manual distributed by that office.

Finite state machine partitioning is a topic that waxes and wanes in importance. The original work was done in the late 1950s, became less interesting during the era of VLSI, and is becoming more important again with pervasive use of programmable logic in digital designs. The topic is not well covered by most of today's textbooks. One exception is M. Bolton's book, Digital System Design with Programmable Logic, Addison-Wesley, Wokingham, England, 1990, which offers a section on the topic. The partitioning rules introduced in Section 9.5.1 were obtained from an applications note in the Altera Applications Handbook, Altera Corporation, Santa Clara, CA, 1988.

[Top] [Next] [Prev]

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