CPSC 330 - Fall 2013
Homework 2
Due Monday, Sept. 30
Each student must turn in a separate set of homework solutions,
but you may work together in study groups with other students
from the class. Include the names of your study group members
on the solution set you submit.
Also, please provide sufficient space for your calculations and
answers so that grading will be easier.
Appendix C (see http://www.cs.colostate.edu/~malaiya/470/Appendix-C.pdf)
1. C.6 - Show NAND is universal by implementing (a) two-input AND, (b)
two-input OR, and (c) one-input NOT functions with one or more
two-input NOR gates.
2. C.11 - Write the four logic functions as specified.
3. C.14 - Implement the switching element as described using two two-input
muxes.
4. Consider a function F to compare two two-bit fields, x1 x0 and y1 y0,
and produce a one on output only if the two fields are the same.
(a) Write a simplified logic function that implements the two-bit
comparison.
(b) Draw a circuit with AND, OR, and NOT gates to implement the function.
(In your diagram, you may use inverted inputs on the AND and OR gates
in place of explicit NOT gates.)
(c) Consider the list of 7400-series DIP chips at
http://en.wikipedia.org/wiki/List_of_7400_series_integrated_circuits.
Give the 7400-series part numbers and part counts needed to implement
your circuit in (b). (Note that inverted inputs will need NOT gates.)
Use the simple four-digit parts up through 7432.
(d) See if you can simplify the circuit in terms of gate count if you
are allowed to use NAND, NOR, and XOR gates in addition to AND, OR,
and NOT gates to implement the function.
(e) Consider the list of 7400-series DIP chips at
http://en.wikipedia.org/wiki/List_of_7400_series_integrated_circuits.
Give the 7400-series part numbers and part counts needed to implement
your circuit in (d). Use the simple four-digit parts up through 7486
(Do not use 7485!)
(f) Consider using 2-input, 1-output PALs as shown in
http://en.wikipedia.org/wiki/File:Programmable_Logic_Device.svg.
(Actual PALs have many more inputs and outputs, but assume you can
get a chip like the one in the diagram.) Show a circuit diagram for
the two-bit comparator using these 2-input, 1-output PALs. For each
PAL give an 8-bit fuse list with 0 for blown fuse (i.e., disconnect)
and 1 for remaining fuse. Try to optimize the circuit to require the
fewest PALs possible. (Hint: A*B = 8'b10100000 = 0xa0, A+B =
8'b10000010 = 0x82. Note that a single-variable AND term is allowed.)
(g) Consider using FPGA CLBs as shown in the lower half of
http://inst.eecs.berkeley.edu/~cs150/sp00/classnotes/u6.1/6_1_3.html.
(Assume that we will be using the unregistered output of the LUT,
that is, the 17th bit is 1.) Show a circuit diagram for the two-bit
comparator using these 4-input CLBs. For each CLB give the 16-bit
LUT configuration. Try to optimize the circuit to require the fewest
CLBs possible. (Hint: A*B + C*D = 16'b0001000100011111 = 0x111f.)
5. Finish the truth table and state diagram for the "Synchronous 3-bit
Up/Down Counter" we started in class on Wednesday, Sept. 18. See
http://www.electronics-tutorials.ws/counter/count_4.html.
The table should have columns (where I is the UP/~DOWN input):
QA(t) QB(t) QC(t) I | JA KA JB KB JC KC | QA(t+1) QB(t+1) QC(t+1)
--------------------+-------------------+------------------------
6. Design a modulo-3 counter using two D flip-flops. (There is no input.)
Use a truth table with don't care values where appropriate.
QA(t) QB(t) | QA(t+1) QB(t+1)
------------+----------------
Simplify the logic expressions for the next state values, and draw the
resulting circuit.