5.4 The FSM design process: a vending machine

Why this matters

Section 5.2 started from a finished diagram. Real designs start from a paragraph of English, and the hard part is going from that paragraph to a diagram that is right. This section walks the whole path once, on a machine small enough to hold in your head: first deciding what the circuit has to remember, then drawing it, then turning the picture into equations that a circuit can implement.

Learning goals

• Turn a description in words into a list of inputs, outputs and the facts the machine must remember.
• Draw a state diagram for a machine with two inputs, and leave out the input combinations that can never happen.
• Build the encoded truth table of a machine from its diagram.
• Read the next-state and output equations off Karnaugh maps, using don't cares.
• Count the states, state bits, arrows and truth-table rows of a machine.

Intuition first

Picture a person sitting at a counter in front of a gumball dispenser, with a hand on the release lever. Coins arrive one at a time. The person does not need a record of every coin that ever came through. They need one fact: how much money is waiting right now. If it is nothing, a nickel makes it five cents. If it is five cents, any coin brings the total to ten or more, so they pull the lever and the next customer starts from nothing.

That one fact is the state of the machine, and the rest of the design is bookkeeping. The only question that takes thought is what the smallest useful fact is. Here it is two possibilities, "no money waiting" and "one nickel waiting", and a circuit can remember two possibilities in a single flip-flop.

The four steps

Definition 5.4.1(FSM design process).

The FSM design process turns a description into a circuit in four steps. First, understand the problem: list the inputs and outputs and say in plain sentences what the machine must do. Second, draw the state diagram, together with a block diagram of the machine and the logic around it. Third, use the diagram to fill in a truth table whose inputs are the present state and the machine's inputs, and whose outputs are the next state and the machine's outputs. Fourth, use the truth table to design the combinational logic for each output.

Every step has a way to go wrong that the later steps cannot repair, so check each one before moving on. A state diagram that matches a misread description gives a perfectly correct circuit for the wrong machine.

Step 1: understand the problem

Example 5.4.1(the gumball machine).

A gumball machine has one coin slot that takes nickels and dimes. In any clock cycle the coin sensor reports at most one coin: a nickel on the input N, or a dime on the input D, or nothing. As in Section 5.2, each report is taken as it is: a coin is in the slot for exactly one clock cycle, and the machine does not turn a longer signal into a single coin. The machine opens the gumball gate, by raising its output Open, once the money in it adds up to at least ten cents. It gives no change, so a nickel followed by a dime is accepted even though the two coins add up to fifteen cents. After it opens, the next coin starts a new sale. Open is 1 in the cycle in which the coin that completes the price is in the slot, which makes it a Mealy output: it depends on the state and on the coin in the same cycle.

The machine has three outside signals besides the coin inputs: the clock, a reset that puts it in its starting condition, and the output to the release mechanism.

Illustration a block diagram that explains an idea; its behavior is not checked

A block diagram with inputs reset and clk and outputs none.

Block "coin sensor" sensor: N is n1, D is n2.

Block "vending FSM" fsm: N is n1, D is n2, reset is reset, clk is clk, Open is n3.

Block "release" release: Open is n3.

This diagram is illustrative: its behavior is not checked.

Description: Three boxes in a row. The coin sensor on the left has two output lines, N and D, that go to the vending FSM box in the middle. Two more lines labeled reset and clk also enter the vending FSM from the lower left. A line labeled Open leaves the vending FSM and goes to a box labeled release on the right, with the words gumball gate under it.

Figure 5.4.1. The machine in its surroundings. The coin sensor gives N and D to the state machine, which gives Open to the release that works the gumball gate. Reset and clock go to the state machine.

What must the machine remember? Only the money that has not yet reached the price. Zero cents and five cents are the two possibilities: with ten cents the machine opens and starts over, so ten never has to be stored. Two situations need two states, and two states need one state bit.

One more decision belongs to this step. The sensor reports at most one coin, so a nickel and a dime in the same cycle can never happen, and the machine is never asked what to do then. We call that input combination a don't care: we are free to let the design do whatever is cheapest, and we write down that we are doing so.

Step 2: draw the state diagram

We name the two states by the money waiting, 0¢ and 5¢ (in the SystemVerilog of Section 5.5 they are C0 and C5), and draw each state's arrows by asking what each input does there. The input part of a label is a product of literals, one for each input, with a bar over the ones that are 0. The label for a nickel alone is N with a bar over D, which says that N is 1 and D is 0.

In 0¢ there are three input combinations that can happen. With no coin, nothing changes and the output is 0. A nickel makes five cents, so the machine moves to 5¢ with output 0. A dime is already ten cents: the machine raises Open and, because the next sale starts fresh, stays in 0¢.

In 5¢ the same three cases come out differently. With no coin the machine stays and the output is 0. A nickel makes ten cents, so it opens and goes back to 0¢. A dime makes fifteen, so it also opens and goes back to 0¢. Both arrows lead to the same state with the same output, so they could be drawn as one arrow whose label joins the two input combinations with a plus sign; the diagram keeps them apart, one arrow for each coin.

Description: State diagram with two circles, 0 cents on the left and 5 cents on the right. A thick arrow from nowhere enters 0 cents. 0 cents has a self-loop for no coin with output 0 and another self-loop for a dime with output 1, and an arrow to 5 cents for a nickel with output 0. 5 cents has a self-loop for no coin with output 0 and two arrows back to 0 cents, one for a nickel and one for a dime, both with output 1.

Figure 5.4.2. The gumball machine. Each label gives the coins in the slot, then the output; the arrow from nowhere marks the starting state, 0 cents. The case of a nickel and a dime together has no arrow because it cannot happen.

The six arrows can be checked against the description one at a time, and the numbered copy of the diagram below lets us point at them. arrow 2 (0¢ to 5¢ when N=1, D=0, output 0) is the only arrow that leaves 0¢ for another state. arrow 3 (0¢ to 0¢ when N=0, D=1, output 1) is the one that opens the machine without changing the state.

Description: The same two-state diagram as the previous figure, with a number from 1 to 6 beside each arrow.

Figure 5.4.3. The same diagram with its arrows numbered.

The same machine as a state table, one row for every state and every coin that can occur:

State table of ch05/vending: one row for every present state and input combination, giving the next state and the output; inputs in the order N, D. X means the input combination cannot occur (don't care).

Present state	N	D	Next state	Open
0¢	0	0	0¢	0
0¢	0	1	0¢	1
0¢	1	0	5¢	0
0¢	1	1	X	X
5¢	0	0	5¢	0
5¢	0	1	0¢	1
5¢	1	0	0¢	1
5¢	1	1	X	X

A customer puts in a nickel, then another nickel, then a third nickel, then nothing, one cycle each, starting right after reset. Which output sequence does the machine produce, one digit per cycle, with the first cycle after reset as cycle 0 and listed first?

010001100010

Here is a slower customer, as a scenario table. Each column is one clock cycle, and in a scenario table cycle 0 is the first cycle after reset, the one in which the first input is applied. (The tour tables of Sections 5.2 and 5.6 count differently: they call the reset cycle itself cycle 0, so cycle $k$ of a scenario is cycle $k+1$ of the tour table of the same machine.) The machine remembers the first nickel while the slot is empty, and opens when the second one arrives.

Scenario wait-between-coins of ch05/vending, 5 cycles, cycle 0 first. Inputs: N is 1, 0, 0, 1, 0; D is 0, 0, 0, 0, 0. State in each cycle: 0¢, 5¢, 5¢, 5¢, 0¢. Open in each cycle: 0, 0, 0, 1, 0.

Cycle	0	1	2	3	4
N	1	0	0	1	0
D	0	0	0	0	0
State	0¢	5¢	5¢	5¢	0¢
Open	0	0	0	1	0

Cycle 0 is the first cycle after reset: the machine starts in 0¢, and each cycle ends with a clock edge.

Step 3: the truth table

A circuit can only store bits, so the states need codes. With two states one bit is enough, and we use 0 for 0¢ and 1 for 5¢. The truth table has one row for every combination of the state bit and the two inputs, so $2^{1+2} = 8$ rows. Each row is read off the diagram: find the arrow that leaves the state for those inputs, and copy its destination and its output.

Encoded truth table of ch05/vending: present-state bits PS and inputs N, D on the left, NS, Open on the right; 8 rows in ascending binary order, PS most significant; X means don't care (unused state codes and impossible inputs)

State	$\mathrm{PS}$	N	D	$\mathrm{NS}$	$\mathrm{Open}$
0¢	0	0	0	0	0
0¢	0	0	1	0	1
0¢	0	1	0	1	0
0¢	0	1	1	X	X
5¢	1	0	0	1	0
5¢	1	0	1	0	1
5¢	1	1	0	0	1
5¢	1	1	1	X	X

The two rows where N and D are both 1 have X in both outputs. Those are the don't cares from step 1: since the sensor cannot report two coins at once, no arrow was drawn for them, and the table is free to put whatever helps in their place.

Step 4: the logic

With one state bit the table has two outputs to implement: the next-state bit NS and Open. Each gets its own K-map. The state bit and N are on the columns and D is on the row, the three-variable layout of Section 5.3 with the first two variables on the columns.

NS = $\overline{\mathrm{PS}} \cdot N + \mathrm{PS} \cdot \overline{N} \cdot \overline{D}$

• $\overline{\mathrm{PS}} \cdot N$vertical pair: column 01 (2 cells); 1 of the cells is a don't care
• $\mathrm{PS} \cdot \overline{N} \cdot \overline{D}$single cell: row 0, column 10

Karnaugh map of NS: columns PS,N, rows D; cell values are 0, 1 or X for don't care

	PSN=00	PSN=01	PSN=11	PSN=10
D=0	0	1	0	1
D=1	0	X	X	0

Groups drawn:

1. not PS and N: vertical pair in column PS,N=01; 2 cells, 1 of them don't care.
2. PS and not N and not D: single cell in row D=0, column PS,N=10; 1 cell.

Description: Karnaugh map of the next-state bit with columns for the state bit and N and rows for D, with its two groups outlined.

Figure 5.4.4. The next-state bit. The cells where N and D are both 1 are don't cares; the group in which D changes uses one of them.

The vertical pair in column PS,N=01 has PS at 0 and N at 1 fixed, and D changes, so its term is $\overline{\mathrm{PS}} \cdot N$. One of its two cells is a don't care, and using it is what keeps the term from needing a $\overline{D}$. The other group is a single cell, which sits in the case of a state bit of 1, no nickel and no dime, so its term has all three variables: $\mathrm{PS} \cdot \overline{N} \cdot \overline{D}$. Nothing around it is a 1 or a don't care, so it cannot grow.

Open = $D + \mathrm{PS} \cdot N$

• $D$row of four: row 1 (4 cells); 2 of the cells are don't care
• $\mathrm{PS} \cdot N$vertical pair: column 11 (2 cells); 1 of the cells is a don't care

Karnaugh map of Open: columns PS,N, rows D; cell values are 0, 1 or X for don't care

	PSN=00	PSN=01	PSN=11	PSN=10
D=0	0	0	1	0
D=1	1	X	X	1

Groups drawn:

1. D: row of four in row D=1; 4 cells, 2 of them don't care.
2. PS and N: vertical pair in column PS,N=11; 2 cells, 1 of them don't care.

Description: Karnaugh map of the output Open with columns for the state bit and N and rows for D, with its two groups outlined.

Figure 5.4.5. The output Open. The group where D is 1 uses two don't cares, and the group where PS and N are both 1 uses one.

For the output, the row of four in row D=1 holds every case in which a dime is present: whatever the state and the nickel input are, a dime opens the machine. The vertical pair in column PS,N=11 is the nickel arriving in 5¢. Written as equations, the next state is $\overline{\mathrm{PS}} \cdot N +$ $\mathrm{PS} \cdot \overline{N} \cdot \overline{D}$ and the output is $D + \mathrm{PS} \cdot N$.

The don't cares earn their place. The term $\overline{\mathrm{PS}} \cdot N$ and the longer term $\overline{\mathrm{PS}} \cdot N \cdot \overline{D}$ agree on every input that can occur, and the shorter one is the one that comes out of the map.

$\overline{\mathrm{PS}} \cdot N$ $= \overline{\mathrm{PS}} \cdot N \cdot \overline{D}$ (for every input that is not a don't care)

The machine is now a register that holds PS and two small blocks of gates. The next figure draws those gates. Each small circle on a gate input inverts that input, which saves drawing separate inverters.

A logic schematic with inputs N, D, clk and reset and output Open.

AND gate a1: inputs inverted n1 and N; output n2.

AND gate a2: inputs n1, inverted N and inverted D; output n3.

AND gate a3: inputs n1 and N; output n5.

OR gate o1: inputs n2 and n3; output n4.

OR gate o2: inputs n5 and D; output Open.

Flip-flop ps: d is n4, q is n1, clocked by clk, synchronous reset reset.

It is checked against the module hdl:ch05/vending_machine.

Description: A schematic with inputs N, D, clk and reset on the left, five gates in the middle, a flip-flop on the right and the output Open at the lower right. A wire from the flip-flop output returns to the left to feed the AND gates.

Figure 5.4.6. The vending machine as gates and one flip-flop. The flip-flop holds PS; the upper gates compute NS and the lower gates compute Open.

The drawing is simulated against the SystemVerilog module of Section 5.5, so it computes the same function as the module that section lists. Reading the circuit from the equations is the same job as in Section 5.3.

Counting

The counts of Section 5.3 apply to any diagram: $\lceil \log_2 S\rceil$ state bits, at most $2^I$ arrows leaving a state, and $2^{s+I}$ truth-table rows. For the gumball machine, $S=2$, $s=1$, $I=2$: one state bit, at most four arrows leaving each state (three are drawn, because the fourth, both coins, is a don't care), and eight truth-table rows.

Course conventions

How CSE 369 writes this

In CSE 369 we write the inputs of a multi-input machine in a declared order, N then D here. The course draws this machine's arrows both as bit strings in that order (10 for a nickel) and as literal products; the book uses the products. The same machine can be encoded in different ways: which code a state gets is a choice, and different choices give different equations and different circuits, all equally correct. The book uses the 0 and 1 above for every view of this machine, so the diagram, the table, the maps, the circuit and the module in Section 5.5 all agree. When you work from lecture material, check the codes written in each picture before comparing equations.

Pitfalls

Common pitfall

• Starting to draw before the description is clear. Decide the inputs, the outputs and what must be remembered first; a diagram for a misread machine will pass every later check.
• Forgetting what happens after the output fires. A machine that opens must say where it goes next; here the sale ends and it starts over.
• Leaving an input combination out when it can happen. Only combinations that can never occur may go without an arrow, and the design should say which they are.
• Treating a don't care as a 0. In the K-map a don't care may be grouped when it helps and ignored when it does not; it is not a promise about what the circuit does.
• Mixing up the states of two versions of one machine. A diagram, a table and an equation must all use the same codes.

Check your understanding

Take the quiz (5 questions)

How many state bits does the gumball machine need?

123

How many rows does the machine's encoded truth table have?

864

The machine is in the state with 5 cents waiting and a dime arrives. What is the output?

10

The machine is in the state with no money waiting and a nickel arrives. Which state does it go to?

C5C0

Which expression gives the output Open when both coins can never arrive together?

$D + \mathrm{PS} \cdot N$$D \cdot \mathrm{PS} + N$$D + \overline{\mathrm{PS}} \cdot N$

Exercises

Exercise 5.4.1

A different gumball machine takes nickels (N), dimes (D) and quarters (Q), one coin at a time, and opens once the money in it adds up to at least 15 cents. It gives no change and starts over after it opens. Open is 1 in the cycle in which the coin that completes the price is in the slot. Draw its state diagram, with a label for each arrow, and say how many state bits it needs.

Hint

What is the largest amount of money that can be waiting without the machine having opened? Every amount that can be waiting is a state.

Solution

At 15 cents or more the machine opens, so the amounts that can be waiting are 0, 5 and 10 cents: three states, and two state bits. Now go through each state and each of the four ways a cycle can go: no coin, a nickel, a dime, a quarter.

From 0 cents, a quarter makes 25, so the machine opens and starts over, staying in the 0-cent state with output 1. A nickel moves to 5 cents and a dime to 10 cents, both with output 0, and no coin changes nothing.

From 5 cents, a dime makes 15 and a quarter makes 30, so both open the machine and return to 0 cents. A nickel makes 10, so it moves the machine to 10 cents without opening. No coin changes nothing.

From 10 cents, any coin brings the total to 15 or more, so a nickel, a dime or a quarter all open the machine and return to 0 cents. Only no coin stays.

Two or three coins in the slot at once cannot happen, so the combinations with more than one coin have no arrows.

Description: State diagram with circles for 0, 5 and 10 cents. The starting arrow enters 0 cents. Each state has a self-loop for no coin. From 0 cents, a nickel goes to 5 cents and a dime goes to 10 cents, and a quarter loops with output 1. From 5 cents a nickel goes to 10 cents and a dime or a quarter goes to 0 cents with output 1. From 10 cents any single coin goes back to 0 cents with output 1.

Figure 5.4.7. The 15-cent machine. Arrows that share a start, an end and an output are drawn once, with their coin combinations joined by plus signs.

State table of ch05/vend15: one row for every present state and input combination, giving the next state and the output; inputs in the order N, D, Q. X means the input combination cannot occur (don't care).

Present state	N	D	Q	Next state	Open
0¢	0	0	0	0¢	0
0¢	0	0	1	0¢	1
0¢	0	1	0	10¢	0
0¢	0	1	1	X	X
0¢	1	0	0	5¢	0
0¢	1	0	1	X	X
0¢	1	1	0	X	X
0¢	1	1	1	X	X
5¢	0	0	0	5¢	0
5¢	0	0	1	0¢	1
5¢	0	1	0	0¢	1
5¢	0	1	1	X	X
5¢	1	0	0	10¢	0
5¢	1	0	1	X	X
5¢	1	1	0	X	X
5¢	1	1	1	X	X
10¢	0	0	0	10¢	0
10¢	0	0	1	0¢	1
10¢	0	1	0	0¢	1
10¢	0	1	1	X	X
10¢	1	0	0	0¢	1
10¢	1	0	1	X	X
10¢	1	1	0	X	X
10¢	1	1	1	X	X

Tags: StandardFinite state machinesSequential logic

Exercise 5.4.2

A customer of the 15-cent machine of the previous exercise puts in a dime, lets two cycles pass with nothing in the slot, and then puts in another dime. The first dime arrives in cycle 0, the first cycle after reset. Fill in the state during each cycle and the output.

Scenario ten-cents-waits of ch05/vend15, 4 cycles, cycle 0 first. Inputs: N is 0, 0, 0, 0; D is 1, 0, 0, 1; Q is 0, 0, 0, 0. The state and output rows are empty for the reader to fill in.

Cycle	0	1	2	3
N	0	0	0	0
D	1	0	0	1
Q	0	0	0	0
State	blank	blank	blank	blank
Open	blank	blank	blank	blank

Cycle 0 is the first cycle after reset: the machine starts in 0¢, and each cycle ends with a clock edge.

Hint

The dime moves the machine to 10 cents, and an empty slot leaves it there. What does a dime do at 10 cents?

Solution

Follow the arrows one cycle at a time. In cycle 0 a dime is in the slot while the machine is in 0 cents, so the output is 0 and the state during cycle 1 is 10 cents. The two empty cycles leave the machine at 10 cents with output 0. When the second dime arrives in cycle 3, the machine holds 10 cents, the total is 20, and the output is 1.

Scenario ten-cents-waits of ch05/vend15, 4 cycles, cycle 0 first. Inputs: N is 0, 0, 0, 0; D is 1, 0, 0, 1; Q is 0, 0, 0, 0. State in each cycle: 0¢, 10¢, 10¢, 10¢. Open in each cycle: 0, 0, 0, 1.

Cycle	0	1	2	3
N	0	0	0	0
D	1	0	0	1
Q	0	0	0	0
State	0¢	10¢	10¢	10¢
Open	0	0	0	1

Cycle 0 is the first cycle after reset: the machine starts in 0¢, and each cycle ends with a clock edge.

Tags: Warm-upFinite state machinesSequential logic

Exercise 5.4.3

A machine has two inputs, A and B, and one output, Out. Out is 1 in the cycle that completes three cycles in a row in which A and B are equal, that is both 0 or both 1; the cycles need not agree on whether the equal value is 0 or 1. After that cycle the count starts over. Draw the state diagram, and then answer: how many state bits does the machine need, and how many rows does its truth table have?

Hint

The machine has to remember how many equal cycles in a row it has seen. Which counts are worth remembering, and what does a cycle where A and B differ do to the count?

Solution

The count of equal cycles in a row can be zero, one or two; three triggers the output and the count restarts, so it is never stored. That is three states, which we call R0, R1 and R2, and two state bits.

In every state, a cycle where A and B differ sends the machine back to R0 with output 0. A cycle where they agree moves it to the next state, with output 0 for R0 and R1. In R2 an equal cycle is the third in a row: the output is 1 and the machine goes to R0.

Description: State diagram with three circles R0, R1 and R2 in a row. A starting arrow enters R0. An arrow labeled with the two equal input combinations and output 0 goes from R0 to R1 and from R1 to R2. The arrow that carries the equal combinations from R2 back to R0 has output 1. From every state, the combinations where A and B differ lead to R0 with output 0.

Figure 5.4.8. The equal-inputs counter. Each state has one arrow for the two cycles in which A and B are equal and one for the two in which they differ, each drawn once with its combinations joined by a plus sign.

Two inputs and two state bits give $2^{2+2} = 16$ rows. Four of them, the ones for the unused state code, are don't cares.

Encoded truth table of ch05/s04-agree-run: present-state bits PS1, PS0 and inputs A, B on the left, NS1, NS0, Out on the right; 16 rows in ascending binary order, PS1 most significant; X means don't care (unused state codes and impossible inputs)

State	$\mathrm{PS}_{1}$	$\mathrm{PS}_{0}$	A	B	$\mathrm{NS}_{1}$	$\mathrm{NS}_{0}$	$\mathrm{Out}$
R0	0	0	0	0	0	1	0
R0	0	0	0	1	0	0	0
R0	0	0	1	0	0	0	0
R0	0	0	1	1	0	1	0
R1	0	1	0	0	1	0	0
R1	0	1	0	1	0	0	0
R1	0	1	1	0	0	0	0
R1	0	1	1	1	1	0	0
R2	1	0	0	0	0	0	1
R2	1	0	0	1	0	0	0
R2	1	0	1	0	0	0	0
R2	1	0	1	1	0	0	1
unused	1	1	0	0	X	X	X
unused	1	1	0	1	X	X	X
unused	1	1	1	0	X	X	X
unused	1	1	1	1	X	X	X

Tags: StandardFinite state machinesTruth tables

Exercise 5.4.4

A two-key pad has the keys A and B. In any clock cycle at most one key is down, since both together can never happen, and a press lasts one cycle. The output Out is 1 in a cycle in which a key is down and it is the same key that was pressed most recently before. In a cycle in which no key is down, Out is 0, and that cycle does not change which key was pressed most recently. So A and then A pulses Out on the second A, A and then B does not, and A, nothing, nothing, A pulses on the second A. After reset no key has been pressed yet.

1. Draw the state diagram. Use the states None, LastA and LastB with the codes 00, 01 and 10.
2. Write the encoded truth table, with PS1, PS0, A and B on the left and NS1, NS0 and Out on the right.
3. Draw a K-map for each of NS1, NS0 and Out, with PS1 and PS0 on the columns and A and B on the rows. Group the 1s, using the don't cares where they help, and write a minimal equation for each.
4. Suppose the register somehow holds the unused code 11. For each of the three input values that can occur, find the next code and Out. Can the circuit stay in the unused code?

Hint

The machine has to remember which key was pressed last, or that none was: three situations. The table has 16 rows. Two kinds of row are don't cares: the rows of the input value both keys down, and the rows of the unused code. In a four-variable map the two kinds overlap in one cell.

Solution

The diagram. An idle cycle changes nothing. A press of a key moves the machine to the state for that key, and the output is 1 only when the machine was already in that state.

Description: State diagram with three circles None, LastA and LastB. A thick arrow enters None. None has a self-loop for no key with output 0, an arrow to LastA for key A with output 0 and an arrow to LastB for key B with output 0. LastA has a self-loop for no key with output 0 and a self-loop for key A with output 1, and an arrow to LastB for key B with output 0. LastB has a self-loop for no key with output 0 and a self-loop for key B with output 1, and an arrow to LastA for key A with output 0.

Figure 5.4.9. The two-key repeat detector. Out is 1 on the arrows that repeat the key just pressed.

The table. Three states with three input values each give nine rows from arrows. The other seven rows are don't cares: the three rows of the input value in which both keys are down, one for each state, and the four rows of the unused code 11.

Encoded truth table of ch05/s04-repeat-key: present-state bits PS1, PS0 and inputs A, B on the left, NS1, NS0, Out on the right; 16 rows in ascending binary order, PS1 most significant; X means don't care (unused state codes and impossible inputs)

State	$\mathrm{PS}_{1}$	$\mathrm{PS}_{0}$	A	B	$\mathrm{NS}_{1}$	$\mathrm{NS}_{0}$	$\mathrm{Out}$
None	0	0	0	0	0	0	0
None	0	0	0	1	1	0	0
None	0	0	1	0	0	1	0
None	0	0	1	1	X	X	X
LastA	0	1	0	0	0	1	0
LastA	0	1	0	1	1	0	0
LastA	0	1	1	0	0	1	1
LastA	0	1	1	1	X	X	X
LastB	1	0	0	0	1	0	0
LastB	1	0	0	1	1	0	1
LastB	1	0	1	0	0	1	0
LastB	1	0	1	1	X	X	X
unused	1	1	0	0	X	X	X
unused	1	1	0	1	X	X	X
unused	1	1	1	0	X	X	X
unused	1	1	1	1	X	X	X

The maps. NS1 is 1 when the next state is LastB, which has the code 10. That happens whenever key B is down, and also whenever the machine is in LastB and key A is not down.

NS1 = $B + \mathrm{PS}_{1} \cdot \overline{A}$

• $B$group of eight: rows 01 and 11 (8 cells); 5 of the cells are don't care
• $\mathrm{PS}_{1} \cdot \overline{A}$2-by-2 square: rows 00 and 01, columns 11 and 10; 2 of the cells are don't care

Karnaugh map of NS1: columns PS1,PS0, rows AB; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
AB=00	0	0	X	1
AB=01	1	1	X	1
AB=11	X	X	X	X
AB=10	0	0	X	0

Groups drawn:

1. B: group of eight in rows AB=01 and 11; 8 cells, 5 of them don't care.
2. PS1 and not A: 2-by-2 square in rows AB=00 and 01, columns PS1,PS0=11 and 10; 4 cells, 2 of them don't care.

Description: A Karnaugh map of NS1 with columns PS1 PS0 and rows A B. Four cells are 1, seven are X and the rest are 0. Two groups are drawn, one of eight cells and one of four.

Figure 5.4.10. NS1 of the repeat detector. The cells of both don't care kinds are X.

The group of eight in rows AB=01 and 11 has B fixed at 1 and everything else changing, so its term is $B$. It takes in the row of the input value B alone, which holds three 1s and a don't care, and the row of both keys, which is all don't cares. The 2-by-2 square in rows AB=00 and 01, columns PS1,PS0=11 and 10 has PS1 fixed at 1 and A fixed at 0, and its term is $\mathrm{PS}_{1} \cdot \overline{A}$: in LastB and with key A not down, the machine stays. So $\mathrm{NS}_1 =$ $B + \mathrm{PS}_{1} \cdot \overline{A}$.

NS0 has the same shape with the two keys and the two state bits exchanged: it is 1 when the next state is LastA, code 01.

NS0 = $A + \mathrm{PS}_{0} \cdot \overline{B}$

• $A$group of eight: rows 11 and 10 (8 cells); 5 of the cells are don't care
• $\mathrm{PS}_{0} \cdot \overline{B}$2-by-2 square, wraps top and bottom: rows 10 and 00, columns 01 and 11; 2 of the cells are don't care

Karnaugh map of NS0: columns PS1,PS0, rows AB; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
AB=00	0	1	X	0
AB=01	0	0	X	0
AB=11	X	X	X	X
AB=10	1	1	X	1

Groups drawn:

1. A: group of eight in rows AB=11 and 10; 8 cells, 5 of them don't care.
2. PS0 and not B: 2-by-2 square wrapping around the top and bottom edges in rows AB=10 and 00, columns PS1,PS0=01 and 11; 4 cells, 2 of them don't care.

Description: A Karnaugh map of NS0 with columns PS1 PS0 and rows A B. Four cells are 1, seven are X and the rest are 0. Two groups are drawn, one of eight cells and one of four.

Figure 5.4.11. NS0 of the repeat detector.

The group of eight in rows AB=11 and 10 has A fixed at 1, and the 2-by-2 square wrapping around the top and bottom edges in rows AB=10 and 00, columns PS1,PS0=01 and 11 has PS0 fixed at 1 and B at 0. So $\mathrm{NS}_0 =$ $A + \mathrm{PS}_{0} \cdot \overline{B}$.

Out is 1 in LastA with key A down and in LastB with key B down. Each of those two cells has don't cares around it, so each becomes a group of four.

Out = $\mathrm{PS}_{0} \cdot A + \mathrm{PS}_{1} \cdot B$

• $\mathrm{PS}_{0} \cdot A$2-by-2 square: rows 11 and 10, columns 01 and 11; 3 of the cells are don't care
• $\mathrm{PS}_{1} \cdot B$2-by-2 square: rows 01 and 11, columns 11 and 10; 3 of the cells are don't care

Karnaugh map of Out: columns PS1,PS0, rows AB; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
AB=00	0	0	X	0
AB=01	0	0	X	1
AB=11	X	X	X	X
AB=10	0	1	X	0

Groups drawn:

1. PS0 and A: 2-by-2 square in rows AB=11 and 10, columns PS1,PS0=01 and 11; 4 cells, 3 of them don't care.
2. PS1 and B: 2-by-2 square in rows AB=01 and 11, columns PS1,PS0=11 and 10; 4 cells, 3 of them don't care.

Description: A Karnaugh map of Out with columns PS1 PS0 and rows A B. Two cells are 1, seven are X and the rest are 0. Two groups of four cells are drawn.

Figure 5.4.12. Out of the repeat detector.

The 2-by-2 square in rows AB=11 and 10, columns PS1,PS0=01 and 11 has PS0 and A fixed at 1, and the 2-by-2 square in rows AB=01 and 11, columns PS1,PS0=11 and 10 has PS1 and B fixed at 1, so $\mathrm{Out} =$ $\mathrm{PS}_{0} \cdot A + \mathrm{PS}_{1} \cdot B$. These are minimal forms for the codes 00, 01 and 10. Other codes would give other equations.

The unused code. Substitute PS1 = PS0 = 1 into the three equations. A module that implements these three equations, run by a testbench that first checks all nine rows of the table against the diagram and then tries the unused code, gives the values below.

With no key down, the next code is 11, the unused code itself, so the circuit stays there for as long as no key is pressed. With key A down, the next code is 01 and Out is 1. With key B down, the next code is 10 and Out is 1. So the first press takes it out of the unused code, with a pulse on Out that no repeated key caused. Only a fault could put the machine there, and this is what the don't cares chose to do about it.

Tags: ChallengeFinite state machinesKarnaugh mapsTruth tables

Exercise 5.4.5

Design a machine with no inputs and one output. After reset it outputs the five bits 1, 1, 0, 1, 0, one per clock cycle, and then repeats them forever. Draw the state diagram, and say how many state bits it needs, how many rows its truth table has, and how many K-maps you would need to implement it.

Hint

A machine with no inputs can only depend on its own state. How many different situations must it tell apart? Two cycles that output the same bit are not necessarily in the same state: ask what comes next.

Solution

A machine with no inputs has nothing to react to, so each state has exactly one arrow leaving it, and the state alone decides the output. Writing the output inside each circle is natural here, which is the Moore style that Section 5.2 mentioned. It is not the only correct answer: a ring of five states with the same output written on the arrow that leaves each state is a Mealy machine with the same states and the same counts.

Two cycles can share a state only if the same sequence of bits follows both of them. The first and second bit are both 1 but are followed by 1, 0, 1, 0 and by 0, 1, 0, 1, so they are different states. Every position in the cycle is followed by a different sequence, so the machine needs five states, one for each bit, joined in a ring.

Description: State diagram with five circles B0 to B4 joined in a ring by arrows that go from each circle to the next and from B4 back to B0. The output written in the circles is 1, 1, 0, 1 and 0 in that order. A starting arrow enters B0.

Figure 5.4.13. The sequence generator: five states in a ring, with the output written inside each state.

Five states need three state bits. There are no inputs, so the truth table has $2^3 = 8$ rows, three of which are don't cares because only five codes are used. It has three next-state bits and one output, so four K-maps.

Encoded truth table of ch05/s04-sequence: present-state bits PS2, PS1, PS0 and inputs (none) on the left, NS2, NS1, NS0, Out on the right; 8 rows in ascending binary order, PS2 most significant; X means don't care (unused state codes and impossible inputs)

State	$\mathrm{PS}_{2}$	$\mathrm{PS}_{1}$	$\mathrm{PS}_{0}$	$\mathrm{NS}_{2}$	$\mathrm{NS}_{1}$	$\mathrm{NS}_{0}$	$\mathrm{Out}$
B0	0	0	0	0	0	1	1
B1	0	0	1	0	1	0	1
B2	0	1	0	0	1	1	0
B3	0	1	1	1	0	0	1
B4	1	0	0	0	0	0	0
unused	1	0	1	X	X	X	X
unused	1	1	0	X	X	X	X
unused	1	1	1	X	X	X	X

Tags: ChallengeFinite state machinesSequential logic