One circuit, several outputs
Real circuits rarely compute one function. A decoder, an adder, a seven-segment driver: several outputs, all of the same inputs. In a two-level circuit each output is an OR gate fed by AND gates — and nothing stops one AND gate from feeding two OR gates.
So the cost to minimize changes. It is no longer the number of terms in each expression, but the number of distinct product terms over all outputs: a term that appears in two expressions is still one gate.
Minimizing each output on its own and hoping the answers overlap does not work reliably. Two outputs may each have a perfectly minimal expression and share nothing, when a slightly different choice would have let them share a gate. To find those opportunities you need to know, for every term, which outputs it is good for.
Tags
Give every minterm a tag: the set of outputs that contain it. For
f1 = Σm(0, 1, 6, 7) f2 = Σm(3, 6, 7)
| Minterm | ABC | in f1 | in f2 | Tag |
|---|---|---|---|---|
| 0 | 000 | ✓ | {1} | |
| 1 | 001 | ✓ | {1} | |
| 3 | 011 | ✓ | {2} | |
| 6 | 110 | ✓ | ✓ | {1, 2} |
| 7 | 111 | ✓ | ✓ | {1, 2} |
Minterms that are in no output are left out. All the others go into one combined list, and you build one Scheinman tree for all the outputs together. (The tool shows tags as Greek letters: α for the first output, β for the second, and so on.)
The intersection rule
The tree is built exactly as in lesson 7, with one change, at the moment two entries match:
- The matched entry’s tag is the intersection of its parents’ tags.
- If the intersection is empty, there is no match: discard it.
- A parent gets its check mark only if the intersection contains the parent’s whole tag.
Why the intersection? The combined term covers both parents’ minterms. It can be used in an output only if every minterm it covers belongs to that output — which means the output must be in both tags.
Why the third rule? A check mark says “something larger takes care of me”. If minterm 7 has tag {1, 2} and the match it just took part in has tag {2}, then it has been taken care of for f2 only. For f1 it is still on its own, so it must stay unchecked.
Example 1: a shared prime implicant
The root: split on A (weight 4)
List: 0{1}, 1{1}, 3{2}, 6{1,2}, 7{1,2}
Left A = 0
- 0{1}
- 1{1}
- 3{2} ✓
Right A = 1, subtract 4
- 2{1,2} was 6
- 3{1,2} was 7
Match A eliminated
- 3 is in both lists: {2} ∩ {1,2} = {2} → keep pair (3, 7) with tag {2}.
- Check 3: its whole tag {2} is inside {2}. Do not check 7: its tag {1,2} is not.
The pair (3, 7) follows the path Match, Right, Right: the term BC, good for f2 only.
The Left branch: A = 0, split on B (weight 2)
List: 0{1}, 1{1}, 3{2}✓
Left B = 0
- 0{1}
- 1{1}
Right B = 1, subtract 2
- 1{2} was 3 ✓
Match B eliminated
- 1 is in both lists: {1} ∩ {2} = ∅ → discard. No check marks.
Minterms 1 and 3 are neighbours, but they belong to different outputs. A term covering both would be valid for neither, and the empty intersection says exactly that. One level down, 0 and 1 match with {1} ∩ {1} = {1}: the term AB, tag {1}.
The Right branch: A = 1
The list is 2{1,2}, 3{1,2} (originally 6 and 7). Both go Right at B, becoming 0 and 1. At C they split, 1 becomes 0, and the two match: {1,2} ∩ {1,2} = {1,2}. Path Right, Right, Match:
AB covering 6, 7 tag {1, 2} — one gate, usable by both outputs
Result
| Prime implicant | Covers | Tag |
|---|---|---|
| AB | 0, 1 | {1} |
| BC | 3, 7 | {2} |
| AB | 6, 7 | {1, 2} |
f1 = AB + AB f2 = BC + AB
Four term appearances, three gates. Here the shared term is an ordinary prime implicant of both functions, so two separate K-maps would have found it too. The next example is the one they would miss.
Example 2: a shared gate that neither output would choose
f1 = Σm(0, 1, 2) f2 = Σm(1, 3, 7)
Minimized separately, each needs two gates and they share nothing:
f1 = AB + AC f2 = AC + BC — four gates
Now follow minterm 1, the only one with tag {1, 2}, through the combined tree:
- In the A = 0 branch, splitting on B, it matches 3: {1,2} ∩ {2} = {2}. The pair (1, 3) is kept with tag {2} — that is AC. But {2} does not contain {1,2}, so 1 is not checked.
- One level down, splitting on C, it matches 0: {1} ∩ {1,2} = {1}. The pair (0, 1) is kept with tag {1} — that is AB. Again {1} does not contain {1,2}: 1 is still not checked.
Each larger term serves minterm 1 for one output; no larger term serves it for both. So at the end minterm 1 is collected as it stands: the three-literal term ABC with tag {1, 2}. It is not a prime implicant of f1, nor of f2. It is a prime implicant of the pair.
The combined chart
With several outputs, the chart has one column for each (output, minterm) that must be covered, and a row can only cover columns of the outputs in its tag.
| Prime implicant | Tag | f1 | f2 | |||||
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 1 | 3 | 7 | |||
| AB | {1} | × | × | |||||
| AC | {1} | × | × | essential | ||||
| AC | {2} | × | × | |||||
| BC | {2} | × | × | essential | ||||
| ABC | {1, 2} | × | × | selected | ||||
AC is essential (only it covers 2 in f1) and so is BC (only it covers 7 in f2). Two columns remain: minterm 1 in f1 and minterm 1 in f2. You can spend two gates, AB and AC — or one: ABC covers both columns.
f1 = AC + ABC f2 = BC + ABC
Three gates instead of four. Look at what was traded. Written as expressions, the two outputs now show 10 literals instead of 8, and neither expression is the minimal SOP of its own function. But the hardware is smaller: three AND gates with 7 inputs in total, instead of four with 8, because the shared gate is built once.
See every step of Example 2 See the shared gate as a circuit
Generating is not selecting
The tree finds the shared terms. Whether they get used depends on how the cover is chosen, and the choice has to be made for all outputs at once. The tool offers three strategies so you can see the difference:
| Cover selection | What it does | Example 2 |
|---|---|---|
| Per output | Each output gets its own chart, as if the others did not exist. What you would do first by hand. | 4 gates |
| Joint greedy | One chart for all outputs; repeatedly pick the row that covers the most uncovered columns. Fast, not always minimal. | 4 gates |
| Exact | One chart for all outputs, searched exhaustively (branch and bound) — the multiple-output counterpart of Petrick’s method. | 3 gates |
Greedy misses the saving here because at the start every row covers exactly two columns. It breaks the tie in favour of fewer literals and takes AB; after that, ABC is worth only one column and the chance to share is gone. Only a search that compares whole solutions sees that one row can replace two.
How much does sharing buy?
Sometimes nothing. In a full adder the sum Σm(1, 2, 4, 7) is an XOR: four isolated minterms, none of which can combine. The carry is the majority function AB + AC + BC. The two outputs have minterm 7 in common, but using ABC for the carry would not remove any of the carry’s three gates. Seven gates, however you select.
Sometimes a great deal. A BCD to seven-segment decoder has seven outputs of four inputs, with inputs 10–15 as don’t-cares. Minimized one output at a time it needs 16 distinct AND gates; joint greedy selection brings that to 10, and exact selection to 9. Enter it in the tool and compare the three modes yourself:
a: 0,2,3,5,6,7,8,9 b: 0,1,2,3,4,7,8,9 c: 0,1,3,4,5,6,7,8,9 d: 0,2,3,5,6,8
e: 0,2,6,8 f: 0,4,5,6,7,8,9 g: 2,3,4,5,6,8,9 don’t-cares: 10,11,12,13,14,15
Don’t-cares with several outputs
A don’t-care’s tag lists the outputs for which it is a don’t-care, and it enters the list already checked, as in lesson 7. One extra step is needed at the end: for each collected term, look again at every output and add it to the tag if all the minterms the term covers are 1s or don’t-cares of that output. This tag expansion recovers sharing that the intersections were too cautious to see.
The whole procedure
- Tag every minterm with the outputs that contain it; make one combined list.
- Build one Scheinman tree, applying the intersection rule at every match.
- Collect unchecked entries with their tags. Discard a term only if another term contains it and has a tag that includes all of its outputs.
- Expand tags if there are don’t-cares.
- Build one chart with a column per (output, minterm), and select rows for all outputs together.
- Each output’s expression is the OR of the selected terms whose tags include it — leaving out any that the output does not need.
Check yourself
- Write the tags for f1 = Σm(1, 3, 5), f2 = Σm(3, 5, 7).
Show answer
1{1}, 3{1,2}, 5{1,2}, 7{2}. - In a three-output problem, 2{1,2} in the Left list matches 2{2,3} in the Right list. What is the matched entry’s tag, and which parents are checked?
Show answer
The tag is {1,2} ∩ {2,3} = {2}. Neither parent is checked: {2} contains neither {1,2} nor {2,3}. The left parent is still needed on its own account for output 1, the right parent for output 3. - In Example 1, minterm 7 was not checked at the root. Where does it finally get its check mark?
Show answer
In the Right branch, when 6 and 7 match with tag {1,2}. That intersection contains 7’s whole tag, so now it is fully taken care of — by AB, for both outputs. - For the functions of question 1, separate minimization gives f1 = AC + BC and f2 = AC + BC: four gates. Find a three-gate solution.
Show answer
Minterms 3 and 5 both have tag {1,2}, and neither is ever fully checked, so ABC and ABC are both in the pool with tag {1,2}. Use one of them as the shared gate: f1 = AC + ABC, f2 = BC + ABC. (Or, symmetrically, f1 = BC + ABC, f2 = AC + ABC.) Three gates. - True or false: in a minimum-gate multiple-output solution, each output’s expression is a minimal SOP of that output.
Show answer
False. In Example 2, f1 = AC + ABC has five literals, while the minimal SOP of f1 alone is AB + AC with four. The circuit as a whole is what is minimal, not each expression.