An Introduction to Finite State Machine Design

First naive design

Just like a completed jigsaw begins with a first piece, whereever in the whole frame that piece is, my usual approach to tackle a problem is to start from a very simple idea and see if it works. For this problem there is only one output LED, and it has only two states, ON or OFF, so two states might suffice. I cast this idea into a state diagram for Moore machine in Figure 2

Figure 2: A state diagram consisting of only two states

Simply stated, when no switch is pressed, the state remains the same. It only toggles when either switch is active. From this diagram, I transfer the data to a state transition table, with the AB=00 cases as X (dont’ care)

Notice that the state is just output bit of a DFF, so as the LED output since they carry the same logic at all time. At this point I guess you already doubt if this seemingly too simple design could work at all. Actually, it does not! I proceed anyway to demonstrate the design steps of state diagram approach, and to locate the bug afterwards. The next step is determine a combinational circuit that generates the next state logic. Putting the data from above table into a Karnaugh map

and perform standard SOP minimization. The resulting boolean equation for state update is
q_new = A’q’ + B’q’ + ABq
This next state logic must be fed to the input of the DFF. This can be implemented by the schematics shown in figure 3.

Figure 3: schematics for the first naive design
or one could implement on a CPLD/FPGA using his prefered HDL. Using Verilog as an example


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