Boolean Algebra and Digital Logic

- 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

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

- (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 F_{min}that produces the same output (i.e. is equivalent to) the function F (you should be able to determine a minimal function by inspection). - (10 points)
Start with the same function F again, as defined in Problem 2. Show how to
obtain the minimized
function F
_{min}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) . . . . . . .

- (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.

- (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
**x**or_{1}x_{0}**y**. 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._{1}y_{0}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.

- (15 points) Do problem 3.24 from the textbook.
- (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.

- 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?
- (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).

- a).
Draw a finite state machine for the 2-input Muller C-Element.