CPSC 330 - Fall 2008
Homework 2
Due - Wednesday, September 24
[updated Sept. 17 to change due date and fix typo in #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
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
1 1 | 0 | 1 | 1 | 1 true because the table is an
^ ^ exhaustive enumeration and the
\______/ last 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. (a) Show by truth table the 3-variable version of de Morgan's Law
for and-ing: ~(A*B*C) = (~A) + (~B) + (~C)
(b) Show by algebraic manipulation the 3-variable version of de
Morgan's Law for or-ing: ~(A+B+C) = (~A)*(~B)*(~C)
(You will use the 2-variable version in proving this.)
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. Simplify the following Karnaugh maps of function F. (4 pts. each)
\ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | 0 | 0 | 1 | F = fn(A,B,C) = _________________________
+----+----+----+----+
1 | 0 | 0 | 1 | 1 |
+----+----+----+----+
\ BC
A \ 00 01 11 10
+----+----+----+----+
0 | 1 | d | 0 | d | F = fn(A,B,C) = _________________________
+----+----+----+----+
1 | d | 1 | 0 | 1 |
+----+----+----+----+
Examples
[see lecture notes and pdf handout]
3. Consider the clocked JK latch given in the following diagram:
http://www.asic-world.com/images/digital/jk_latch.gif
We will for the moment ignore the clock (or enable) signal E.
Let the next state of this latch be called Q_next. Fill in the
intermediate columns of the table and verify that the R and S inputs
do indeed lead to Q_next values as shown.
J K | Q Q' | R=K*Q S=J*Q' | Q_next
----+------+--------------+-------
| | |
0 0 | 0 1 | | 0 \
| | | | retain previous value (same as Q)
0 0 | 1 0 | | 1 /
| | |
----+------+--------------+-------
| | |
0 1 | 0 1 | | 0 \
| | | | reset
0 1 | 1 0 | | 0 /
| | |
----+------+--------------+-------
| | |
1 0 | 0 1 | | 1 \
| | | | set
1 0 | 1 0 | | 1 /
| | |
----+------+--------------+-------
| | |
1 1 | 0 1 | | 1 \
| | | | toggle (changes to Q`)
1 1 | 1 0 | | 0 /
| | |
----+------+--------------+-------
4. 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.
5. 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 only be 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 Jand 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.