CPSC 330 - Fall 2007
Homework 2
Due - Monday, September 24
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. Problem A.6 on page 725 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
4. 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.)
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.)
5. Consider the design of a serial comparator takes that two inputs A and B.
The comparator has three valid states:
state meaning
00 A = B
01 A < B
10 A > B
11 never reached from stating state of 00
Assume the comparator starts in state 00 and changes state as each pair of
bits, A and B, are examined.
(a) Finish the derivation of the circuit diagram for processing the bits
of A and B in a left-to-right order.
(b) Since serial hardware is typically set up to process the bits in a
right-to-left manner (to account for the carry in addition), repeat
the derivation of a circuit diagram for a serial comparator but
this time for right-to-left scans.
Two unsigned words, a and b, are processed from the least significant
bit to most significant bit. Thus, in the first step, a0 and b0 are
supplied to the A and B inputs. In the second step, a1 and b1 are
supplied. Etc.
Thus, comparing a=1001 with b=0011 means you will run through the
following steps:
initially: state starts at 00 (a=b)
0: compare A=a0=1 and B=b0=1: state stays at 00 (a=b)
1: compare A=a1=0 and B=b1=1: state changes to 01 (a**b)
thus, for these example four-bit unsigned values a=1001 and b=0011, a>b
Note: transitions from state 11 are don't cares (d's). Also, there is
no need to design a state-reset capability for this problem.
i) give the state diagram
ii) give the truth table (there is no need for output columns)
iii) design a circuit (output is merely the state values)
**