CSE370 (Autumn 03) Assignment 3 Solution
1. CLD-II, Chapter 3, problem 3.1, parts a, and b.
3.1.a Use K-Maps to simplify F=∏M(0,4,18,19,22,23,25,29)
F = WY+V’Z+V’Y+WZ’+VW’Y’
b.
F=∑m(0,1,4,5,12,13)
F=
A’C’+BC’
2. CLD-II, Chapter 3, problem 3.4, all parts.
3.4.a Express F=AB’C+AD+AC
in Canonical product of sums form. Use ∏M notation
To
get ∏M notation
simply state all of the 0 squares.
∏M=(0,1,2,3,4,5,6,7,8,12)
b. Express F in minimized product of
sums form
Group
the zeros as shown above, then convert to PoS form.
F
= A’+C’D’ = A(C+D)
c. Express F' in minimized product of
sums form
F’
means 1s and 0s switch. To get the POS, group the 1s as shown
and then put the result in POS form.
F’
= AC+AD = (A’+C’)(A’+D’)
d.
Express F' in
minimized sum of products form
Group
on the 0s to get the sum of products of F'
F’
= A’+C’D’
e.
Implement F and F’
using only NAND gates
F
= AD+AC = ((AD)’(AC)’)’
F’
= A’+C’D’ = (A’’(C’D’)’)’ = (A(C’D’)’)’
f.
Implement F and F'
using only NOR gates
F
= (C’+D’)(A’) = ((C’+D’)’+A)’
F’
= (A’+C’)(A’+D’) = ((A’+C’)’+(A’+D’)’)’
3. CLD-II,
Chapter 3, problem 3.6, parts c, and e.
3.6.c Use K-map to put F’=∑m(2,4,5,6,7,8,10,13) into minimized
Sum of Products form
F’ = A’B+BC’D+A’CD’+AB’D
e. F=(A’+B+C)(A+B+C’+D)(A+B’+C+D)(A’+B’)
First convert back to SoP form
(A’+B+C)(A+B+C’+D)(A+B’+C+D)(A’+B’)
(A’+B+C)’+(A+B+C’+D)’+(A+B’+C+D)’+(A’+B’)’
AB’C’+A’B’CD’+A’BC’D+AB
Next, Place 0s in the K-Map according
to that function
F =
A’C’D’+A’B’D+A’BC+AB’C
4. CLD-II, Chapter 3, problem 3.11, part b.
3.11.b Draw a schematic for F=(AB+C)E+DG using
only NOR and NAND gates.
First construct the F from AND and OR gates
Replace ANDs with NANDs and add Bubbles on
the inputs that correspond.
Replace ORs with bubbled inputs with NANDs.
5. CLD-II, Chapter 3, problem 3.16, all parts.
3.16
Consider the functions:
(i)
F=(A+(BC))(C’+D)
(ii)
G=((A+B’)D)+(A+(BC))
a.
Implement each function using only NAND Gates
F:
use procedure for 3.11.b
G: use procedure from 3.11.b
b. Repeat (a) using NOR gates only
F:
Implement using ANDs and ORs
Replace
ORs with NORs and invert inputs to all ANDs
Replace
ANDs with inverted inputs with NORs
G:
Follow same procedure
c. Find the 2-level minimized Sum of
Products Form
F = (A+BC)(C’+D) = A(C’+D)+BC(C’+D)
= AC’+AD+BCD
Fill in and then group the 1s for the SoP
F
= AC’+AD+BCD
G
= ((A+B’)D)+(A+BC) = AD+B’D+A+BC
G = A+B’D+BC
d.
Find the 2-level
minimized Product of Sums Form
Group the 0s in the K-maps
from part C
F = CD’+A’B’+C’A’
= (C’+D)(A+B)(C+A)
G =A’BC’+A’B’D’
=(A+B’+C)(A+B+D)
e.
For each function
what is the “simplest” implementation
F is better with the NOR
implementation
G
is better with the NAND implementation
6. CLD-II, Chapter 3, problem 3.25, all parts.
3.25 Develop
a minimized implementation of a 2-bit combinational divider. The
system
has 2 2-bit inputs A,B and C,D and generates 2 2-bit outputs, the quotient
W,X and the remainder Y,Z.
a.
Draw the truth tables for W,X(A,B,C,D) and Y,Z(ABCD)
|
A |
B |
C |
D |
W |
X |
|
Y |
Z |
|
0 |
0 |
0 |
0 |
X |
X |
|
X |
X |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
0 |
|
0 |
1 |
0 |
0 |
X |
X |
|
X |
X |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
|
0 |
1 |
|
1 |
0 |
0 |
0 |
X |
X |
|
X |
X |
|
1 |
0 |
0 |
1 |
1 |
0 |
|
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
|
1 |
1 |
0 |
0 |
X |
X |
|
X |
X |
|
1 |
1 |
0 |
1 |
1 |
1 |
|
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
1 |
|
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
1 |
|
0 |
0 |
b.
Minimize the functions W,X,Y,Z using
4-variable K-maps.
Write
the expressions for the minimized sum of products form of each function
W
= AC’
X
= AB+BC’+AD’
Y
= AB’CD
Z
= BD’+CBA’
c.
Repeat the minimization process, this time deriving product of sums form.
W = A’+C = AC’
X = BD+CA’ = (B’+D’)(C’+A)
Y = B’D’+B+C’D+A’D = (B+D)(B’)(C+D’)(A+D’)
Z = C’+B’C+AD = C(B+C’)(A’+D’)
7. CLD-II, Chapter 3, problem 3.27, all parts.
3.27 Develop
a minimized implementation of a “ones count” circuit.
The system has 4
inputs
A,B,C,D and generates a 3-bit output XYZ. XYZ is 000 if 0 inputs are 1,
001 if 1 input is 1 and so on.
a.
Draw the truth table for XYZ(A,B,C,D)
|
A |
B |
C |
D |
X |
Y |
Z |
|
A |
B |
C |
D |
X |
Y |
Z |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
0 |
0 |
b.
Minimize the functions X,Y,Z using
4-variable K-maps to derive minimized Sum of Products form.
X
= ABCD
Y
= ABC’+BC’D+AC’D+AB’C+A’CD+BCD’
Z
=
A’B’C’D+A’BC’D’+AB’C’D’+ABC’D+A’BCD+AB’CD+A’B’CD’+ABCD’
c.
Repeat the minimization process, this time deriving Product of Sums form.
X = A’+C’+B’+D’ = (A)(B)(C)(D)
Y = A’B’C’+A’C’D’+B’C’D’+A’B’D’+ABCD
Y =(A+B+C)(A+C+D)(B+C+D)(A+B+D)(A’+B’+C’+D’)
Z = (A+B+C+D)(A+B+C’+D’)(A+B’+C+D’)(A+B’C’+D)(A’+B+C+D’)
(A’+B+C’+D)(A’+B’+C+D)(A’+B’+C’+D’)