ECE 462 (Spring 2005) - Homework 7 

Posted March 16
Due in class on March 30 (extended till April 1)
	  

Grading policy

	Answers to only a subset of the questions will be graded for
	correctness of the answer and the procedure. Credit will be
        granted for attempting the other questions.


Readings: Two handout on sequential machines (see links under
	  lectures 20 and 23 on Lecture Summary page).
	  Handout on Binary Decision Diagrams (to be posted
	  under lecture 22).

Problem numbers below refer to the textbook by McCluskey.

(A) Reduced BDD for the function f(w,x,y) = wx + xy + wy using:

    (i) the ordering w < x < y
    (ii) the ordering y < w < x

(B) Table 9.2-4(b) on page 393 specifies a Mealy machine. 
    The states are named A, B, C and D. (In the table, ignore
    the number written to the left in brackets such as [1]).

    (i) Draw the state transition diagram for this machine.
    (ii) Draw the state transition diagraph for the equivalent Moore
         machine.
    (iii) Convert the Moore machine above to a Mealy machine (following
	  the procedure discussed in class). Do you get the same
	  machine as in (i) above?
 
(C) Consider the Mealy machine specified by the state table
in Table P9.3(a) on page 419. Note that the machine is specified
using two tables, one for next state, and another for output.
Minimize the number of states, and determine the table for the
reduced machine.

(D)Determine whether either of the machines below is contained in the
    other machine. Determine whether the two machines are equivalent.
    (For a direct sum, and then determine equivalence classes of the
     states, to help determine the answer.)

               0        1
          ------------------
         A   B,0       C,0
         B   C,1       B,0
         C   B,1       C,0

               0        1
          ------------------
         D   F,1       D,0
         E   F,0       D,0
         F   D,1       F,0
         G   D,0       F,0


(E) Find a synchronizing sequence for the machine below, if such a sequence
    exists.

               0        1
          ------------------
         A   B,0       C,0
         B   A,1       B,0
         C   A,1       C,1
	 D   C,0       B,1         

(F) Find a preset distinguishing sequence for machine below, if such a sequence
    exists.
	
               0        1
          ------------------
         A   B,0       C,0
         B   A,1       B,0
         C   A,0       C,1
	 D   C,1       B,1         
	 E   E,0       E,1

(G) Determine an adaptive experiment for the machine in part (F)

(H) Find a homing sequence for the machine below. 

               0        1
          ------------------
         A   B,0       C,0
         B   A,1       B,0
         C   A,1       C,1
	 D   C,1       B,1         
	 E   E,0       E,1