Field-Programmable Gate Arrays: Reconfigurable Logic for Rapid Prototyping and Implementation of Digital Systems

2.3   STATE MACHINES

State machines provide a formalism for sequential logic. Finite state machines (FSM), as the name implies, have a finite amount of memory. The next state of any FSM depends on its present state and its inputs. There are two types: the Moore, or state output machine, in which the output depends strictly on the present state, and the Mealy, or transition output machine, in which the output depends on both the current state and the inputs. A well-known example, the traffic light controller [Mead80], is useful in bringing out the distinction.

A farm lane intersects a busy highway. There is a sensor to detect the presence of vehicles on the lane and traffic lights control both lane and highway. Figure 2–4 shows the state diagram. Assuming there has been no farm traffic for a while, the detection of a vehicle on the lane will cause the highway traffic lights to switch from green to yellow, staying in yellow for a short time—say 5 seconds. Then they will change to red, while the farm lane lights display green. After a longer time—say 30 seconds—or if no cars are detected, the lights will show yellow for a short time to the farm lane while maintaining red to the highway traffic. Finally, the cycle completes by presenting green to the highway again. A longer time-out—30 seconds—prevents the cycle being repeated too frequently. The two time-outs, short and long, are produced by a separate timer. Note that it is started as a result of a transition, rather than presence ...