Why are sum-of-products implementations more popular than product-of-sums implementations?

Question

In my book about circuit design (Fundamentals of Digital Logic with VHDL from Stephen Brown and Zvonko Vranesic), the writers always prefer a sum-of-product for representing and implementing simple circuits.

In Boolean Algebra, this preference is used as well, but I think mostly because writing sum-of-products is just easier and shorter. And maybe easier to understand for readers.

But when implementing using logic gates I would suppose other considerations than these are made as well. Like costs and delays of the gates.

So, is there a specific reason why preferably sum-of-products implementations are made? F.e. are AND-gates cheaper than OR-gates? I read about the transistor realisation of these gates, but I can't recall such a statement.

Answer 1

From what I learned in my digital logic courses, everything tends to be made with NAND, since they are cheaper and any Boolean function can be realized with NAND (or NOR, for that matter). I'd imagine that sum-of-products implementations (AND and OR gates) aren't particularly ubiquitous due to this.

Answer 2

Although product-of-sums and sum-of-products have essentially equivalent complexity (one can be transformed into the other by inverting all inputs and outputs), I think most people find sum-of-products easier to work with. For example, suppose a ROM chip is supposed to be selected at memory addresses [during which MREQ will be active] at 0xC000-0xFFFF, and is also supposed to be selected at address 0x0000-0x3FFF if BANKSEL is not set. Its selection equation could be written in sum-of-products form as:

UseROM = (MREQ & A15 & A14) # (MREQ & !A15 & !A14 & !BANKSEL)

The corresponding product-of-sums form, assuming the same output polarity, would be

UseROM = MREQ & (A15 # !A14) & (!A15 # A14) & (A14 # !BANKSEL)

Sum-of-products form effectively identifies the circumstances where the output should be active, while product-of-sums effectively identifies the circumstances where the output should be inactive. In the former, there are two product terms, each of which is clearly associated with access in one of the two ranges. In the latter, there are four factors, only one of which has an obvious relationship with the desired behavior. One could invert the sense of the inputs and outputs and get something more like the former:

DontUseROM = (!MREQ # !A15 # !A14) & (!MREQ # A15 # A14 # BANKSEL)

That will reduce the complexity to match the first example, but it's far less intuitive. Indeed, the only way to make sense of it is to figure out what must happen for DontUseROM to go low, i.e. EITHER the first OR the second factor must go low. And each factor will only go low when the inputs meet ALL conditions needed for that to happen. In other words, back to sum-of-products.

Answer 3

Inverted logic can be unnatural. Let's move over to quantified logic:

$$\forall x:({duck}(x)\land {quacks}(x))\lor ({dog}(x)\land {barks}(x))\lor(\lnot {duck}(x)\land\lnot{dog}(x))$$

"Everything is either a duck (and quacks), or a dog (and barks) or else it is neither duck nor dog."

If write down the dual, and then use DeMorgan's on it to flip the logic, we get something unnatural:

Dual (so far so good):

$$\lnot\exists x:\lnot((({duck}(x)\land {quacks}(x))\lor ({dog}(x)\land {barks}(x))\lor(\lnot {duck}(x)\land\lnot{dog}(x)))$$

DeMorgan's, step 1:

$$\lnot\exists x:\lnot(({duck}(x)\land {quacks}(x))\land\lnot({dog}(x)\land {barks}(x)\land\lnot(\lnot {duck}(x)\land\lnot{dog}(x))$$

step 2:

$$\lnot\exists x:(({\lnot duck}(x)\lor {\lnot quacks}(x))\land({\lnot dog}(x)\lor {\lnot barks}(x)\land({duck}(x)\lor{dog}(x))$$

"There does not exist a thing which, simultaneously:

• is either a non-quacker or a non-duck; and
• is either a non-barker or a non-dog; and
• is either a duck or a dog, or both."

Say what? :)

Sum-of-products goes hand in hand with divide-and-conquer. A sum-of-products representation of a proposition divides it into all the cases which independently make it true. Proposition P is true if such and such; or some situation; or if that other case. Division into independent cases assists clarity in reasoning.

Furthermore, in predicate logic and related reasoning, we usually deal with positives, like "duck", and less with negatives like "non-duck". "non-duck" is not a class of object. Things are classified using positive attributes that they do have, not what they don't have. The space of things which are "non-duck" is unbounded. Reasoning with such negatives is confusing.

In propositional logic, as in zeroth order logic without quantifiers, like what we deal with in logic circuits, we can write down the complete truth table. It may turn out that the negative space of a function is in fact simpler to characterize.

For instance a boolean formula over four variables has only a 16 row table. Suppose there are three rows for which it is true, and it is false everywhere else. Then a simple formula is produced by giving those three combinations of four variables, and combine them with or.

But suppose that the formula is only false in three rows. Then it may be more convenient and natural to characterize these exceptions, and express it that way: the formula is true when the variables are not in this combination, and not in this other combination, and not in this third combination. The not operators can then distribute into the combinations, yielding a product over sums.

Positive example:

A B C D  P
0 0 0 0  0 
0 0 0 1  0
0 0 1 0  0
0 0 1 1  0
0 1 0 0  1 *
0 1 0 1  0
0 1 1 0  0
0 1 1 1  1 *    Sum of products:
1 0 0 0  0      P = A'BC'D' + A'BCD + ABC'D
1 0 0 1  0
1 0 1 0  0
1 0 1 1  0
1 1 0 0  0
1 1 0 1  1 *
1 1 1 0  0
1 1 1 1  0

Negative example:

A B C D  P
0 0 0 0  1 
0 0 0 1  1
0 0 1 0  1
0 0 1 1  1
0 1 0 0  0 *
0 1 0 1  1
0 1 1 0  1
0 1 1 1  0 *    Product of sums:
1 0 0 0  1      P = (A'BC'D' + A'BCD + ABC'D)'
1 0 0 1  1      P = (A'BC'D')'(A'BCD)'(ABC'D)'
1 0 1 0  1      P = (A + B' + C + D)(A + B' + C' + D')(A' + B' + C + D')
1 0 1 1  1
1 1 0 0  1      Sum of products:
1 1 0 1  0 *    A'B'C'D' + A'B'C'D + A'B'CD' ... (10 more terms)
1 1 1 0  1
1 1 1 1  1

Even so, in spite of its simplicity, it is somewhat hard to understand the third formula (product-of-sums) compared to the second (product-of-negated-products). However, the alternative unsimplified sum of 13 products is also hard to understand, due to the large number of terms.

Answer 4

First of all: as others said, it's possible to implement all the logic functions using uniquely NAND or NOR gates.

Now, because of its static CMOS implementation, the NAND gate tends to be faster than the NOR. That's because the NAND gate has the critical path as a series of N nMOS transistors, where N is the fan-in:

The NOR, instead, has the critical path with a series of N pMOS transistors.

In the same conditions, due to the lower mobility of holes than electrons, pMOS are less conductive than nMOS, and therefore is preferable to use NAND gates.

Answer 5

the propagation delay to the AND gate is less than OR gate so implementing logic in SOP is better than POS. Second point is cost of the gate, AND gate is cheaper than OR gate.