# Candy Machine Example

These notes describe (briefly) the steps to create a synchronous 15-cent candy machine that accepts nickels and dimes, and outputs candy and refunds. You can view the final circuit on CircuitVerse here.

# State diagram

We need 5 states for this machine:

- 0 cents: The start state
- 5 cents: After putting in a nickel
- 10 cents: After inserting one dime
**or**two nickels - 15 cents: Dispense one piece of candy and return to the start state.
- 20 cents: Issue a nickel refund and go to the 15 cents state.

The transitions between states are controlled by two inputs:

- D: Dime is being inserted
- N: Nickel is being inserted

**Note**: When D and N are both 0, then that means nothing is being inserted, and the machine should maintain the current state of 0, 5, or 10 cents.

**Also note**: We assume that N and D will never both be 1 — this is an *impossible input*. We also assume that no one will put money in while the candy or refunds are being dispensed. That will make for lots and lots of don’t-cares!

Here is the resulting state diagram. We implicitly assume that there is a self-looping transition on every state with zero inputs, i.e., \(\overline{D}\cdot{}\overline{N}\). The candy machine is also unlike most state machines we will see, in that it sometimes transitions when there is no input - those edges are labeled “forced”.

After deciding on the basic shape of the diagram, we must also do *state assignment*. Because there are 5 states, we need 3 bits to store the state, so each state is assigned a 3-digit binary number. We can use any numbers we like, except that **the start state should be all zeros**, to make resetting the circuit easier.

# Next state table

From the state diagram, we can build a next-state table. In this case we have 3 state bits \(Q_2, Q_1, Q_0\), two input bits \(D, N\), three next-state bits, and two outputs (for “dispense candy” and “refund”).

In the next-state table, we treat the state bits and the input bits all as inputs, so the table will have \(2^5=32\) rows.

We will have lots of *don’t-cares*, for two reasons: unreachable states which are not part of the state diagram (in this case, they are 100, 101, and 111), and impossible inputs (we assume D and N are never true at the same time, and that D and N will both be false whenever we are in states 011 or 110).

Here is the next-state table in all its glory:

Q2 | Q1 | Q0 | D | N | Q2’ | Q1’ | Q0’ | |
---|---|---|---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |

0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |

0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | |

0 | 0 | 0 | 1 | 1 | x | x | x | |

0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | |

0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |

0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |

0 | 0 | 1 | 1 | 1 | x | x | x | |

0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | |

0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | |

0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | |

0 | 1 | 0 | 1 | 1 | x | x | x | |

0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | |

0 | 1 | 1 | 0 | 1 | x | x | x | |

0 | 1 | 1 | 1 | 0 | x | x | x | |

0 | 1 | 1 | 1 | 1 | x | x | x | |

1 | 0 | 0 | 0 | 0 | x | x | x | |

1 | 0 | 0 | 0 | 1 | x | x | x | |

1 | 0 | 0 | 1 | 0 | x | x | x | |

1 | 0 | 0 | 1 | 1 | x | x | x | |

1 | 0 | 1 | 0 | 0 | x | x | x | |

1 | 0 | 1 | 0 | 1 | x | x | x | |

1 | 0 | 1 | 1 | 0 | x | x | x | |

1 | 0 | 1 | 1 | 1 | x | x | x | |

1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | |

1 | 1 | 0 | 0 | 1 | x | x | x | |

1 | 1 | 0 | 1 | 0 | x | x | x | |

1 | 1 | 0 | 1 | 1 | x | x | x | |

1 | 1 | 1 | 0 | 0 | x | x | x | |

1 | 1 | 1 | 0 | 1 | x | x | x | |

1 | 1 | 1 | 1 | 0 | x | x | x | |

1 | 1 | 1 | 1 | 1 | x | x | x |

(Note, we could/should technically include the two outputs DISPENSE and REFUND as two additional output columns in this table. But for this circuit, it’s really easy to see how to build the DISPENSE and REFUND lights with one AND gate, since they are both only enabled during a single state. So we leave them out of the state table and K-maps, for simplicity.)

# K-Maps

Now we have three next-state functions to find minimized formulas for: Q2’, Q1’, and Q0’. Naturally, we will use K-maps. Note that to create the K-map for Q2’ (for instance), we will use the first five columns of our next stable table (for Q2, Q1, Q0, D, and N), as well as the column for Q2’, but will ignore the columns for Q1’ and Q0’. We will *not* create one K-map that is trying to simultaneously handle Q2’, Q1’, and Q0’.

Because our next state table has 5 inputs (the 2 actual inputs plus the 3 state bits), we need 5-way K-maps. Review the K-maps notes for more details on these.

## Q2’

Here is the 5-way K-map for Q2’:

The formula is pretty simple here! \(Q_2' = Q_1\cdot{}D\)

## Q1’

The formula is \(Q_1' = Q_1\cdot{}\overline{Q_0} + Q_0\cdot{}N + D\)

## Q0’

The formula is \(Q_0' = Q2 + \overline{Q_1}\cdot{}Q_0\cdot\overline{N} + \overline{Q_0}\cdot{}N\)

# The circuit

The complete circuit can be found on CircuitVerse here. It may or may not also be embedded into the webpage below.