Problem Set Number 1
Computer Science 471

Due by 5 PM, Monday Sept. 23, 1996

1. (5 points) Make gates out of muxes. Show how to use a single 2-input multiplexor to implement AND, OR, NOT, and EXOR gates (i.e., one mux per gate). Assume that logical values 0 and 1 are available, and that your two inputs are presented in high-true form only. One of these gates should give you trouble; please explain.

2. (5 points) Problem 3.11 from the text.

3. (5 points) Problems 3.12 through 3.15 from the text.

4. (5 points) What hardware is required to test 32-bit quantities for equality? Draw a gate-level circuit with 32-bit inputs x and y, and 1-bit output x=y. Use some clear shorthand for repeated instances of the same structure.

5. (10 points) What hardware is required to test whether one 32-bit quantity is less than another? Sketch the general idea for a combinational logic circuit that would take 32-bit, signed, 2's-complement, integer inputs x and y and produce a 1-bit output x<y. You do not need to draw all the gates; just be clear about what is required.

6. (5 points) Draw a gate-level circuit for x>=0 (where x is 32-bit, signed, etc., etc.).

7. (10 points) Problem 3.30 from the text.

8. (10 points) Problem B.14 from the text.

9. (5 points) The textbook authors (and their publisher) would like you to fill out a short questionnaire for each chapter. The chapter 1 questionnaire may be found at Please fill it out and e-mail the result to the publisher as directed. Your answers to this and future questionnaires will greatly help the authors improve their book. Please do not, repeat not, ``cc your instructor on this email,'' as the form directs. To get the 5 points for this question, just write down the time you sent your message to the publisher.

10. (another 5 points) Same deal for Appendix B; find the questionnaire at

11. (1 point) How long did this take you, not counting the reading, and with whom did you work?