Karnaugh Minimization Versus a Cost-Driven Implementation
A 4-input function F(A,B,C,D) is specified by minterms {0,1,2,5,8,9,10,13} with don't-cares at {6,7,14,15}. A junior engineer runs a Karnaugh map, gets a two-level sum-of-products with three product terms, and declares it optimal. A senior engineer points out that the target is a CPLD macrocell where each product term costs one macrocell and the OR is free, but input inversions are also free, while a two-input XOR gate is expensive. The senior claims a different factoring could reduce total cost even if the literal count is unchanged. The don't-cares were chosen by the original spec author for a reason nobody documented.
1. Group the minterms and don't-cares to find a minimal sum-of-products, and state how many product terms and literals result.
Read the worked answer
Plot on a 4-variable map. Group the 1s with adjacent don't-cares to make the largest groups:
- {0,1,2,3?} - 3 is not a 1 or DC, so cannot use. Instead group {0,1,8,9}: cells 0,1,8,9 form a 2x2 group (A=0 rows 0/1 with B=0, and A=1 rows 8/9). That gives B'C'? Check: cells 0(0000),1(0001),8(1000),9(1001) share B=0,C=0 → term B'C'. Four cells.
- {0,2,8,10}: cells 0,2,8,10 share B=0,D=0 → term B'D'. Four cells.
- {5,7,13,15}: 5(0101),7(0111),13(1101),15(1111) share B=1,D=1 → term BD. Uses DCs 7,15. Four cells.
- {6,7,14,15}: all DCs, not needed.
Coverage check: 0,1,2,5,8,9,10,13 all covered? 0,1,2,8,9,10 by first two terms; 5,13 by BD. Yes. Result: F = B'C' + B'D' + BD. Three product terms, six literals. Matches the junior's term count but note the specific terms matter for the next step.
2. The senior engineer claims factoring can reduce cost on the CPLD. Show a factored form and argue whether it actually helps given free inversions and costly XOR.
Read the worked answer
Observe B'C' + B'D' = B'(C' + D'), and BD. A tempting rewrite is F = B'(C'+D') + BD, i.e. B'·(C NOR? no) - C'+D' = (CD)'. So F = B'·(CD)' + B·D.
Cost analysis on the macrocell: the factored form uses B', (CD)', B, D and two AND terms plus OR. The (CD)' is a NAND, cheap. So this is 2 product terms (B'·(CD)' and B·D) - fewer macrocells than three. That is a real win.
But if someone proposes an XOR-based form (e.g. recognizing B'C'+B'D'+BD as something like B XOR ... ), the XOR gate is expensive per the constraint, so avoid it. The correct judgment: factoring to share B' and to use a NAND of C,D reduces product-term count from 3 to 2, which matters because macrocells are the scarce resource; literal count is unchanged, so a literal-only cost model would miss the improvement. The senior is right, but only for the macrocell cost model - on an FPGA LUT or a standard-cell library the ranking could differ.
3. The undocumented don't-cares are later revealed to be inputs that can actually occur and must produce F=1. What happens to the solution and what is the lesson?
Read the worked answer
If {6,7,14,15} must be 1, the function changes: now cells 6,7,14,15 are required 1s. Re-group:
- {6,7,14,15} all 1 now → term BC (B=1,C=1).
- {5,7,13,15} → BD still valid (all 1s/DCs now 1s).
- {0,1,8,9} and {0,2,8,10} still valid. But does BD + BC + B'C' + B'D' cover everything? 6,7,14,15 by BC and BD; yes. Actually BD already covers 7,15; BC covers 6,7,14,15. Combined with the B' terms, all 1s covered. Minimal may now be B'C' + B'D' + BD + BC, or with sharing B'(C'+D') + B(D+C).
Lesson: don't-cares are a contract, not a convenience. Using a DC to enlarge a group is only valid if the DC truly never occurs or its value is irrelevant. Undocumented DCs are a design risk; they must be traced to the spec or treated as 1s (worst case for a sum-of-products that must be 1) or as 0s depending on required behavior. The minimal expression found under wrong assumptions can be functionally wrong even though it is 'minimal.'