[Top] [Next] [Prev]

Chapter Review

In this chapter, we have concentrated on understanding the basic timing behavior of a finite state machine: when inputs are sampled, when the next state and outputs undergo transition, and when these become stable. We presented the Moore and Mealy machine organizations, the latter in both asynchronous and synchronous forms. The basic idea is that you can represent a finite state machine by combinational logic functions of the current state (both Moore and Mealy machines) and inputs (Mealy machine) for the next state and output. Flip-flop storage elements hold the current state.

We introduced a six-step process for finite state machine design, and the body of this chapter concentrated on the first two of these steps: understanding the problem and obtaining an abstract representation of the finite state machine from an imprecise description of its behavior. We cover the remaining four steps, state minimization, state assignment, implementation of the state registers, and implementation of the next state and output combinational functions, in Chapter 9.

In terms of abstract FSM representations, we presented the algorithmic state machine (ASM) notation as a precise way to describe FSM behavior using a flowchart-like description. In addition, we gave example descriptions in popular hardware description languages, VHDL and ABEL.

We illustrated the process of mapping a word specification to a state diagram or ASM chart with four detailed case studies: a finite string recognizer, a complex counter, a traffic light controller, and a digital combination lock. The mapping strategies are founded on (1) understanding the input/output behavior of the specified FSM, (2) drawing diagrams to help understand the problem statement, (3) enumerating states and developing state transitions for the expected or "goal" cases, (4) expanding the description to include the exceptional or error states and transitions, and (5) carefully reusing states whenever possible.

We are now ready to examine the process of finite state machine optimization and implementation in the next two chapters.

Further Reading

The concept of algorithmic state machines (ASMs) has appeared in several recent books. A very good, albeit brief, description can be found in Prosser and Winkel, The Art of Digital Design, Prentice-Hall, Englewood Cliffs, NJ, 1987. A more detailed mathematical description is to be found in Green, Modern Logic Design, Addison-Wesley, Wokingham, England, 1986.

VHDL is a government-backed industry standard hardware description language. Several vendors of computer-aided design tools now provide VHDL simulator support. Armstrong, Chip-Level Modeling with VHDL, Prentice-Hall, 1989 provides an excellent tutorial introduction to modeling hardware systems with VHDL. The language's capabilities are presented in a step-by-step fashion as the reader advances through the text. A more exhaustive (and exhausting) description can be found in Coehlo, The VHDL Handbook, Kluwer, Boston, MA, 1989. This book includes voluminous example VHDL models for standard TTL components, such as gates, multiplexers, counters, and ALUs, and also contains the description of a complete RISC (reduced instruction set computer) processor.

[Top] [Next] [Prev]

This file last updated on 07/14/96 at 21:28:46.
randy@cs.Berkeley.edu;