# Computer Organization: Problem Set 0

## Due Monday, October 7

#### Instructions

• Work entirely on your own.
• Your solution should be typed and printed with plenty of spacing within and between problems in black ink on otherwise blank paper that is stapled (assuming it is more than one page).
• You may hand write portions of your solution (e.g., circuit diagrams) where appropriate, but in those cases please take care to make your solutions are legible.
• For problems that ask you to produce long sequences of bits (sequences of more than four bits), type the result in groups of four bits, with spaces between.
• For problems that ask you to write MIPS assembly language, only use those instructions which we have discussed in class. (If you are not sure whether you should use a particular instruction, just ask the instructor.)
• Where appropriate, show your work. For problems that ask you to indicate the unsigned or signed decimal value represented by a sequence of bits you may use a calculator or a computer program to assist with the conversion. However, you should show your work, indicating which powers of two are involved in your calculations.

#### 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``
4. ``    c = 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.