CSEE 3827: Fundamentals of Computer Systems - Problem Set #3: Vending machine controller
Problem Set #3
CSEE 3827: Fundamentals of Computer Systems
1
Directions and References
• Please write neatly and enter your solutions in the space provided. If you need additional space, please insert an additional page into the PDF immediately after the problem in question.
• You are encouraged to show your work, so we can see how you arrived at a solution. • The behavior of a J-K flip-flop is below:
J K 𝑄𝑛𝑒𝑥𝑡
0 0 𝑄𝑐𝑢𝑟𝑟 hold
0 1 1 0 1 1
0 reset
1 set 𝑄𝑐𝑢𝑟𝑟 toggle
2
1. Re-implement the vending machine controller from lecture, but extend it to give change by releasing
nickels when appropriate.
The inputs are:
• 𝑁, 𝐷: single bit inputs indicating whether a nickel or a dime (but never both) have been inserted • 𝐶𝐿𝐾, 𝑅𝑆𝑇: the usual clock and active low reset inputs
The outputs are:
-
𝑜𝑝𝑒𝑛: a single bit, set to 1 for one clock cycle to vend an item
-
𝑟𝑒𝑡𝑢𝑟𝑛: a single bit, set to 1 for one cycle to return a nickel (a nickel can only be returned when an item is vended)
As before, the machine accept only nickels and dimes, and vends a single item whose price is 15¢. This new machine should accept and credit all coins entered, including while vending or returning change. Note: the item and change should be produced as soon as possible, and this depends on the type of finite state machine used.
(a) Draw a state transition diagram for a Moore implementation of this machine. Your design should minimize the number of states.
3
(b) Using the minimum necessary number of D flip-flops, set the state encoding and derive SoP expressions for the next state and output logic.
4
2. Now design a Mealy implementation of the vending machine controller specified in Problem 1.
(a) Draw a state transition diagram for the Mealy implementation, again minimizing the number of states.
(b) Using the minimum necessary number of D flip-flops, set the state encoding and derive SoP expressions for the next state and output logic.
5
(c) With respect to timing, how do the Moore and Mealy machine implementations of the vending machine differ?
6
3. Consider the finite state machine below:
𝑥
𝑒𝑣𝑒𝑛
𝑥
𝑥
𝑥
𝑒𝑣𝑒𝑛
-
(a) Complete the timing diagram, assuming zero gate delay in any logic and rising-edge triggered flip-flops.
𝐶𝐿𝐾
𝑅𝑆𝑇 𝑥
𝑒𝑣𝑒𝑛
-
(b) Assume the machine is to be implemented using flip-flops with synchronous reset whose setup time is 0.5ns and propagation delay from clock to 𝑄 is 0.5ns. Assuming there is no clock skew, what is the range of safe critical paths for the next state logic, such that the machine will work at clock frequencies up to 300MHz?
7
4. In this problem, you will design a 4-bit 2’s complement negator (without overflow detection). Every four cycles, the machine will take in 4 1-bit values 𝑥0, 𝑥1, 𝑥2, 𝑥3 (in order from LSB to MSB, where 𝑥0 is input for cycle 𝑛, 𝑥1 is input for cycle 𝑛 + 1, etc.) and produce 4 1-bit values 𝑦0, 𝑦1, 𝑦2, 𝑦3 (in order from LSB to MSB, where 𝑦0 is output for cycle 𝑛, 𝑦1 is output for cycle 𝑛 + 1, etc.) such that 𝑦3:0 = −𝑥3:0. Every four cycles after reset, a new four bit value begins. Let the input bit be 𝑥 and the output bit be 𝑦.
(a) Draw a transition diagram for the Mealy implementation, minimizing the number of states.
(b) Using the minimum necessary number of D flip-flops, set the state encoding and derive SoP expressions for the next state and output logic.
8
5. In this problem, you will design a finite state machine that detects the pattern “010”. The input is a single bit 𝑥 and the output is a single bit 𝑦, where 𝑦𝑖 = 1 if and only if 𝑥𝑖−3:𝑖−1 = 010.
(a) Draw a transition diagram for the Moore implementation, minimizing the number of states.
(b) Using the minimum necessary number of JK flip-flops, set the state encoding and derive SoP expressions for the next state and output logic.
9
6. Inthisproblem,youwilldesignafinitestatemachinethatdetectsifthecurrentrunningvalueisdivisible by 3. The input is a single bit 𝑥, and each 𝑥 input at a given clock cycle is the new LSB of the current running value. The output is a single bit 𝑦, which is 1 if and only if the current running value (including the input 𝑥 in the current clock cycle) is divisible by 3.
(a) Draw a transition diagram for the Mealy implementation, minimizing the number of states.
(b) Using the minimum necessary number of JK flip-flops, set the state encoding and derive SoP expressions for the next state and output logic.
10
7. Consider the circuit below. Which latch functionalities does it have? Which latch functionalities does it not have? Why? Show your work. (Note: it is not necessarily guaranteed that 𝑋 = 𝑌, so 𝑋 and 𝑌 are used instead of 𝑄 and 𝑄.) You can assume that 𝑋 = 𝑌 initially, however.
𝐴
𝑋
𝑌
𝐵
11
