103.

[Top] [Next] [Prev]

1. (State Reduction) Use the implication chart method to reduce the 4-bit string recognizer state diagram of Figure 9.2.

2. (State Reduction) Given the state diagram in Figure Ex9.2, obtain an equivalent reduced state diagram containing a minimum number of states.

You may use row matching or implication charts. Put your final answer in the form of a state diagram rather than a state table. Make it clear which states have been combined.

3. (State Reduction) Given the state diagram in Figure Ex9.3, determine which states should be combined to determine the reduced state diagram. You may use row matching or implication charts.

4. (State Reduction) Given the state diagram in Figure Ex9.4, draw the fully reduced state diagram. State succinctly what strings cause the recognizer to output a 1.

5. (State Reduction) Starting with the state diagram of Figure Ex9.5, use the implication chart method to find the minimum state diagram.

Which of the original states are combined?

6. (State Assignment) Given the state diagram in Figure Ex9.6, implement a state assignment using the following techniques:

Minimum bit change heuristic

State assignment guidelines Show your assignment in a state map. Explain the rationale for your state assignment.

7. (State Assignment) Given the state diagram in Figure Ex9.7, select a good state assignment, justifying your answer in terms of the state assignment guidelines.

8. (State Assignment) One method for state assignment is to exhaustively enumerate all the possible state assignments. Given the traffic light controller symbolic state table of Figure 9.20, use espresso to evaluate all 24 possible 2-bit encodings of the states. Using literal count as your metric, what is the optimal encoding?

9. (State Assignment) Using a logic minimization tool like espresso, try some random encodings of the traffic light controller that are nondense. That is, map the four states into eight (3 bits) or sixteen (4 bits) possible states. How do they compare in terms of literal count to the encodings found in the previous question? How many state assignments are possible in these two nondense encodings? Derive a formula for it if you can.

10. (State Assignment) Given the next-state function of the finite state machine shown in Figure Ex9.10, use the implication chart method to find the most reduced state diagram.

11. (State Partitioning) Show how to partition the next-state functions of Figure Ex9.10, P3, P2, P1, P0, into two groups, each of which depends on only three of the four possible current state bits, Q3, Q2, Q1, Q0.

12. (State Partitioning) Given a 3-bit, eight-state Gray code up/down counter (similar to the state machine in Figure 9.48), show how the state diagram can be partitioned into two communicating finite state machines with five states each, including idle states.

13. (State Partitioning) Given the state diagram in Figure Ex9.13, partition the state machine into two communicating finite state machines, one containing the states S0, S1, S2, S3, and the other containing S4, S5, S6.

14. (State Partitioning) Figure Ex9.14 gives a state diagram with nine states.

Show how to partition the state diagram into three communicating state machines, consisting of the state groups S0, S1, S2; S3, S4, S5; and S6, S7, S8.

15. (State Partitioning) The partitioning rules presented in Figure 9.47 describe only the transformations on states and transition conditions. Outputs are not considered.

Describe how the partitioning rules should be modified to handle Mealy outputs. How are the transfers into the idle states affected?

Describe how the partitioning rules should be modified to handle Moore outputs. How might the outputs from the partitioned machines be combined?

16. (Flip-Flop Choice) Given the state diagram in Figure Ex9.16 and the state assignment S0 = 000, S1 = 001, S2 = 010, S3 = 011, S4 = 100, and S5 = 101, do the following:

Write the encoded state table, and derive the minimized Boolean equations for implementing the next-state and output functions. Assume the state registers are implemented with D flip-flops.

Repeat the above, but this time using J-K flip-flops.

17. (Flip-Flop Choice) Given the state diagram in Figure Ex9.17 and the state assignment A = 000, B = 001, C = 011, D = 111, E = 101, implement the state machine using a minimum number of gates and J-K flip-flops. You may assume that an external RESET signal places the machine in state A (000).

18. (Design Process) Implement the following finite state machine description using a minimum number of states and a good state assignment, assuming D flip-flops are used for the state registers. The machine has a single input X, a single output Z, and will assert Z = 1 for every input sequence ending in the string 0010 or 100.

19. (Design Process) Your task is to implement a finite state machine with toggle flip-flops given the following state diagram. The finite state machine is actually a complex Gray code counter. The counter has two control inputs, I1 and I0, which determine the next state. The counter's functional specification is as follows. When I1 I0 = 00, it is a Gray code up-counter. When I1 I0 = 01, it is a Gray code down-counter. When I1 I0 = 10, it is a Gray code count by two. Finally, when I1 I0 = 11, the counter holds it current state. The state diagram is shown in Figure Ex9.19.

Complete a state transition table, including the next-state bits (Q1 and Q0) and the needed inputs to the two toggle state flip-flops T1 and T0 to obtain that next state.

Produce the four-variable K-maps for the next-state functions. Obtain the minimized two-level implementation.

Draw an implementation schematic, using a minimum number of inverters and two-input NAND, NOR, XOR, and XNOR gates. Assume that complements are not available.

20. (Design Process) Design a Mealy finite state machine with input X and output Z. The output Z should be asserted for one clock cycle whenever the sequence 0111 or 1000 has been input on X. The patterns may overlap. For example, X = 0000111000 should generate the output stream Y = 0000001001.

Complete the state diagram for the sequence detector, without concern for state minimization.

Complete the state table for the state diagram derived in part (a).

Use row matching or implication charts to minimize the state table derived in part (b).

Use the state assignment guidelines to obtain a good state assignment for the reduced state machine of part (c). Justify your method in terms of the high-, medium-, and low-priority assignment guidelines.

Implement your encoded, reduced state table using D flip-flops.

Implement your encoded, reduced state table using T flip-flops.

Implement your encoded, reduced state table using J-K flip-flops.

[Top] [Next] [Prev]

---

This file last updated on 07/15/96 at 06:40:56.
[e-mail];