H5: Minimization

Time Estimate1-2 hours   Grade Impact1%   DueSep 14 @ 12pm  

Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.

Notes

Show your work. You must show all steps of your work for full credit. While calculators can perform these calculations, demonstrating your process ensures understanding and mastery of the concepts.

Notation. To encourage flexibility between notations, the problems in this assignment use a variety of notations. We have discussed each style already; review the textbook or your notes if you need help.

Exercises

1. Using a 3‑variable K‑map, simplify $F(A,B,C)=\Sigma m(1,2,5,6)$. Provide the minimal Sum‑of‑Products expression and show the groupings used (label cell indices and resulting product terms).

2. For $F(W,X,Y,Z)=\Sigma m(0,1,2,5,6,7,8,9,14,15)$, use a 4‑variable K‑map to find a minimal SoP. Show the prime implicants you used and indicate which minterms each implicant covers.

3. Given $F(A,B,C,D)=\Sigma m(1,3,7,11)$ with don’t‑care terms $d(2,10)$, use a 4‑variable K‑map to derive a minimal expression (SoP or PoS). Indicate how you used the don’t‑care terms (i.e., which don’t‑cares were treated as 1 or 0 and why).

4. Find a minimal-cost PoS and SoP expression given the following truth table:

   A	B	C	F
   0	0	0	0
   0	0	1	1
   0	1	0	0
   0	1	1	1
   1	0	0	0
   1	0	1	1
   1	1	0	0
   1	1	1	1

5. Find a minimal-cost PoS and SoP expression given the following truth table:

   A	B	C	F
   0	0	0	0
   0	0	1	0
   0	1	0	0
   0	1	1	1
   1	0	0	0
   1	0	1	1
   1	1	0	1
   1	1	1	1

6. Find a minimal-cost PoS and SoP expression given the following truth table:

   A	B	C	F
   0	0	0	0
   0	0	1	1
   0	1	0	1
   0	1	1	0
   1	0	0	1
   1	0	1	0
   1	1	0	0
   1	1	1	1

6. Find a minimal-cost PoS and SoP expression given the following truth table:

   A	B	C	D	F
   0	0	0	0	0
   0	0	0	1	0
   0	0	1	0	0
   0	0	1	1	0
   0	1	0	0	0
   0	1	0	1	0
   0	1	1	0	1
   0	1	1	1	1
   1	0	0	0	0
   1	0	0	1	1
   1	0	1	0	0
   1	0	1	1	1
   1	1	0	0	0
   1	1	0	1	1
   1	1	1	0	1
   1	1	1	1	1

7. Find a minimal-cost PoS and SoP expression given the following truth table:

   A	B	C	D	F
   0	0	0	0	1
   0	0	0	1	0
   0	0	1	0	1
   0	0	1	1	0
   0	1	0	0	0
   0	1	0	1	0
   0	1	1	0	0
   0	1	1	1	0
   1	0	0	0	1
   1	0	0	1	0
   1	0	1	0	1
   1	0	1	1	0
   1	1	0	0	0
   1	1	0	1	0
   1	1	1	0	0
   1	1	1	1	0

8. (30 points) Choose one of the following options. Generative AI is strictly prohibited for this question.

   1. In a short essay (about 500 words), discuss the practical trade‑offs that appear when minimizing logic for physical hardware implementation. You may wish to cover metrics such as literal/gate count, logic depth (delay), area, power, and testability. Explain why the algebraically minimal expression (fewest literals) is not always the best choice on silicon or an FPGA, and give one concrete example where an alternative optimization goal (e.g., reduced depth or balanced load) should take priority.

   2. Find and describe an alternative approach to minimization. Write a short description (about 250 words) of this approach, then use it to solve 2 of the earlier problems in this assignment.

   3. In a programming language of your choice, write a simple automated K-map solver. It only needs to work on the command line, and it should work with 2 variables. Up to 20 points of backup credit (which can be used to replace points lost in this H4, H5, Q6, and/or Q7) are available if your program also works with 3 and 4 variables. It should take a truth table as input (specify the input format however you desire), and it should output a K-map printout alongside a minimal expression.