CPSC 330 - Fall 2011
Homework 2
Due Monday, Oct. 3
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
1. (a) Show by truth table the 3-variable version of de Morgan's Law
for and-ing: ~(A*B*C) = (~A) + (~B) + (~C)
Be sure to circle the appropriate two equal columns and indicate
that because the columns are equal, the two expressions that they
represent are equal.
(b) Show by algebraic manipulation the 3-variable version of de
Morgan's Law for or-ing: ~(A+B+C) = (~A)*(~B)*(~C)
For each step, give the name of a logic property (from the lecture
notes www.cs.clemson.edu/~mark/330/logic.txt) that justifies the
step. Note that you can use the 2-variable versions of DeMorgan's
Law in proving this 3-variable version.
2. Simplify the following Karnaugh maps for functions D, E, and F.
D \ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | 0 | 0 | 1 | D = fn(A,B,C) = ____________________
+----+----+----+----+
1 | 0 | 0 | 1 | 1 |
+----+----+----+----+
E \ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | d | 0 | d | E = fn(A,B,C) = ____________________
+----+----+----+----+
1 | d | 1 | 0 | 1 |
+----+----+----+----+
F \ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | 1 | 0 | 0 | F = fn(A,B,C) = ____________________
+----+----+----+----+
1 | 1 | d | d | d |
+----+----+----+----+
3. A bit-serial adder has one D flip-flop, two inputs X and Y, and one
output S. The combinational logic consists of a full adder with the
carry out being used as the next state. (Ignore the initial set/reset
of the carry.)
+---------+
X ----->| | sum
| full |-----------------------> S
Y ----->| |
| adder | carry = D_in +---+ Q
.---->| |------------->| |---.
| +---------+ | D | |
| CLK->| | |
| +---+ |
`--------------------------------------'
(a) Give the state transition table with inputs X, Y, current state
Q(t), next state Q(t+1), and output S.
(b) Give the state diagram.
4. Consider a state machine with two inputs, R and I (reset and in), that,
after a reset R, outputs a 1 on each second 1 that it receives on input
I. Reset causes any count of previous and current I=1 inputs to be
lost, and the counting of I=1 inputs starts in the subsequent clock
cycle after the reset signal goes back to 0.
That is, the state machine behaves like this
input R: 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0
input I: 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1
output S: 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1
(a) Give the state diagram. (There should be only two states.)
(b) Give the state transition table with inputs R, I, current state
Q(t), next state Q(t+1), and output S.
(c) Give the simplified logic expressions for Q(t+1) and S.
(d) Extend the state transition table with J and K columns and, using
the JK excitation table, fill in the appropriate values for causing
the required state transitions.
(e) Give the simplified logic expressions for J and K.
5. Redesign the circuit of the first example on the sequential logic
handout www.cs.clemson.edu/~mark/330/seq_design.pdf using JK flip-flops
rather than D flip-flops.