Homework 1
Bruce Yen
ECE572: Adv. Logic Synth.
Fall 2003
Professor Perkowski
Kmaps/ESOP/SOP
Due: 10/6/2003
Part 1: 4-Variable Karnaugh Map
Figure 1a
Figure 1a is the statement of problem in the form of a
Karnaugh map. The SOP of the literals is:
F = A’B’C’D’ + A’B’C’D + A’B’CD + A’BC’D + ABC’D’ + ABCD’ + AB’CD’
The POS of the literals is:
F = (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’)(A’+B+C’+D’)
Part 2: ESOP Minimization – Algebraic
From the initial SOP equation we can replace the ORs with XORs because they are all disjoint.
F = A’B’C’D’ Å A’B’C’D Å A’B’CD Å A’BC’D Å ABC’D’ Å ABCD’ Å AB’CD’
We begin to simplify:
F = A(BC’D’ Å BCD’ Å B’CD’) Å A’(B’C’D’ Å B’C’D Å B’CD Å BC’D)
= AD’(BC’ Å BC Å B’C) Å A’(B’(C’D’ Å C’D Å CD) Å BC’D)
= AD’(B(C’ Å C) Å B’C) Å A’(B’(C’D’ Å CD) Å B’C’D Å BC’D)
= AD’(B Å B’C) Å A’B’C’D’ Å A’B’CD ÅA’C’D
= ABD’ Å AB’CD’ Å A’B’C’D’ Å A’B’CD Å A’C’D
Which is not a very good solution, as we find out later through a graphical minimzation. This solution has 5 implicants and 18 literals versus 4 implicants and 9 literal solution found graphically. It is more difficult to algebraically introduce even/odd overlapping with a strictly algebraic method. This is because one must introduce dual overlaps intuitively, and this solution ignores the possibility of overlapping, as shown in figure 2b.
Figure 2b. Figure 2c.
In figure 2c I’ve impliemented the circuit assuming I have 2, 3, 4-input ANDs, 2-input XORs and dual rail inputs. Also, I assume no timing/delay issues (Made with student version of PSPICE Schematics).
Part 3: ESOP Minimization - Graphical
Figure 3a. Figure 3b. Figure 3c.
Figure 3a. My initial attempt. It is quick and simple, done by encirling large blocks of 1’s and placing an overlapping envelope when 0’s were present within the block.
Figure 3b. This solution I created with the idea in mind of minimizing the number of literals involved by increasing the size of the blocks where I could. I noticed that if I simply extended A’D to become D, and overlapped that with an extension of AD’, it would eliminate 2 literals. It can be shown that it is simliar to a large checkerboard pattern. This is a better solution than solution 1.
Figure 3c. This solution I created with the idea in mind of minimizing the number of inputs. Whereas the previous two solutions use all inputs (A, B, C, D, A’, B’, C’, D’) this solution attempts to minimize the number of inputs and eliminates both A and B’. However, I did have to trade off one additional literal over solution b.
Table 3.
|
Solution # |
# implicants |
# literals |
# inputs |
Boolean Expression |
|
Figure 4a |
4 |
11 |
8 |
B’C’D’ Å A’BCD Å A’D Å AD’ |
|
Figure 4b |
4 |
9 |
8 |
B’C’D’ Å A’BCD Å A Å D |
|
Figure 4c |
4 |
10 |
6 |
A’ Å A’BCD Å BC’D’ Å CD’ |
|
Figure 2b |
5 |
18 |
8 |
ABD’ Å AB’CD’ Å A’B’C’D’ Å A’B’CD Å A’C’D |
In figure 3d I’ve impliemented the circuit to solution b, assuming I have 2, 3, 4-input ANDs, 2-input XORs and dual rail inputs. Also, I assume no timing/delay issues (Made with student version of PSPICE Schematics).
Figure 3d.
]
Part 4: SOP Minimization - Covering Method
Table 4: Covering Table
|
Minterm |
0 |
1 |
3 |
5 |
10 |
12 |
14 |
|
Implicant |
|
|
|
|
|
|
|
|
A’B’C’ |
X |
X |
|
|
|
|
|
|
A’B’D |
|
X |
X |
|
|
|
|
|
A’C’D |
|
X |
|
X |
|
|
|
|
ABD’ |
|
|
|
|
|
X |
X |
|
ACD’ |
|
|
|
|
X |
|
X |
A quick glance at this table tells us that every implicant is an essential implicant because each includes a minterm that none of the other implicants cover. We will use overlapping minterms to reduce the number of literals per term; this will result in NANDs/NORs with smaller number of inputs. This solution is shown on a Karnaugh map in figure 4a.
SOP Solution: A’B’C’ + A’B’D + A’C’D + ABD’ + ACD’
This solution is shown on a Karnaugh map in figure 4a.
In figure 4b I’ve impliemented the the SOP solution, assuming I have 3-input ANDs, 2, 3-input ORs, and dual rail inputs. Also, I assume no timing/delay issues (Made with student version of PSPICE Schematics).
Figure 4a Figure 4b
