Homework 2

Homework 2
Boolean Algebra and Digital Logic

Due: Tuesday, November 6, 2007 at 9am

Outcomes

After successfully completing this assignment, you will be able to...

construct a logic diagram from a truth table, and vice versa
minimize a circuit using a Karnaugh map
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
draw a state diagram for a simple finite state machine

Before Starting

Read Chapter 3.

Format and Submission of Assignment

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

Problems (10 points each)

Use a Karnaugh map to minimize the function F on 3 variables given by:
```
F(x,y,z) = x'y + xyz' + xyz
```
Make sure your Karnaugh map is clearly labelled.

Minimize the function F from problem 1, but this time do it by applying the postulates and theorems of Boolean Algebra (the postulates (P1 through P6) and theorems (Th1 through Th16) are listed on pages 44 and 45 of this pdf file). 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(x,y,z) = x'y + xyz' + xyz                 given
F(x,y,z) = y(x' + xz') + xyz                P4 (distributive law)
.                                           .
.                                           .
.                                           .                                .

The truth table for a Boolean expression F is shown below. Write the Boolean expression for F in sum-of-products form.

   x  y  z | F
   -----------
   0  0  0 | 0
   0  0  1 | 1
   0  1  0 | 1
   0  1  1 | 0
   1  0  0 | 0
   1  0  1 | 1
   1  1  0 | 1
   1  1  1 | 0

Do problem 3.24 from the textbook.
Implement a 4-to-1 multiplexer using only 2-to-1 multiplexers. (Hint: you will need three 2-to-1 multiplexers. The outputs of two of the multiplexers will become the inputs to the third multiplexer.)
Do problem 3.26 from the textbook.
Figure 3.21 on page 69 in the textbook depicts a 4x3 memory. Describe what additional components would need to be added if this memory were to be expanded to accomodate 8 3-bit words (an 8x3 memory). Be specific - exactly how many additional components would be required, and what would they be used for? (The components in the diagram are and-gates, or-gates, and D-latches).
Given a memory of 2048 bytes consisting of several 64x8 RAM chips, and assuming byte-addressable memory, which of the following configurations indicates the correct way to use the address bits? Explain your answer.
- 10-bit address: 2 bits for chip select, 8 bits for the address on a chip
- 64-bit address: 16 bits for chip select, 48 bits for the address on a chip
- 11-bit address: 6 bits for chip select, 5 bits for the address on a chip
- 6-bit address: 1 bits for chip select, 5 bits for the address on a chip
- 11-bit address: 5 bits for chip select, 6 bits for the address on a chip
- 10-bit address: 4 bits for chip select, 6 bits for the address on a chip
- 64-bit address: 8 bits for chip select, 56 bits for the address on a chip
Design a circuit that compares two 2-bit integers, calculating an output of 1 when the first integer is less than the second integer, and calculating an output of 0 otherwise. Design your circuit in four steps:
- a). generate a truth table (your truth table will have four input columns and one output column)
- b). write the Boolean expression for the function in sum-of-products form
- c). minimize the function using a Karnaugh map, and write the Boolean expression for the minimized function in sum-of-products form. Make sure your Karnaugh map is clearly labelled.
- d). draw the logic circuit for the minimized function
Do problem 3.43 from the textbook (both parts, a and b).