Homework Set 1
DUE: Oct 8,1999, 9:30 am

Collaboration Policy:
Unless otherwise noted, you may collaborate with other CSE467 students on the homework assignments. Do not look at homework or exam solutions from previous years. You must spend at least 15 minutes working on a problem before seeking assistance. Collaboration means that you may discuss the problems and make notes during the discussion, but you may not look at other student’s work when writing up your homework. Your homework represents your own work—the homework must show that you understand the material and have worked as an individual on every problem. You may not divide up the task of doing the problem sets in the interpretation of collaboration. You may discuss lecture material with anyone.

Late Homework Policy:
The weekly assignments are due at the beginning of class. Assignments handed in after class will incur a 10% penalty; the penalty will increase by 10% for each additional day late.

Reading:
Review Katz: Chapters 1-5

Please show all of your work, and remember, your solutions must be legible. The points for each problem are noted on the problem statement.

1.  (6 pts) Draw Karnaugh Maps (k-maps) for each of the following functions, and use the k-maps to find minimized sum-of-products boolean expressions: (a) f(X,Y,Z) = å m(0,1,2,4,6); (b) f(A,B,C,D) = å m(1,4,5,6,7,9,12,14); and (c) f(X,Y,Z) = Õ M(0,2,7).

2.  (13 pts) Chris, Jayant, Dean and Emily share a common safety vault at the HUB. The vault may be opened only in the presence of Chris and any one (or more) of the other three, or in the presence of Jayant and one (or both) of Dean and Emily. Write a truth table (a function F of the 4 variables C, J, D and E) that models the above situation. Write boolean expression for F in sum-of-products and product-of-sums forms. Draw a k-map and find a minimized sum-of-products boolean expression. Draw a logic circuit for the minimized expression using AND and OR gates. Modify the schematic to obtain a two-level circuit using only NAND gates. Repeat using only NOR gates (and inverters).

3.  (4 pts) Implement XOR and XNOR (2 input gates) using AND, OR and inverter gates. Draw the 2-variable k-maps for XOR and XNOR. (Note: Remember what these k-maps look like, so that you know what to do when you see similar arrangements again.)

4.  (9 pts) Given the following function in sum of products form (not necessarily minimized), f(W,X,Y,Z) = WZ + X’YZ’ + YW’ + W’XZ’, implement the function f using (a) an 8:1 multiplexer, (b) a 4:16 decoder and an n-input OR gate (you choose n), and (c) a 16-word ROM.

5.  (8 pts) Draw a schematic for a ROM subsystem comprising 2 independently addressable memory banks, each of size 32k × 8bits (i.e., the total ROM size is 64kB, partitioned into 2 banks of 32kB each). Use 8k × 8 bit ROMs (use part 2764, as on pg. 205 of Katz). Each memory bank should have its own 13-bit address bus. There is also a bank_select input that selects between the two memory banks (bank_select = 0 enables bank 1; bank_select = 1 enables bank 2). You will need two 2:4 decoders, one octal 2:1 multiplexer (i.e., a multiplexer containing 8 2:1 muxes), and perhaps an inverter or two. Describe one advantage of using a dual memory subsystem rather than a single large one (such as a single 64kB memory).