CPSC 330 - Spring 2006
Homework 2
Due by class time on Monday February 13.
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.
Purpose:
(1) work with combinatorial 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
Consider the consensus theorem: A*B + (~A)*C + B*C = A*B + (~A)*C
1. Show by truth table that the theorem is true.
2. Show by algebraic manipulation that the theorem is true.
Consider DeMorgan's Law for three variables: ~(A*B*C) = ~A + ~B + ~C
3. Show by truth table that the law is true.
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.
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-'
4. 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 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
5. Give the full adder circuit diagrams for sum and carry_out using nine
NAND gates and three NOT gates. The NAND gates can have up to four
inputs each.
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. 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
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. (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 the four-bit unsigned values a and b, a>b
Note: transitions from state 11 are don't cares (x's). Also, there is no
need to design a state-reset capability for this homework.
(a) give the state diagram
(b) give the truth table
(c) design a circuit
**