The De Morgan dual is the canonical conjunctive normal form (CCNF), maxterm canonical form, or Product of Sums (PoS or POS) which is a conjunction (AND) of maxterms.
variables appears exactly once (either in its complemented or uncomplemented form).
A minterm gives a true value for just one combination of the input variables, the minimum nontrivial amount.
, a maxterm is a sum term in which each of the n variables appears exactly once (either in its complemented or uncomplemented form).
Maxterms are a dual of the minterm idea, following the complementary symmetry of De Morgan's laws.
It is apparent that a maxterm gives a false value for just one combination of the input variables, i.e. it is true at the maximal number of possibilities.
That is, each maxterm is assigned an index based on the opposite conventional binary encoding used for minterms.
In general, there may be multiple minimal SoP forms, none clearly smaller or larger than another.
], in less obvious cases a convenient method for finding minimal PoS/SoP forms of a function with up to four variables is using a Karnaugh map.
Where performance is an issue (as in the Apollo Guidance Computer), the available parts are more likely to be NAND and NOR because of the complementing action inherent in transistor logic.
If the higher voltage is defined as the 1 "true" value, a NOR gate is the simplest possible useful logical element.
Specifically, a 3-input NOR gate may consist of 3 bipolar junction transistors with their emitters all grounded, their collectors tied together and linked to Vcc through a load impedance.
Any input that is a 1 (high voltage) to its base shorts its transistor's emitter to its collector, causing current to flow through the load impedance, which brings the collector voltage (the output) very near to ground.
Only when all 3 input signals are 0 (low voltage) do the emitter-collector impedances of all 3 transistors remain very high.
Then very little current flows, and the voltage-divider effect with the load impedance imposes on the collector point a high voltage very near to Vcc.
The complementing property of these gate circuits may seem like a drawback when trying to implement a function in canonical form, but there is a compensating bonus: such a gate with only one input implements the complementing function, which is required frequently in digital logic.
That's because a NOR gate, despite its name, could better be viewed (using De Morgan's law) as the AND of the complements of its input signals.
That is, One might suppose that the work of designing an adder stage is now complete, but we haven't addressed the fact that all 3 of the input variables have to appear in both their direct and complement forms.
An additional 4-input NOR gate building the canonical form of co′ (out of the opposite minterms as co) solves this problem.
The trade-off to maintain full speed in this way includes an unexpected cost (in addition to having to use a bigger gate).
Consequently, whenever performance is vital, going beyond canonical forms and doing the Boolean algebra to make the unenhanced NOR gates do the job is well worthwhile.
We have now seen how the minterm/maxterm tools can be used to design an adder stage in canonical form with the addition of some Boolean algebra, costing just 2 gate delays for each of the outputs.
The discussion has focused on identifying "fastest" as "best," and the augmented canonical form meets that criterion flawlessly, but sometimes other factors predominate.
The designer may have a primary goal of minimizing the number of gates, and/or of minimizing the fanouts of signals to other gates since big fanouts reduce resilience to a degraded power supply or other environmental factors.
But if (contrary to our convenient supposition) the circuits are actually 3-input NOR gates, of which two are required for each 4-input NOR function, then the canonical design takes 14 gates compared to 12 for the bottom-up approach, but still produces the sum digit u considerably faster.
The fanout comparison is tabulated as: The description of the bottom-up development mentions co′ as an output but not co.
At each stage, the calculation of co′ depends only on ci′, x′ and y′, which means that the carry propagation ripples along the bit positions just as fast as in the canonical design without ever developing co.
The calculation of u, which does require ci to be made from ci′ by a 1-input NOR, is slower but for any word length the design only pays that penalty once (when the leftmost sum digit is developed).
And, to be sure, the co′ out of the leftmost bit position will probably have to be complemented as part of the logic determining whether the addition overflowed.
Most gate circuits accept more than 2 input variables; for example, the spaceborne Apollo Guidance Computer, which pioneered the application of integrated circuits in the 1960s, was built with only one type of gate, a 3-input NOR, whose output is true only when all 3 inputs are false.