CSE370 Assignment 8

Distributed: 12 May 2000
Due: 22 May 2000

Reading:

1. Katz, Chapter 8 (pp. 402-432).
2. Katz, Chapter 9 (pp. 449-470).
3. Katz, Chapter 10 (pp. 496-508).

Exercises:

1. Suppose you are told that a Mealy machine is implemented with five flip-flops, four inputs, and four asynchronous outputs. Consider the complete state diagram for this machine (that is, there are no don't cares). Answer the following questions:
   (a) What are the minimum and maximum numbers of states in the state diagram?
   (b) What are the minimum and maximum numbers of transitions starting at a particular state?
   (c) What are the minimum and maximum numbers of transitions ending at a particular state?
   (d) What are the minimum and maximum numbers of different binary patters that can be asserted on the outputs?
2. Suppose you are told that a Moore machine also has five flip-flops, four inputs, and four outputs. Answer the same set of questions as the previous problem.
3. Katz exercise 8.11 (note that the problem states that negative-edge triggered flip-flops should be used).
4. Katz exercise 8.17.
5. Katz exercise 8.23.
6. Implement a state machine with a single input (X) and two outputs (Z and V). This state machine will "unstuff" a stream of bits. We "stuff" a stream of bits when we do not want a particular pattern of bits to ever occur in the stream. For example, if we do not want to see three or more ones in a row, we would stuff an extra zero after every two consecutive ones (e.g., 0011011100100 would become 001100110100100). Your state machine is to take such a "stuffed" stream as input (X) and produce the original "unstuffed" version (Z). Since the unstuffed stream will potentially have less bits thean the stuffed stream, a second output is added (V) so that the state machine can signal when a bit is "valid", that is, it is to be considered part of the output stream. When V is low, Z is ignored.
   (a) Draw a Moore machine state diagram for this FSM.
   (b) Create a Verilog module that implements your FSM and turn in your simulation for the example above (use $display statements that include good explanatory text). Be sure to identify important events on your printout (e.g., when an input zero is removed in the output stream).
   (c) Synthesize logic for your FSM and map it to the 16R6 PAL of Fig 10.18 on page 513 (pal10_18.pdf or pal10_18.gif). Describe why you chose the particular state encoding you used.

Rationale:

• To gain an understanding of how state machines are specified in both state diagrams and hardware description languages.
• To gain familiarity with the timing of finite-state-machines.
• To learn how to implement a state machine using programmable logic devices.