Question

Design a FSM for a Vending Machine

In this task, you will design a FSM for a simple (albeit strange) vending machine of office supplies. The vending machine sells three possible items, each at a different cost:

Item	Cost
Pencil	10 cents
Eraser	20 cents
Pen	30 cents

The vending machines accepts nickels (worth 5 cents), dimes (worth 10 cents), and quarters (worth 25 cents). Physically, it is only possible to insert a single coin at a time. The vending machine features a large button labeled “DONE”, which, when pressed, will dispense the most expensive item which can be purchased with the input money. For example, if a dime and two nickels had been entered (totalling 20 cents), then it would dispense an eraser upon pressing “DONE”. Once an item is dispensed, the vending machine returns to an initial state wherein it shows that no money has been inserted.

To help simplify things, the vending machine does not provide any change. This means that any additional money provided will be lost. For example, if a quarter had been entered and then “DONE” pressed, the vending machine would dispense an eraser (because this is the most expensive item which can be purchased with 25 cents), and then the vending machine would return to the point where it shows that no money has been entered. As another example, if two quarters had been entered, then upon pressing “DONE”, it would dispense a pen (the most expensive item purchasable with 50 cents), and then the vending machine would return to the point where it shows that no money has been entered.

While there are different ways to model these different parameters as inputs, your FSM should deal with the following inputs:

Input	Description
K	Set to 1 if a nickel has been entered, else 0
D	Set to 1 if a dime has been entered, else 0
Q	Set to 1 if a quarter has been entered, else 0
E	Set to 1 if “DONE” has been pressed, else 0

In addition to the above inputs, you’ll also need to specify what the current state is, which should be indicated with inputs C0 through CN, where N is the position of the greatest possible bit in your state encoding. For example, if you needed eight states in your FSM, then you’d have inputs C0, C1, and C2, as eight states can be uniquely encoded using three bits.

Similarly to the inputs, the output parameters can be modeled in different ways. However, for the sake of consistency across different solutions, your FSM should deal only with the following outputs:

Output	Description
DPENCIL	Short for “Dispense Pencil”. Set to 1 if we should dispense a pencil, else 0.
DERASER	Short for “Dispense Eraser”. Set to 1 if we should dispense an eraser, else 0.
DPEN	Short for “Dispense Pen”. Set to 1 if we should dispense a pen, else 0.

In addition to the above outputs, you’ll also need to specify what the next state is, which should be indicated with outputs N0 through NM, where M is the position of the greatest possible bit in your state encoding. For example, if you needed eight states in your FSM, then you’d have inputs N0, N1, and N2, as eight states can be uniquely encoded using three bits.

This overall task is separated into a series of questions.

1. Draw the finite state machine corresponding to this task.

2. How many latches/flip-flops do you need to implement this state machine? (Hint: this corresponds to the number of bits necessary in order to encode all possible states uniquely.)

3. Draw a single truth table representing the behavior of the state machine. Be sure to label your states in binary. Your table should have inputs and outputs corresponding to the inputs and outputs described previously.

To simplify things, you may put don't cares where appoproiate in the inputs. For example, because it is physically impossible to insert more than a single coin at a time, if input K = 1 (indicating a nickel has been inserted), then inputs D and Q can be safely labeled as don't cares, as implicitly they should always be 0 (and in reality we ignore their values entirely in this situation). With this setup, we can cut down on the number of repeated rows; instead of having two rows which differ in only whether or not Q is set, we can have a single row where Q = X.

__________________________________________________________________________________________________________________

The following are a series of hints which may be of use:

---You may assume only one coin is ever entered at a time. For example, this means that if D = 1 (indicating a dime was entered), then it is guaranteed that K = 0 and Q = 0 (indicating a nickel and a quarter were not entered, respectively). Similarly, you don't need to worry about the user inputting multiples of the same coin at once (e.g., two quarters at once), which does not have a possible encoding in this setup. The practical advantage of this assumption is that transitions will only ever depend on one input at a time; you'll never need a transition which corresponds to the user inputting a combination of coins.

---You may assume that “DONE” is pressed only after all coins have been entered. Similar to the previous assumption, this means you don't need to worry about a case where the user inputs a coin while simultaneously pressing “DONE”. For example, if E = 1, then it is guaranteed that K = 0(meaning no nickels were inserted).

---You may assume that when “DONE” is pressed, the user will provide no more input until the vending machine has finished dispensing the most expensive item purchasable with the input money. This means that until the vending machine returns to the original state it started in with no input money, K = 0, D = 0, Q = 0, and E = 0.

---You may assume that the vending machine does not provide any change, and gives no indication to the user when money has simply been eaten. As with the example before, this means that if more money was provided than needed (e.g., providing 25 cents to purchase a 20 cent eraser), then the additional money simply disappears. Similarly, if the user does not provide enough money to purchase anything (e.g., inserting only a nickel and subsequently pressing “DONE”), then no items should be dispensed, but the vending machine will still return to the initial state.

---To help keep your diagrams clean, you need only indicate outputs when the output would be 1. For example, if in one particular state a pencil should be dispensed, then in this particular state DPENCIL should be indicated. In all other states, simply omitting DPENCIL is equivalent to outputting that DPENCIL = 0.

---As for what your states in this vending machine indicate, probably the simplest approach is to have a distinct state for each amount of currency which can be deposited. At the very least, this means having states corresponding to 5 cents deposited, 10 cents deposited, 15 cents deposited, and so on. While your vending machine will likely need more states than this, the bulk of the states work in this fashion.

---Technically, a user can input an arbitrarily large amount of money into the machine. However, you don't need to worry about this too much, as the vending machine only dispenses one item at a time, and provides no change. As such, inputting 30 cents (enough to buy a pen, the most expensive item), is no different than inputting 35 cents or more.

Answer 1

The following is the mealy FSM of the system

The rectangular boxes represent the various states.

The elipses represent the outputs (since this is a mealy implementation, the outputs depend on the transition and not the state)

Method:

Start with the worst case scenario, that’s a lousy customer who wants to buy a pen in nickels.

So we get 5, 10, 15, 20, 25, 30 cents received as the various states. Any value more than 30 cents is simply equivalent to 30. 10 cents is 10 cents. Doesn’t matter if it’s two nickels or a dime. So these are all the states we need. No more.

Now just see where adding a dime or quarter to any value gets you and add those transitions.

No of flops required: 3 (cuz 7 states) and 2^3=8>7

               

Now that’s a big table!

Draw it taking reference from the diagram