Computer Science 150 Homework Assignment 1
Spring 1997
Due: Thursday, February 5th, 5:00 pm

  1. (a) Represent the following sentences by a single Boolean equation (10pts)
    "The tape drive motor for a computer tape drive should be running iff:
    (i) the tape cassette has been inserted,
    (ii) the tape drive is in the manual mode and the motor start button has been pressed, or it is in the automatic mode and the "tape on" signal from the computer is present."

    (b) Draw a Truth Table for the function indicating when the computer tape drive should be running.(10pts)
     

  1. The Search for Extra-Terrestrial Intelligence (SETI) collects vast amounts of data from radar telescopes and compares the signals received from other planets to signals which intelligent beings might use. If a match is found between the measured signal and an ``intelligent'' pattern, then it is likely that some other life form created that signal.
  2. Your task is to construct a synchronous finite state machine (FSM) for SETI that can perform this pattern matching automatically.

    The input data to the FSM is a serial bitstream which represents the data being received from the radar telescope. That is, the input is a binary digit (0/1) which can change on every tick of the machine's clock. On the first clock cycle, the first bit from the telescope is received, then on the second clock cycle, the second bit is received, and so on.

    The output of the FSM should be a single bit which indicates a pattern match. The desired pattern is 011, repeated twice; that is,  the FSM should indicate a match (1 out) any time the bitstream contains a 0, followed by a 1 on the next clock tick, which in turn is followed by a 1 on the subsequent clock cycle, then a 0 on the next cycle, followed by a 1 on the next, then finally a 1 again.

    Your boss at SETI suggests a Mealy machine be used for simplicity, although this is not required.

    Hand in the following:
    (a) A state diagram for the FSM. Assume a single state transistion will happen at each clock tick. Be sure to indicate the reset state on your diagram. (25 pts)
    (b) The state transition table corresponding to the state diagram. Try to perform some state assignment (that is, give each state some binary encoding), but don't worry about deriving the ``best'' assignment. (15 pts)

    Bonus: Your boss at SETI wants you to come up with a circuit which performs the same task which only uses one D- latch,a 2-bit shift register and no more than 6 gates (government cutbacks have drained SETI's research funds). Hint: the problem can be formulated as follows: the output should indicate a match when 011 has been seen, followed by the input from two clock cycles ago was a 0, the input from the previous clock cycle was a 1, and the current input is a 1. (10 bonus points; not required)
     

  3. NAND gates and NOR gates are simple to construct using today's digital circuit technology; XOR and EQ are more complex, but certain functions, like addition and multiplication, are best implemented using XORs.

  4.  
    (a) Show how the two-input XOR and EQ functions can be implemented using just NAND gates. You may use as many NAND gates as you wish for each of these, but minimum is better. Hand in the schematics and a truth table showing the values of each gate output in your circuit (15 pts)
    (b) Show how the two-input XOR and EQ functions can be implemented using just NOR gates. You may use as many NOR gates as you wish for each of these. Hand in the schematics and a truth table showing the values of each gate output in your circuit (15 pts)


    Newton/Pister