Computer Organization: Problem Set 0

Due Monday, October 7


Instructions


The Problems Themselves

  1. Consider the 3-bit "equality" function: given three, single-bit inputs, it returns true (1) if all three bits are identical (all 0 or all 1) and false otherwise.

    1. Write a truth table that captures the logic of the operation.

    2. Write a sum-of-products logic formula for the output.

    3. Draw a circuit diagram using fundamental logic gates (i.e., NOTs, ORs, ANDs, NORs, and NANDs) that implements the function. Try to use as few gates as possible, but limit yourself to 2-input gates.

  2. Consider this circuit:

    .

    1. What is the depth of the circuit?

    2. Do you think the circuit was derived using the sum-of-products formula? Explain.

    3. How many rows would the corresponding truth table have? Explain. (Do not write the truth table.)

    4. Write a logic formula that corresponds to the circuit.

    5. What does this circuit achieve? (Example: "it computes the majority of three 1-bit inputs".)

  3. The sum of products algorithm gives us a method for generating logic formulas from truth tables (and, therefore, circuits using fundamental logic gates from truth tables). The algorithm purports to produce formulas that correspond to depth-two circuits, regardless of the size of the truth tables, but it assumes that we can use AND and OR gates of arbitrary "fan in" (meaning the gates can take as many inputs as we want). If we restrict ourselves to using two-input gates only, the result of the sum of products seems less efficient - since the depth is no longer two. For example, take this depth-one circuit using a four-input OR gate:

    To achieve the same effect we might construct a depth-three circuit using three two-input ORs:

    .

    This would seem to suggest that in order to simulate an n-input OR (or AND) gate we need to use a depth n-1 circuit with n-1 OR (or AND) gates.

    Imagine we have a truth table over 8 variables where the output is true (1) half of the time. Suppose we apply the sum-of-products algorithm to the truth table to generate a logic formula.

    1. Using two input AND gates, how many AND gates total do we need to compute a single minterm? How much depth is required for that portion of the circuit (i.e, to compute a single minterm)? Explain.

    2. How many minterms will there be? Explain.

    3. Using two input OR gates - how many OR gates total do we need to compute the combined sum of all the minterms (the output of the circuit)? How much depth is required for that portion of the circuit?

      We can think of the 8 inputs as consisting of two 4-bit numbers, and imagine a slightly different table that has five output bits representing the sum of two 4-bit numbers.

       inputs     outputs     (description)
      -------------------------------------
      0000 0000    00000        0 +  0 =  0
         ...        ...
      1001 1101    10110        9 + 13 = 22
         ...        ...
      1111 1111    11110       15 + 15 = 30
    4. If we used the approach you have taken in the previous parts of this problem (for minimizing the depth of the circuit) would you say the sum of products algorithm leads to a practical circuit for computing the sum of two 4-bit numbers? Explain.

      Now imagine we scale up and wish to use the same approach to compute the sum of two 16-bit numbers.

    5. Approximately how many rows would we need for a truth table corresponding to all the possible sums of two 16-bit numbers?

    6. Does the sum of products formula help us to build a reasonable circuit for adding two 16-bit numbers? Explain.


  4. Write the following binary number in hexadecimal:

    00011100111010101011000011011110
  5. Write the following hexadecimal number in both binary and decimal. Why do I not specify whether the latter is to be signed or unsigned?

    0x4012F00D
  6. Consider the following binary number.

    10101110011010010000000000001100

    Write the number in hexadecimal. Then write it as a MIPS assembly instruction, an unsigned decimal value, and a signed two's complement decimal value. Show your work.

  7. Translate the following three machine instructions into MIPS assembly instructions.

    00000001000010010101000000100000
    
    10001110111011100000000001001000
    
    00100010101101011111111111111111
  8. Write equivalent MIPS assembly language instructions for each of the following pseudocode fragments. In each case, assume the variables are associated with registers starting with $s0 (so a is $s0, b is $s1 and so on up through h which is $s7) and any temporaries necessary should be stored starting in `$t0`. Assume a, b and c are arrays of integers and d, e, f, g and h are integers.

    1.     f = f + (e - d)
          h = (f - g) - h
    2.     d = d - 9
    3.     e = g + b[7]
    4.     c[5] = e - f
    5.     a[h+1] = a[h]
    6.     c[b[d]] = 13
  9. Show a sequence of MIPS assembly instructions (not pseudoinstructions) to place the hexadecimal value 0x77fff into register $s6, using the decimal representation of any immediate values. For each assembly instruction, show the corresponding machine code in hexadecimal notation.

  10. Given a binary number, how, if at all, can you tell whether it corresponds to a machine instruction, an unsigned integer, a signed two's-complement integer, or something else entirely? Explain.