6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hmm, I read how AND and OR gates can be realized with NAND gates, yes. So probably an AND gates requires less NAND's than an OR. Which seems reasonable :P But are NAND's cheaper than NOR's? \$\endgroup\$ – Steven Roose Jun 23 '12 at 18:19
  • 6
    \$\begingroup\$ @StevenRoose In a standard CMOS process, yes. PFETs are usually worse than NFETs, so the PFETs must be larger to match the NFET pull-downs. With a NOR gate, two PFETs are in series and should be doubled in size. For a NAND gate, you would have an active area of say 8-10 units, and a NOR gate would have an area of maybe 14-20 depending on the relative strength of the PFETs and NFETs. \$\endgroup\$ – W5VO Jun 23 '12 at 22:28
  • 1
    \$\begingroup\$ It's worth noting that (a and b) or (c and d) is equivalent to (a nand b) nand (c nand d). \$\endgroup\$ – supercat Sep 15 '15 at 20:49
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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 a dug duck or a dog."

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.

\$\endgroup\$
  • \$\begingroup\$ I would add that even in when things are expressed in product-of-sums form, the normal method of human-evaluating them would be to invert them to yield product of sums. If there does not exist anything meeting all three criteria, that implies that everything must 'fail' at least one; only quacking ducks fail the first, only barking dogs fail the second, and things which are neither dogs nor ducks fail the third. In other words, back to sum-of-products. \$\endgroup\$ – supercat Dec 7 '12 at 16:54
  • \$\begingroup\$ As for your second example, I would suggest that the most natural description would be to describe it in terms of when P is false, using sum-of-products and inverting the result. Even with non-inverted SOP, there's no need for 13 terms. I think only five are needed: !B + C!D + A!D + AC + !A!CD, for example. \$\endgroup\$ – supercat Dec 7 '12 at 17:07
1
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ I think the human-parsing aspects are far more relevant than the distinction between NAND and NOR gates. SOP is equivalent to POS with inputs and outputs inverted, and in many contexts one can invert inputs and outputs "for free". If one has a piece of paper which is white except for a few black rectilinear shapes, one could either describe the paper's contents by describing the dark areas (shapes), or by describing all the white areas (spaces around and between them). In most cases, the former description will be easier. \$\endgroup\$ – supercat Dec 6 '12 at 23:50
  • \$\begingroup\$ @supercat it's true that inversion is almost free, but it's also true that if a pMOS has half the transconductance of an nMOS, a 2-inputs NOR gate will need four times bigger pMOSes to be balanced, and you'll pay with input capacitance. And I think that the human-parsing reason is quite subjective. \$\endgroup\$ – clabacchio Dec 7 '12 at 8:38
  • \$\begingroup\$ On every CPLD I've seen, every input is available in normal and inverted form, and almost every sum-of-products output is too (though some single-product-term outputs aren't), and many logic compilers will in fact translate logic from one form to another when it would make things more efficient (e.g. converting the three-term Q = W # X # (Y & Z) into the two-term !Q = (!W & !X & !Y) # (!W & !X & !Z)). The affinity for sum-of-products isn't based on the hardware, since the choice of hardware representation may not depend upon the source-code representation at all. \$\endgroup\$ – supercat Dec 7 '12 at 16:47
  • \$\begingroup\$ @clabacchio how will you play with capacitance and how does it help in case of the NOR gate? \$\endgroup\$ – Thar Jan 23 '16 at 19:08
0
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Neither of these statements is true in general. Can you back either one up with any sort of reference or citation? \$\endgroup\$ – Dave Tweed Dec 6 '12 at 22:59
  • 1
    \$\begingroup\$ The normal SOP implementation for expressions (A and B) or (C and D) in hardware is far more likely to be (A nand B) nand (C nand D) than to involve positive-logic gates. If one needs an inverted output, the realization (A and B) nor (C and D) may be useful (implemented as a four-input gate that's a cross between nand and nor) but in general, an AND or OR gates must be built up of a NAND or NOR followed by an inverter. \$\endgroup\$ – supercat Dec 6 '12 at 23:45
  • \$\begingroup\$ @supercat how is your comment related to this answer \$\endgroup\$ – Thar Jan 23 '16 at 19:05
  • \$\begingroup\$ @SD7: AND and OR gates are used far less often than NAND, NOR, and hybrid gates; if a circuit described using AND and OR is actually implemented using NAND gates, the propagation delay it would have if implemented using AND and OR gates doesn't seem very relevant. \$\endgroup\$ – supercat Jan 23 '16 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.