## Homework 2 Boolean Algebra and Digital Logic

### Outcomes

After successfully completing this assignment, you will be able to...
• construct a logic diagram from a truth table, and vice versa
• explain the difference between combinational and sequential circuits
• show how logic gates are combined to form a simple ALU
• show how logic gates are combined to form a simple memory
• demonstrate how direct and set-associative cache schemes work
• draw a state diagram for a simple finite state machine

### Format and Submission of Assignment

The solution for this assignment must be submitted as hard-copy at the beginning of class (9am) on November 9. All papers must be stapled together, and your name and login name must appear at the top of every sheet. Handwriting must be legible - if we can't read it, the grade is zero.

### Problems

1. (10 points) Draw the truth table for the circuit pictured here:

2. (10 points) A function F on 3 variables is given by:
```F(a,b,c) = a'b'c + a'bc + abc + abc'
```
This function can be minimized to two terms. Determine a minimal function Fmin that produces the same output (i.e. is equivalent to) the function F (you should be able to determine a minimal function by inspection).

3. (10 points) Start with the same function F again, as defined in Problem 2. Show how to obtain the minimized function Fmin by applying the postulates and theorems of Boolean Algebra (the postulates (P1 through P6) and theorems (Th1 through Th16) are listed on pages 2 and 3 of this .pdf file; the numbers on the bottom of the pages are 44 and 45). Here are the first couple of steps to get you started. Don't combine any steps (each step should follow from a single application of one of the postulates or theorems).
```           step                             reason
----                             ------

F(a,b,c) = a'b'c + a'bc + abc + abc'        given
F(a,b,c) = a'(b'c + bc) + abc + abc'        P4 (distributive law)
.                                           .
.                                           .
.                                           .                                .
```

4. (10 points) In class we showed that AND and NOT are functionally complete. We then showed that NAND is also functionally complete, by designing the functions AND and NOT using only NAND gates.

Draw a logic diagram for a circuit that computes A OR B. Your circuit may use only NAND gates.

5. (10 points) In class we saw how to construct a black box representation of a 4-to-1 MUX built from three 2-to-1 MUXes. Suppose you want a MUX where you select 2 bits at a time, instead of 1 bit. For example, you might want to select either of the inputs x1x0 or y1y0. Since you're only selecting one of two inputs, you should still use only one control bit, but now instead of 1 output bit, you will have 2.

Draw a black box representation of a 2-to-1 two-bit MUX that is implemented using two 2-to-1 one-bit MUXes. Follow the conventions we used in class for representing black boxes.

6. (15 points) Do problem 3.24 from the textbook.

7. (15 points)
• a). A machine with 32-bit addresses uses a direct-mapped cache. There are 128 slots in the cache, with 32 bytes per cache line. Which bits of the 32-bit address are used for the tag? the slot? the offset?

• b). A machine with 32-bit addresses uses a set-associative cache with 8 slots per set. There are 128 slots in the cache, with 32 bytes per cache line. Which bits of the 32-bit address are used for the tag? the set number? the offset?

• c). For a machine using the set-associative cache of part (b), the following 32-bit memory address is generated (given here in hexadecimal):

4230F691

List all of the slot numbers in the cache that need to be searched in order to determine whether or not the given memory location is in the cache.

8. (20 points) The Muller C-Element is a sequential circuit that behaves as follows: the output of the circuit reflects the inputs when the states of all inputs match. The output remains in this state until the inputs all transition to the other state. Here is a characteristic table for a two-input Muller C-Element:
```      A  B  |  Q(t+)
--------------
0  0  |  0
0  1  |  Q(t)
1  0  |  Q(t)
1  1  |  1
```
• a). Draw a finite state machine for the 2-input Muller C-Element.

• b). Create the state transition table for the finite state machine in part (a).