Minimal SOP for a 4-Variable Karnaugh Map Function
Karnaugh map minimization is a systematic technique for finding the minimum sum-of-products expression for a Boolean function. It reduces gate count, propagation delay, and power consumption in the resulting circuit. Logic synthesis tools (Design Compiler, Yosys) automate this process, but understanding the underlying algorithm is expected at any digital logic interview. This problem gives you a specific 4-variable function and asks you to implement its minimal SOP.
The function F(A, B, C, D) is defined by the following truth table (A is MSB):
ABCD=0000: F=0, ABCD=0001: F=1, ABCD=0010: F=0, ABCD=0011: F=1 ABCD=0100: F=1, ABCD=0101: F=1, ABCD=0110: F=0, ABCD=0111: F=0 ABCD=1000: F=0, ABCD=1001: F=1, ABCD=1010: F=0, ABCD=1011: F=1 ABCD=1100: F=1, ABCD=1101: F=1, ABCD=1110: F=0, ABCD=1111: F=0
The minterms are: 1, 3, 4, 5, 9, 11, 12, 13. Grouping on the Karnaugh map yields three prime implicants covering all minterms: {1,3,9,11} = A'D + AD = D (when B=0 and C=0,1... actually the column D=1 with B=0: minterms 1,3,9,11 = B'D), {4,5,12,13} = B·C' (row B=1, C=0 spans columns D=0 and D=1), and verifying coverage: the minimal SOP is F = B'D + BC'.
Worked example: A=0,B=1,C=0,D=1 → B=1,C=0 → BC'=1 → F=1. A=1,B=0,C=1,D=1 → B'=1,D=1 → B'D=1 → F=1. A=0,B=1,C=1,D=0 → BC'=0, B'D=0 → F=0. ✓
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | A | input | 1 | MSB of the 4-variable function | | B | input | 1 | Second variable | | C | input | 1 | Third variable | | D | input | 1 | LSB of the 4-variable function | | F | output | 1 | Result of the minimized Boolean function |
Constraints
- The circuit is purely combinational. No clock or state.
- The minimal SOP is F = B'D + BC'. Implement exactly this expression.
- The optimal solution uses 2 NOT gates (NOT_B and NOT_C), 2 AND gates (B'D and BC'), and 1 OR gate (5 components total).
- All 16 input combinations are valid and must produce the correct output per the truth table.
Topics
Solve this problem
Place the gates, wire them up and watch the signals settle. Every submission runs on the same simulation engine that grades it.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.