An Introduction to Finite State Machine Design

Roughly speaking, a synchronous Finite State Machine (FSM) refers to a digital circuit/system that has memory, and is driven by a clock signal to change from one state to another depending on the applied input and its previous state. This classification covers from the simplest circuit consisting of only one D flip-flop, to a high-performance computer system. One might refer to FSM as a sequential circuit, in contrast to a combinational circuit that is memoryless. With latest electronics/computer technology, an FSM of low to medium complexity can be designed and implemented rather easily using CPLD/FPGA and software tools. The main advantages of this approach are flexibility, compactness, and ease of maintenance. Hardwiring TTL/CMOS logic gate and DFF ICs together on a PCB is now considered outdated.

Previously on this website, we discussed some design and implementation of quadrature encoder interface circuits (see, for example, VHDL code for quadrature encoder receiver module and reference therein). That is an example of FSM which I normally use in my embedded system classes. I have found, however, that the circuit is somewhat too complicated to beginners who do not have enough background from a basic digital system course. So the purpose of this article is to provide a more simple example and hopefully help students grab the essence of two common approaches for FSM design: the State Diagram , and Algorithmic State Machine (ASM)

Problem Setup

Electrical engineers/technicians familiar with interior lighting know how to design a multiway switch system to control a light bulb from more than one location. A common place for such application is a stairway light that allows family members to turn the light on/off from upstair/downstair, as shown in Figure 1. A switch used in a typical house is of SPDT type, which stays ON or OFF after someone pushes it. To exploit memory facility of an FSM, we use push button switches for both places. So the circuit must be able to retain its state or transit to another state depending on a pulse generated from either of the switch.

Figure 1: A “3-way” lighting using push button switches

To further simplify the problem, let’s say that a single person lives in this house. So no chance of the two switches pressed at the same time. We ‘re gonna implement this circuit on a Xilinx CPLD using CPLD Explorer XC9572 board , which contains necessary input/output components. For this application, only 2 push-button switches and 1 LED are needed. The push-button PB1 and PB2 represent switch A and B, and LED1 is our stair light. Note that all push-button switches on the board are active-low.

Tips: if you wish to control a real light bulb, simply wire this LED output to a transistor that drives a relay coil. For this experiment we focus only on the control logic of FSM.

So the desired functionality is simple: each time the house owner presses either of the A or B switch, the light must invert its state; i.e, from OFF to ON, or ON to OFF. Design an FSM to accomplish this.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s