CPSC 330 - Spring 2007
Homework 2
Due - Monday, Feb. 12, at class time
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
their names in parentheses under your name on the solution set you submit.
Purposes:
(1) work with combinational logic;
(2) work with sequential logic.
Example:
Consider A*( (~A) + B ) = A*B. Show by truth table that this is true.
A B | ~A | ~A + B | A*(~A+B) | A*B
-----+----+--------+----------+-----
0 0 | 1 | 1 | 0 | 0
0 1 | 1 | 1 | 0 | 0
1 0 | 0 | 0 | 0 | 0 true because the last
1 1 | 0 | 1 | 1 | 1 two columns are the same
Show by algebraic manipulation that this is true.
A*( (~A) + B )
= A*(~A) + A*B by distributive postulate
= 0 + A*B by inverse postulate
= A*B by identity postulate
1. Problem A.2(b) on page 724 of your text.
Example:
Determine the simplest logic expression for the values in this Kmap:
\BC
A\ 00 01 11 10
+----+----+----+----+ _ _ _ _ _ _ _ _
0 | 1 | 1 | 0 | 0 | sum of products = A*B*C + A*B*C + A*B*C + A*B*C
+----+----+----+----+ _
1 | 1 | d | d | 1 | don't cares = A*B*C + A*B*C
+----+----+----+----+
_
simplified expression = A + B (treat both don't cares as true)
2. Problem A.3 on page 725 of your text -- use Karnaugh maps.
Example
Design a 2-input circuit that gives an output of 1 only when the two
inputs are equal. First, show the truth table; and, second, show the
gate implementation. (This is the equality function or inverse-xor.)
A B | F in SOP form, A----*-----.
----+-- _ _ | AND-.
0 0 | 1 F = A*B + A*B B-*--------' | _ _
0 1 | 0 | | OR = A*B + A*B
1 0 | 0 | `-NOT-. |
1 1 | 1 | AND-'
`----NOT-'
3. A majority function is implemented by a combinational circuit when the
output is one if and only if the input variables have more ones than
zeros. Otherwise, the output is zero. Design a 3-input majority
function. First, show the truth table. Second, show the gate
implementation using AND, OR, and NOT gates.
Example
Consider again the equality function F= A*B + (~A)*(~B). Implement
this expression using one OR gate and two NAND gates.
A. check: __________
NAND-. _____________ __ ____ ____
B' | _____ A B | AB AB A+B | (AB)*(A+B) (AB)*(A+B)
NAND = (A*B) * (A+B) ----+-----------+----------------------
A. | 0 0 | 0 1 0 | 0 1
OR---' 0 1 | 0 1 1 | 1 0
B' 1 0 | 0 1 1 | 1 0
1 1 | 1 0 1 | 0 1
4. Problem A.13 on page 726 of your text.
Example
Show that the "JK" circuit given in the Wikipedia entry "SR_latch"
(http://en.wikipedia.org/wiki/Image:JK_latch_%28AND-NOR%29.png, accessed
Feb. 1, 2007), is incorrectly labeled.
First, note that the circuit is built from an inner RS nor-nor latch
(cf. http://en.wikipedia.org/wiki/Image:SR-NOR-latch.png). In the
"JK" circuit depicted, R = J and Q, and S = K and not-Q.
_ _
J K | Q Q | R=JQ S=KQ | Q_next
----+-----+-----------+-------
0 0 | 0 1 | 0 0 | 0 Q_previous
0 0 | 1 0 | 0 0 | 1
----+-----+-----------+-------
0 1 | 0 1 | 0 1 | 1 1
0 1 | 1 0 | 0 0 | 1
----+-----+-----------+-------
1 0 | 0 1 | 0 0 | 0 0
1 0 | 1 0 | 1 0 | 0
----+-----+-----------+------- _
1 1 | 0 1 | 0 1 | 1 Q_previous
1 1 | 1 0 | 1 0 | 0
5. Show that a circuit diagram in which R = K and Q, and S = J and not-Q,
(e.g., http://www.shef.ac.uk/physics/teaching/phy107/jkff.html), conforms
to the characteristic table for a JK circuit. (Note that JK should be
implemented as a flip-flop rather than as a mere latch so that J=K=1
will not cause multiple state changes.)
(Extra credit: does the nand-nand circuit shown on the Univ. Sheffield
web page conform to the JK characteristic table or to the SR table?
-- cf. Figure A.26 on p. 693 in your textbook. Explain your answer
fully for full extra credit.)
Example
A sequential circuit has one D flip-flop, two inputs X and Y, and one
output A. The combinational logic consists of two cascaded xor gates
with the output of the second gate being used as the next state.
A = Q(t)
D_in = Q(t) xor (X xor Y)
.--------------------------.
| |
| +-----+ |
+-----+ `-->| | D_in +---+ Q |
X--->| | | xor |------->| |---*-----> A
| xor |------>| | | D |
Y--->| | +-----+ CLK->| |
+-----+ +---+
The truth table for this circuit is
current next
inputs state output state
X Y Q(t) | X xor Y | A D_in == Q(t+1)
---------------+-----------+-----------------------
0 0 0 | 0 | 0 0 0
0 0 1 | 0 | 1 1 1
0 1 0 | 1 | 0 1 1
0 1 1 | 1 | 1 0 0
1 0 0 | 1 | 0 1 1
1 0 1 | 1 | 1 0 0
1 1 0 | 0 | 0 0 0
1 1 1 | 0 | 1 1 1
or you may find it easier to order the table with the current state
listed first (the tables are equivalent)
current next
state inputs output state
Q(t) X Y | X xor Y | A D_in == Q(t+1)
----------------+-----------+-----------------------
0 0 0 | 0 | 0 0 0
0 0 1 | 1 | 0 1 1
0 1 0 | 1 | 0 1 1
0 1 1 | 0 | 0 0 0
1 0 0 | 0 | 1 1 1
1 0 1 | 1 | 1 0 0
1 1 0 | 1 | 1 0 0
1 1 1 | 0 | 1 1 1
The state diagram for this circuit as a Moore machine (where the
outputs are associated with the states) is:
01,10
.---. .-----------. .---.
/ v.===./ v.===./ \
00,11 | |0/0| |1/1| | 00,11
\ /`==='^ /`==='^ /
`---' `-----------' `---'
01,10
(Note that a part of this circuit is essentially a T flip-flop.)
6. Problem A.38 on page 731 of your text.