CS 370 - Autumn 2002
Introduction to Digital Design
Instructor: Carl Ebeling

Homework Set 1
DUE: Oct. 11, 2002, Start of class

Collaboration Policy:

Unless otherwise noted, you may collaborate with other CSE370 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 during or immediately after class will incur a 10% penalty. We will penalize your assignment 10% per day for each additional day late.

Please show all of your work.Your solutions must be legible…we will not spend time trying to decipher poorly written assignments.

1. (12 pts) Convert the following decimal numbers to binary, octal and hexadecimal:
(a) 27
(b) 915
(c) 0.375
(d) 250.8

2. (12 pts) Find the 1's complement and the 2's complement of each of the following binary numbers (use 8-bit numbers):
(a) 00101010
(b) 01101011
(c) 11001001
(d) 0
(e) 11111111
(f)  10000000

3. (4 pts) Convert the following numbers to decimal (assume that all numbers are unsigned):
(a) 100110110112
(b) 73618
(c) 7E3C16
(d) 10001.1012

4. (6 pts) A=0110102, B=1000012, C=111111 2, D=10112. Calculate:
(a) A+B+C+D
(b) B–A
(c) A×D

5. (6 pts) Convert the following numbers to 2’s complement binary and perform the following operations in binary. How many bits are required to express each result without overflow?
(a) 3921 + 212
(b) 820 – 1996

6. (2 pts) Re-express the following 4-bit 2’s complement numbers as 8-bit 2’s complement numbers
(a) 0111
(b) 1010

7. (6 pts)  Prove the three simplification theorems using perfect induction.

8. (8 pts)  Show that an n-input AND gate can be replaced by n-1 2-input AND gates.  Can the same be done for NAND gates?  Justify your answer.

9. (6  pts) Use the Boolean theorems to rewrite the following expression using as few inversions as possible (complemented parentheses are allowed):
B' C + A C D' + A' C + E B' + E (A + C) (A' + D')

10. (6 pts) Simplify (i.e., minimize the number of literals) using known logic identities.  Note which theorems or laws you used in the derivation:
(a)   f (X,Y,Z) = Y' Z + X' Y Z + X Y Z
(b)  f (X,Y,Z) = (X + Y)(X' + Y + Z)(X' + Y + Z')

11. (6 pts) Find and simplify the complement of the following functions:
(a)   A B C + B (C' + D')
(b)  [A + (B C D)' ] [ (A D)' + B (C' + A) ]

12. (10 pts) The following truth table represents a logic function. A, B, and C are inputs, and Out is the output.
Write the truth table as a Boolean expression. Minimize the Boolean expression, and draw the minimized function using logic gates.

 A B C Out 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

13. (6 pts) A self-dual logic function is a function F such that F = FD .  Which of the following functions are self-dual?  Support your answer.
(a) F = x
(b) F = x y' + x' y
(c) F = Majority function.  (With an odd number of inputs, more than half are 1.)