The Scheinman tree method

The same merging, organized as a tree

Quine–McCluskey finds prime implicants by sorting minterms into groups by their number of 1s and comparing neighbouring groups. The Scheinman method finds the same prime implicants by asking one question at a time: what happens if I split the list on this variable?

Two things make it pleasant by hand:

• You work with the decimal minterm numbers. No bit patterns to copy, no dashes to line up.
• Every merge is a local event: it happens between the two halves of one node of a tree. At any moment your work is a partly drawn diagram that you extend one level at a time.

What happens at one node

Take the variables in order, most significant first. Each variable has a weight: for three variables A, B, C the weights are 4, 2, 1; for four variables 8, 4, 2, 1. At a node you have a list of numbers and the next variable to split on.

1. Split. Numbers smaller than the weight have the variable = 0: they go Left, unchanged. The others have the variable = 1: they go Right, and you subtract the weight.
2. Match. Any number that now appears in both lists is a matched pair. Its two minterms were identical except in this variable, so they combine by XY + XY = X and the variable is eliminated. Write the number in a third list, Match, and put a check mark ✓ beside both parents.
3. Continue. Match, Left and Right each become a new node, split on the next variable. Checked numbers stay in their lists — a checked number may match again further down.

Subtracting the weight is what makes matching trivial. After it, “differ only in this variable” simply means “the same number on both sides”.

Reading a term from its path

Every entry in the tree got there by a sequence of branch choices, one per variable. That path is the product term:

For example, over A B C the path Right, Left, Match is the term AB.

Worked example

F(A, B, C) = Σm(0, 4, 5, 7)

This is the function from the home page. It is small, and it contains a trap that is worth meeting early.

The root: split on A (weight 4)

Minterms 0 and 4 differ only in A, and the tree found that without looking at a single bit.

The Match branch: the pair (0, 4)

The Match list holds one entry, the value 0 standing for the pair (0, 4). Split on B (weight 2): 0 goes Left. Split on C (weight 1): 0 goes Left again. It never meets a partner, so it is never checked. Its path is Match, Left, Left:

BC   covering 0, 4   — unchecked

The Left branch: A = 0

One entry, the checked 0. Alone in its list, it has nothing to match at B or at C. Nothing new here.

The Right branch: A = 1, split on B (weight 2)

The matched entry has path Right, Match, and then at C the value 1 goes Right: the term is AC, covering 5 and 7. Nothing further matches it, so it stays unchecked.

Right, then Left: A = 1, B = 0, split on C (weight 1)

Path Right, Left, Match: the term AB, covering 4 and 5.

The whole tree

• Split on A — 0, 4, 5, 7
  • Match (0, 4) → Left at B, Left at C → BC prime
  • Left 0✓ — nothing to match
  • Right 0✓, 1, 3 — split on B
    • Match (5, 7) → Right at C → AC prime
    • Left 0✓, 1✓ — split on C: match (4, 5) → AB prime
    • Right 1✓ — nothing to match

See all nine steps of this example

Collecting the prime implicants

1. Collect every matched entry that was never checked, and every original minterm that was never checked (a minterm that combines with nothing is its own prime implicant).
2. Discard any collected term that is contained in another. This happens with larger groups: a group of four is built from pairs, and some of those pairs can reach the bottom of another branch unchecked. The containment test removes them.

Here every minterm was checked, and three matched entries were not: BC (0, 4), AC (5, 7) and AB (4, 5). None contains another. These are exactly the prime implicants that Q-M or a K-map gives.

Then the chart — always

The tree produces all prime implicants, not a minimal set. Finish with the cover chart:

F = BC + AC

The tree itself warns you that the chart has work to do: minterms 4 and 5 were each checked twice. A minterm that lies inside more than one prime implicant always collects more than one check, and wherever prime implicants overlap there may be a choice to make.

Don’t-cares

Put the don’t-cares in the starting list already checked. They take part in every match, so they help build larger terms, but they are never collected on their own. A matched entry whose two parents are both don’t-cares starts life checked for the same reason. As always, don’t-cares get no column in the chart.

Tree or table?

Both methods apply the same identity and find the same prime implicants; both take exponential time in the worst case. For the four-variable function of lesson 5, Σm(0, 2, 3, 5, 7, 8, 10, 13), the tree gives the same five prime implicants and the chart the same answer, BD + BCD + ACD. The difference is how the work is organized: Q-M compares every term in one group with every term in the next; the tree only ever compares the two halves of one node, by looking for equal numbers.

The step viewer draws every node of the tree for any function of up to five variables, in the same order you would work by hand: Match first, then Left, then Right. Try the lesson 5 function: Σm(0, 2, 3, 5, 7, 8, 10, 13). The Scheinman tool shows the same steps as images.

Check yourself

1. A four-variable list 3, 9, 12, 13 is split on A (weight 8). What are the Left and Right lists? Is there a match?
   Show answer

   Left: 3. Right: 9 − 8 = 1, 12 − 8 = 4, 13 − 8 = 5, so 1, 4, 5. No number is in both lists, so nothing matches at this node.
2. Over A B C D, an unchecked entry has the path Right, Match, Left, Right. What term is it?
   Show answer

   A plain, B eliminated, C complemented, D plain: ACD.
3. Build the tree for F(A, B, C) = Σm(0, 1, 2, 3, 7). Which matched entries are collected, and which survive the containment test?
   Show answer

   Root (split on A): Left 0, 1, 2, 3; Right 3 (was 7). Match (3, 7), whose path Match, Right, Right gives BC. In the Left branch, splitting on B gives Left 0, 1 and Right 0, 1 (were 2, 3): matches (0, 2) and (1, 3). Those two then match each other at C, giving (0, 1, 2, 3) with path Left, Match, Match = A. Further down, the pairs (0, 1) = AB and (2, 3) = AB are also formed and never checked, so they are collected too — and then discarded, because both are contained in A. Prime implicants: A and BC; both are essential, so F = A + BC.
4. Why must a checked number be copied into the next level’s lists?
   Show answer

   Because it can still form a prime implicant with a different partner. In the worked example, 4 and 5 were both checked, yet their pair is the prime implicant AB. If checked entries were dropped, that term would never be generated.
5. After building a tree you find that no minterm was checked more than once. What does that tell you about the chart?
   Show answer

   Every minterm lies in exactly one prime implicant, so every prime implicant is essential: the chart has nothing to choose and the answer is the OR of all of them.