We are looking for beta testers for our mobile app Prefies (pref-ies).
To participate, please go to prefies.com and use access code “Teahlab”.
Many thanks and Happy Holidays!
Puzz! Turn your photo into a puzzle!
Get Puzz! in Google Play

MOORE FINITE STATE MACHINE: CONTROL CIRCUIT FOR
AUTOMATIC DOOR
by Isai Damier

Problem Description for Control Circuit

Some time ago, I had a fictitious meeting with the representatives of a department store. They were planning to upgrade their chain of stores with automatic double doors that swing open, and so they hired me to build a circuit to control the automatic operation of the doors. They had two specific requirements. First, while opening, a door should not hit shoppers who happen to be standing behind the entrance. Second, when no one is around, the door should stay closed to save on air conditioning cost.

Requirement Analysis for Control Circuit

This problem is asking me to replace a doorman with a machine (a circuit to be exact). So instead of trying to come up with some fancy engineering solution, I go to a doorman and ask him to explain his work to me. He took a piece of napkin and a pencil and drew the picture in Figure 1 below.


Figure 1: Doorman Diagram

I asked him to explain the drawing and here is what he said: “ This is no rocket science. A door is either open or closed. So I draw two boxes and label one open and one closed. If the door is closed, I open it only when there are people in front of it but nobody to the REAR of it. So I draw an arrow from closed to open and label it front. In addition, the only time I close a door that's already open is when there is nobody around. So I draw another arrow from open to closed and label it neither. Under all other conditions, if the door is open it will stay open. And if the door is closed, it will stay closed. So I draw the two other arrows and label them with everything else. ”



Clearly this doorman has an eye for details. My work is done. The doorman's schematic is all I need to build the circuit. Nevertheless, a good inventor never reveals his sources. Hence, in my official report I changed what the doorman told me so to sound high-tech. First, I labeled the drawing state transition diagram to make it sound sophisticated (see Figure 2 below). Second, I revised the doorman's explanation and wrote the following.

To read the state transition diagram in Figure 2, imagine the door has two floor pads -- a front pad and a rear pad -- and that the circuit controlling the door is listening to weight on the pads. Therefore, Neither means there is nobody on either pad; Front means there is someone on the front pad only; Rear means there is someone on the rear pad only; and Both means there are people on both pads.


Figure 2: State Transition Diagram

Of course I thanked the doorman for his pains and bought him lunch. I am a nice guy.

Designing the Control Circuit

In reality, the state diagram in Figure 1 is the solution to the problem. Once you have a state diagram, the rest is just techniques. Indeed there are many software applications right now that can print a working circuit from a state diagram. Therefore, it's very important to practice drawing state diagrams. Take a pencil and paper and try to draw the doorman's schematic from the description. Do not continue until you get the drawing right. You must think like the doorman. Be the doorman.

From the state diagram, you are four steps away from a working circuit.

  1. Translate the state diagram to a table
  2. Make the table look like K-maps
  3. Get the Boolean expressions from the K-maps
  4. Draw the circuit from the Boolean equations.
Step 4 is not really worth mentioning. But I add it for the sake of completeness.

Digital System Implementation Procedure

A technique is like a magic trick: It's impressive the first time you see it; but once you get the secret, it becomes a joke. Our first technique is to translate the state diagram in Figure 1 into a table. From the state diagram we see that the door can be in two possible states (open; closed); and movement from state to state is governed by four conditions (neither; front; rear; both). To construct the table, we will label the rows by states (i.e. closed; open). And we will label the columns by conditions (i.e. neither; front; rear; both). Figure 3 below is our empty table.

State Conditions
Neither Front Rear Both
Closed
Open

Figure 3: Empty State Transition Table

Next we fill the table by following the arrows in the state diagram. For instance, the arrow that goes from closed to open is labeled front; which means if the door is closed and the condition is front then the door will go open. So in Figure 4, we write open in the cell where closed and front intersect.

State Conditions
Neither Front Rear Both
Closed Open
Open

Figure 4: State Transition Table with one cell

Figure 5 represents the completed state transition diagram. I add a few more labels to make the table easier to read. You should check Figure 5 against Figure 1 to make sure that the information match exactly.

Given state of door Shopper location
Neither Front Rear Both
What will happen to door (Next State)
Closed Closed Open Closed Closed
Open Closed Open Open Open

Figure 5: State Transition Table

Nearly all designers use this table. As a result, different people call the table by different names: state table, excitation table, flow table, state assigned table, etc. Whatever name you choose to call the table, make sure your audience knows what you are talking about.

Because the table represents the operation of a logic circuit, it makes sense to replace the states with 0s and 1s: Closed = 0; Open = 1. Hence, Figure 5 becomes Figure 6.

Given state of door Shopper location
Neither Front Rear Both
What will happen to door (Next State)
0 0 1 0 0
1 0 1 1 1

Figure 6: Excitation Table

Some designers go further. They call the front pad F, the rear pad R, the given state q, and the next state Q; hence, changing the labels of the table. And they change the pad signals to 0s and 1s so that Neither becomes RF = 00, Front becomes RF = 01; Rear becomes RF = 10; Both becomes RF = 11. Hence, Figure 6 becomes Figure 7.

Given state of door q Shopper Location
RF
00 01 10 11
What will happen to door (Next State Q)
0 0 1 0 0
1 0 1 1 1

Figure 7: State Assigned Table

I told you this table were famous!

Now for the cool trick: if we interchange column 10 with column 11, Figure 7 becomes a K-map! And from the K-map we can get the logic expression for Q, which we do next.

Given state of door q Shopper Location
RF
00 01 11 10
What will happen to door (Next State Q)
0 0
1
0 0
1 0
1
1
1

Figure 8: K-Map

Q = R' • F + q•R.
This is our Boolean function, and Q is the next state of the door.

Finite State Machines have Memory

Normally at this point we would say our work is done and implement the circuit directly from the Boolean expression. But if you try to build this circuit, you will find that q does not have a source. We know that signal F is coming from the front pad and that signal R is coming from the rear pad. But where is signal q coming from?

Intuitively, we know that q is whatever Q was previously. In other words, if we run the control circuit five times, then q(t1) = Q(t0), … q(t5) = Q(t4). This means the circuit must find a way to remember the value of Q, so it can use the value as q next time it has to run. To remember past information, digital systems use flipflops as storage units. Hence, we must input the value of Q into a flipflop. And when we need the value to use as q, simply get it from the output of the flipflop.

We create the circuit as below, linking Q to q using a D-flipflop.

The basic logic NOT gate circuits: an interactive inverter logic circuit where you see its function.
Circuit 1 — Play around with the circuit to see how it works

In reality, which flipflop you use depends on which flipflop you have available. I choose a D-flipflop above because it was convenient. Recall how a D-flipflop works: after each clock cycle, the output becomes the input. Since that's exactly what our control circuit needs to do with Q and q, the D-flipflop was an easy choice.

But what if you only have a JK flipflop? Then you would apply the rules of a JK flipflop to the excitation table in Figure 7 in order to get the input equations for J and K. The rules for a JK flipflop are simple, see Figure 9 below:

  • If the flipflop is to go from state 0 to state 0, then J=0 and K=d (d means don't care; you choose whatever you want for K, 0 or 1).
  • If the flipflop is to go from state 0 to state 1, then J=1 and K=d.
  • If the flipflop is to go from state 1 to state 1, then J=d and K=0.
  • If the flipflop is to go from state 1 to state 0, then J=d and K=1.
q Q J K
0 0 0 d
0 1 1 d
1 0 d 1
1 1 d 0

Figure 9: JK Flipflop Characteristic Table

Figure 10 is a typical way of changing an excitation table to accommodate the JK flipflop. We basically create an extra column for JK under each RF value and then evaluate JK using the characteristic table in Figure 9.

Present
State
Flipflop Inputs
RF = 00 RF = 01 RF = 11 RF = 10
q Q JK Q JK Q JK Q JK
0 0 0d 1 1d 0 0d 0 0d
1 0 d1 1 d0 1 d0 1 d0

Figure 10: Excitation Table with JK Flipflops

To get the Boolean expression for J, we assemble all the J values in one table, as in Figure 11 below. And since the table is already in K-map form, we simply extract the expression: so that J = R' • F.

q RF = 00 RF = 01 RF = 11 RF = 10
0 0
1
0 0
1 d
d
d d

Figure 11: Karnaugh map for J input of flip flop

Doing similarly for K in Figure 12, we get K = R' • F'.

q RF = 00 RF = 01 RF = 11 RF = 10
0
d
d d d
1
1
0 0 0

Figure 12: Karnaugh map for K input of flip flop

We show the JK version of the circuit below. Notice how using a JK flipflop obviates the need to get feedback data from the state variable q. That often happens; sometimes using the right flipflop can reduce the complexity of a circuit.

Circuit 2 — Play around with the circuit to see how it works

Epilogue

While it is always possible to build sequential systems that do not depend on the passage of time (i.e. asynchronous systems), it is often easier to build machines that do indeed depend on some representation of time. We live in a temporal universe. For us time is always continual. Hence, in both the D-flipflop and the JK flipflop versions of the control circuit, we use a time signal to regulate the circuit. In reality the source of the time (CLK) signal can be an actual clock or any persistent system. We do not account for the CLK signal in the Boolean expressions because the CLK signal comes standard with the flipflops.


Get Phuzz! in Google Play