[Top] [Next] [Prev]

Exercises

1. (Timing Methodology) In this chapter, we have encouraged you to think of implementing all state registers of a finite state machine with flip-flops that are clocked in the same way. Consider the combinations of flip-flop types in (a) to (c) and describe briefly what (if anything) could go wrong if they were used to implement an FSM state register: A positive edge-triggered D flip-flop and a negative edge--triggered D flip-flop.

A positive edge-triggered D flip-flop and a master/slave J-K flip-flop.
A negative edge-triggered D flip-flop and a master/slave J-K flip-flop.
Can you change a master/slave J-K flip-flop to behave like a positive edge-triggered device by inverting its clock input -signal?
2. (Parity Checker) Redesign the odd parity checker FSM of Section 8.1.1 to make it check for even parity (that is, assert the output whenever the input contains an even number of 1's). Show your state diagram and implement the machine using either a D or T flip-flop.

3. (Vending Machine) Reimplement the vending machine controller of Section 8.2.2 using T flip-flops.

4. (Parity Checker Subsystem) The odd parity checker of Section 8.1.1 generates a 1 whenever a bit stream of serial inputs contain an odd number of 1's. This is useful in a data communication subsystem for checking that transmitted data has been sent correctly. Data is transmitted as 8 data bits appended with a ninth parity bit. The 9-bit sequence must be in odd parity. That is, if the data bits have an odd number of 1's, the parity bit is 0. If the data bits have an even number of 1's, the parity bit is 1. You are to design a parity checker that asserts OK if the 9-bit sequence is correct in odd parity and ERROR otherwise.

Is it possible to write a state diagram with a small number of states to describe the behavior of this finite state machine? Does your state diagram need to track all possible sequences of 9 bits?

Consider implementing the subsystem using the parity checker FSM of Figure 8.4 in conjunction with a synchronous 4-bit counter like the TTL 74163. Draw a schematic using logic gates, a single flip-flop, and the counter. Draw a timing diagram including a bit sequence that leads to ERROR and one that leads to OK. Make sure you are using components with the same kind of timing behavior!

5. (Mealy Machines) Suppose you are told that a Mealy machine is implemented with three flip-flops, two inputs, and six asynchronous outputs. Consider the complete state diagram for this machine (that is, there are no don't cares). Answer the following questions:
What are the minimum and maximum numbers of states in the state diagram?
What are the minimum and maximum numbers of transition arrows starting at a particular state?
What are the minimum and maximum numbers of transition arrows that can end in a particular state?
What are the minimum and maximum numbers of different binary patterns that can be displayed on the outputs?
6. (Moore Machines) Suppose you are told that a Moore machine has five flip-flops, three inputs, and nine outputs. Answer the following questions:
What are the minimum and maximum numbers of states in the state diagram?
What are the minimum and maximum numbers of transition arrows starting at a particular state?
What are the minimum and maximum numbers of transition arrows that can end in a particular state?
What are the minimum and maximum numbers of different binary patterns that can be displayed on the outputs?
7. (Reverse Engineering) Given the Mealy machine in Figure Ex8.7, implemented with one toggle flip-flop and one D flip-flop, with single input I and single output Z, draw its complete state diagram.

8. (Reverse Engineering) Derive the complete state diagram for the finite state machine implemented in Figure Ex8.8.

9. (Reverse Engineering) Derive the state transition table for the schematic implementation of the finite state machine of Figure Ex8.9 (the next-state and output functions are implemented by a PLA structure). The machine has one input I and one output Z.

10. (Reverse Engineering) The circuit of Figure Ex8.10 is the implementation of a finite state machine. Derive its state diagram through the process of reverse engineering. The machine has two flip-flops with state bits A and B, two inputs X and Y, and the single output Z.

Start by writing the input equations to the flip-flops as a function of X, Y, A, and B. (Hint: Simplify the output from the multiplexer before you proceed!)

Using the excitation table for the J-K flip-flop, derive the functions for A+ and B+ in terms of X, Y, A, B.
Complete the state transition table for the state machine.
11. (Synchronous Mealy Machine) Section 8.4.3 describes the basic architecture of a synchronous Mealy machine. Implement the vending machine controller of Figure 8.25 as a synchronous Mealy machine and as an asynchronous Mealy machine using negative edge-triggered D flip-flops (the Moore machine implementation appears in Figure 8.15). Draw a timing diagram that shows a difference in the detailed timing behavior of the three implementations.

12. (Word Problem) Implement a two-input Mealy machine that produces a 1 at its single output when the values of the two inputs -differ at the time of the previous clock pulse. Show your state -diagram or ASM chart. Describe what each of your states is supposed to represent.

13. (Word Problem) A finite state machine has one input and one output. The output becomes 1 and remains 1 thereafter when at least two 0's and at least two 1's have occurred as inputs, regardless of the order of occurrence. Assuming this is to be implemented as a Moore machine, draw a state diagram or ASM chart for the machine. (Hint: You can do this in nine states.)

14. (Word Problem) A finite state machine has one input (X) and two outputs (Z1 and Z2). An output Z1 = 1 occurs every time the input sequence 101 is observed, provided the sequence 011 has never been seen. An output Z2 = 1 occurs every time the input 011 is observed. Note that once Z2 = 1, Z1 = 1 can never occur. Assuming the machine is to be implemented in the Mealy design style, draw the corresponding state diagram or ASM chart. (Hint: The minimum number of states is eight.)

15. (Word Problem) A Moore machine has two inputs (X1, X2) and one output (Z). Produce the state diagram or ASM chart for the machine, given the following specification. The output remains a constant value unless one of the following input sequences occurs:

The input sequence X1 X2 = 00, 11 causes the output to become 0.
The input sequence X1 X2 = 01, 11 causes the output to become 1.
The input sequence X1 X2 = 10, 11 causes the output to change value.
16. (Word Problem) A sequential circuit has one input (X) and one output (Z). Draw a Mealy state diagram or an ASM chart for each of the following cases:

The output is Z = 1 if and only if the total number of 1's received is divisible by 3 (for example, 0, 3, 6, ).
The output is Z = 1 if and only if the total number of 1's received is divisible by 3 and the total number of 0's received is an even number greater than zero (nine states are sufficient).
17. (Word Problem) A sequential circuit has two inputs and two outputs. The inputs (X1 X2) represent a 2-bit binary number, N. If the present value of N is greater than the previous value, then Z1 = 1. If the present value of N is less than the previous value, then Z2 = 1. Otherwise, Z1 and Z2 are 0.
Derive a Mealy machine state diagram. (Hint: The machine needs only five states.)
Derive a Moore machine state diagram. (Hint: The machine needs at least 11 states.)
18. (Word Problem) A Moore machine has one input and one output. The output should be 1 if the total number of 0's received at the input is odd and the total number of 1's received is an even number greater than 0. This machine can be implemented in exactly six states. Draw a complete state diagram. Indicate what each state is meant to represent.

19. (Word Problem) Two two-way streets meet at an intersection controlled by a four-way traffic light. In the east and west directions, the lights cycle from green to yellow to red. The south-facing lights do the same thing, except that they are red when the east-west lights are green or yellow, and vice versa. However, the north-facing lights are augmented with a green left turn arrow. They cycle red-green arrow-yellow arrow-green-yellow-red. Consider the following additional problem specifications:

When the green or yellow left turn arrows are illuminated, the lights in the other three directions are red.
The timings for the north-facing lights are as follows: red, 60 seconds; green arrow, 20 seconds; yellow arrow, 10 seconds; green, 45 seconds; and yellow, 15 seconds.
The timings for the other lights can be derived from specifications (a) and (b). Assume you have as many programmable timers as you need. These can be loaded with a time constant (in seconds) and assert an output when they count down to zero. Construct a chart that shows the timing behavior of the lights in each of the four directions (Y-axis). List the illuminated lights for east, west, south, and north along the Y-axis. The X-axis is calibrated in the elapsed time in seconds. Show what happens in one complete cycle of the lights. How many unique configurations of the lights are there? Draw an ASM chart, explicitly listing all input and output control signals needed to implement the traffic light system.
20. (Word Problem) Consider the following variation on the classical traffic light controller. The intersection is shown in Figure Ex8.20. A Street runs north-south, B Street runs east-west, and C Street enters the intersection from the southeast. A Street is quite busy, and it is frequently difficult for cars heading south on A to make the left turn onto either B or C. In addition, cars rarely enter the intersection from C Street. Design a traffic light state diagram for this three-way intersection to the following specifications:

There are five sets of traffic lights, facing cars coming from A north, A south, B east, B west, and C southeast, respectively.
The red, yellow, and green lights facing cars from A north are augmented with a left turn arrow that can be lit up as either green or yellow or not lit up at all.
The normal sequencing of lights facing the cars coming from A north is arrow green, arrow yellow, traffic light green, traffic light yellow, traffic light red, and repeat. In other words, the left arrow light is illuminated in every complete cycle of the lights.
However, it should be possible for traffic going from north to south on A Street to cross the intersection even when the left turn arrow is illuminated. Therefore, the traffic light green should also be illuminated while the turn arrow is lit up.
Cars traveling from south to north on A Street (and all directions on B and C Streets) must see a red light while the left turn arrow is illuminated for the traffic heading south.
A car sensor C is embedded in C Street to detect whether a car is waiting to enter the intersection from the southeast.
A timer generates a long interval signal TL and a short interval signal TS when set by an ST signal.
Red and green lights are lit up for at least a TL unit of time. Yellow lights, the green arrow, and the yellow arrow are lit up for exactly a TS unit of time.
The C Street lights cycle from red to green only if the embedded car sensor indicates that a car is waiting. The lights cycle to yellow and then red as soon as no cars are waiting. Under no circumstances is the C Street green light to be lit for longer than a TL unit of time. Draw an ASM chart for the traffic light controller. Indicate the logical conditions for remaining in the current state and for exiting it to the next state. Also, create a table that indicates precisely which lights are illuminated for each of your states.

21. (Word Problem) You are to develop a state diagram for a washing machine. The machine starts when a coin is deposited. It then sequences through the following stages: soak, wash, rinse, and spin. There is a "double wash" switch, which, if turned on, causes a second wash and rinse to occur. There is one timer-you may assume that each stage should take the same amount of time. The timer begins ticking as soon as the coin is deposited, generates a T signal at the end of the time period, and then resets itself and starts again. If the lid is raised during the spin cycle, the machine stops spinning until the lid is closed. You may assume that the timer suspends ticking while the lid is raised. Identify your inputs and outputs, and draw the ASM chart that implements this finite state machine.

22. (Word Problem) You are to design the control for an automatic candy vending machine. The candy bars inside the machine cost 25 cents, and the machine accepts nickels, dimes, and quarters only. The inputs to the control are a set of three signals that indicate what kind of coin has been deposited, as well as a reset signal. The control should generate an output signal that causes the candy to be delivered whenever the amount of money received is 25 cents or more (no change is given). Once the candy has been delivered, some external circuitry will generate a reset signal to put the control back into its initial state. Identify your inputs and outputs, and draw the ASM chart that implements this finite state machine.

23. (Word Problem) You are to design a Mealy state diagram for a digital lock. Assume that two debounced push-buttons, A and B, are available to enter the combination. An electromechanical interlock guarantees that the buttons cannot be activated simultaneously. The lock should have the following features:

The combination is A-A-B-A-B-A. If this sequence is correctly entered, an output signal is asserted that causes the lock to open.
For any state, three B pulses in a row should guarantee to reset the control to its initial state.
When any out-of-sequence use of the A push-button occurs, an output is asserted that rings a bell to warn that the lock is being tampered with. Once the lock is open, pressing either A or B will cause the lock to close without signaling an error. Draw a Mealy state diagram for this finite state machine. Indicate what each state represents and what input conditions cause state and output changes. Not everything may have been specified, so write down any assumptions you make.
24. (Word Problem) Design a state diagram to perform the following function. There are two data inputs A and B, a check input C, and an output D. The FSM takes as input two continuous, synchronous streams of 4-bit twos complement numbers in a bit-serial form with the most significant (sign) bit first. The least significant bit is marked by a 1 on the check line (C). During the time slot in which C is asserted, the output D should go to a 1 if the twos complement number on A is larger than the twos complement number on B.

Complete the timing diagram in Figure Ex8.24 to make sure you fully understand the statement of the problem.

Draw a state diagram that implements this specification using as few states as possible. (Note: It is possible to implement this machine in six or fewer states.)
25. (Word Problem) You are to design a finite state machine to control the position of a mechanical arm. Your inputs include two registers, R0 and R1, that contain the current position of the arm and the target position, respectively, encoded as 32-bit twos complement numbers. R0 is automatically updated by external logic on every clock pulse.

The machine should operate as follows. The FSM commences operation when a START pulse is asserted. If the current position is less than the target, the machine should assert a FORWARD signal. If the position is greater than the target, a REVERSE signal should be asserted. If the position is already correct, return to the initial off state. When the arm has moved seven eighths of the way to the target from its initial position, an additional SLOW output should be activated to brake the motion of the arm. You may assume that the arm moves slowly enough with respect to your FSM's clock rate that you need not worry about overshooting the target.

You will probably need additional data path objects besides registers R0 and R1. Draw a register diagram of your data path, showing the elements and how they are interconnected. Then draw the controller's state diagram, showing the high-level register transfer operations that are asserted in each state or transition (you may choose Moore or Mealy implementation, at your own discretion).

26. (Word Problem) Your task is to design the control for a sequential 4-bit multiplier. The data path is shown in Figure Ex8.26.

It consists of a 4-bit adder, a 4-bit register, and a 9-bit shift register. The latter shifts right when its Sh input is asserted (assume that 0's are entered at the left for this operation). A new value is loaded into the high-order 5 bits of the shift register when Ld is asserted. The same 5 bits are zeroed when Cl is asserted. These signals are synchronous.

As a simple example, consider the 2-bit version of the device forming the product of 112 and 102.

Draw a Mealy machine state diagram for a 4-bit multiply. The inputs are S (a multiply start signal) and M (the low-order bit of the multiplier). The outputs are the Sh, Ld, and Cl signals.

27. (Word Problem) Your task is to design the control for a newspaper vending machine to the following specification. The newspaper costs 35 cents. The vending machine accepts nickels, dimes, and quarters. The customer presses a START button and then begins entering coins. Coin sorter logic indicates to the FSM whether a nickel (N), dime (D), or quarter (Q) has been deposited. (Assume that the FSM advances from one state to the next when a coin is deposited.) If exact change is entered, a latch is released so the customer can get the paper. If the amount of money deposited exceeds 35 cents, change is given if possible. Otherwise, deposited coins are refunded to the customer.

Assume that the money just deposited is kept separated from previously accepted coins. The latter are held in a coin repository. Change is given in dimes and nickels. If one nickel is in the repository, a signal N1 is asserted. If two nickels are there, N2 is true (note: N1, N2 will both be asserted if the repository contains two or more nickels), and so on for the number of nickels and dimes in the repository. If sufficient change is available, the FSM pulses a nickel release (NR) or dime release (DR) signal to release one coin of change at a time (it would jam the machine to release more than one coin at a time).

If insufficient change is available, the coins just deposited are refunded by the FSM, asserting a refund (REF) signal. Otherwise, the deposited coins join the repository as the FSM asserts a release (REL) signal. The block diagram for the FSM is shown in Figure Ex8.27.

Consider for a moment the signals that indicate the number of nickels and dimes available to make change. What is the maximum number of nickels needed at any time? What is the maximum number of dimes needed? Understanding the answers to these questions may help to simplify your state diagram.

Complete a Mealy machine state diagram for the vending machine's control.

28. (Word Problem) You are to design the state diagram for a simple controller that turns a lamp on and off at preset times. This is a timed light switch. The finite state machine has six inputs: RESET, SetTime, SetLiteOn, SetLiteOff, RUN, and ADVANCE. The first five inputs are generated by a five-position rotary switch that advances through RESET, SetTime, SetLiteOn, SetLiteOff, and RUN (the inputs are mutually exclusive and are encountered in the specified order). The ADVANCE input is a push-button. See Figure Ex8.28(a). When you hold the ADVANCE button down (asserted), the displayed time rapidly advances through 24 hours, a minute at a time.

The typical operation of the timed light switch works as follows. It is normally in RUN mode. The lamp is turned on whenever the internal clock matches an internal register (LiteOn) that holds the time to turn the light on. The lamp is turned off whenever the internal clock matches an internal register (LiteOff) that holds the time to turn the light off.

To operate the timed light switch, you must set the current time, then the time on, and finally the time off. This is accomplished as follows. The mode switch is moved from RUN to RESET. This causes an internal timer register to be loaded with the time 08:00. Next, the mode switch is moved to the SetTime position. Whenever ADVANCE is pushed and held down, the timer register rapidly cycles through the minutes and hours. You "pulse" or single step ADVANCE as it gets close to the current time. When you move the switch to Set-LiteOn, the current value in the timer register overwrites the value in the internal clock register. At the same time, the internal timer register is reset to 08:00.

By working with the ADVANCE button, you set a new time at which the light is to be turned on. Moving the mode switch to SetLiteOff causes the LiteOn register to be overwritten by the timer register.

Using the ADVANCE button once again, you advance the timer from its last value (the "lights on" time) to the desired time to turn the lights off. Once the mode switch is set to RUN, the timed light switch goes into its running mode.

The data path associated with the timed light switch is shown in Figure Ex8.28(b). The block diagram is given in Figure Ex8.28(c).

Complete a Moore state diagram for the timed light switch -controller.

29. (Word Problem) Consider the combination lock finite state machine of Section 8.5.4. Add another input, CHANGE COMBINATION, similar to ENTER, that makes it possible to change the lock value once the door has been unlocked. Assume that the new combination is available on three switches. Draw a new state chart incorporating this change.

30. (Word Problem) Given the combination lock of Section 8.5.4, describe how you would design a combination lock with a variable number of bits in the key. Hint: How could you use a counter to assist in this? Draw a block diagram showing signals between the finite state machine and the counter. Draw a revised ASM chart incorporating your design change.

[Top] [Next] [Prev]

This file last updated on 07/14/96 at 21:28:46.
randy@cs.Berkeley.edu;