COS 111 Assignment 4
Spring 2005
Due 03-02-2005

1. Describe the behavior of the following circuit with the help of a 
   truth table.
               ___ 1
        R ----|   \      
              |NAND)o--+-- Q
           ---|___/    |
           \            \
            \            \
             \_______     \
                     \     \
               ___2   \     \
        S ----|   \    |     \
              |NAND)o--+---Q' \
           ---|___/            |
           |___________________|
                                              

  The inputs to NAND 1 are the external input 'R' and the feedback 
  from Q'. Similarly the inputs to NAND 2 are the external input 'S' and
  the feedback from Q.

  As must be obvious from their names, Q and Q' should always be the 
  complement of each other i.e. under no circumstances should the two 
  have the same value.

  In your truth table, if for any combination of R & S, the values of Q
  and Q' become the same, then you should state that such a combination(s)
  of R & S is/are illegal.

2. I am given an arbitrarily large binary string (i.e. a string of 1's 
   and 0's). I would like to know if the string has an odd number of 1's
   or not. Design a circuit for doing this. Give the truth table and
   draw the circuit.
   Assume that you are provided with some means to get the 
   "next bit" in the string and you process the string from the right to 
   the left. 

   (Hint: Use a memory element to record "information" (you decide what
    to record) about the bits scanned thus far. Use this information in
    combination with the "next bit" to update the memory element.)

    Clearly state your assumptions, if any.

3. The truth table for a half-subtractor (HS) is as follows:
   
   Inputs: X and Y
   Outputs: B and D (borrow and difference)
   Truth table for X-Y


    X  Y  ||  B  D
    ---------------
    0  0  ||  0  0
    0  1  ||  1  1
    1  0  ||  0  1
    1  1  ||  0  0


    Give the Boolean expressions for B and D. 

    
    The truth table for a full-subtractor (FS) is as follows:
    Inputs: Xi, Yi and Bi.
    Outputs: Di and B(i+1)

    Xi  Yi  Bi  ||  Di  B(i+1)
    --------------------------
    0    0   0  ||  0    0
    0    0   1  ||  1    1
    0    1   0  ||  1    1
    0    1   1  ||  0    1
    1    0   0  ||  1    0 
    1    0   1  ||  0    0
    1    1   0  ||  0    0
    1    1   1  ||  1    1

             Xi  Yi 
            _|___|___
           |         |
  B(i+1)<--|   FS    |<---Bi
           |_________|
                |
                Di

    First, understand how the circuit works by trying out various binary
    subtraction examples.
    The full-subtractor is used to find the difference of the ith bit
    when subtracting 2 binary numbers. The resulting borrow is passed
    on as the input borrow for the (i+1)th bit.


    Now, your task is two-fold.
    1. Show how to construct a FS from 2 HS and an OR gate.
    2. Show how to construct a 4-bit subtractor using full-subtractors.
       Show the inputs and outputs clearly.