Canonical normal form

Minterms are often numbered by a binary encoding of the complementation pattern of the variables, where the variables are written in a standard order, usually alphabetical. This convention assigns the value 1 to the direct form (${\displaystyle x_{i}}$) and 0 to the complemented form (${\displaystyle x'_{i}}$); the minterm is then ${\displaystyle \sum \limits _{i=1}^{n}2^{i-1}\operatorname {value} (x_{i})}$. For example, minterm ${\displaystyle abc'}$ is numbered 110₂ = 6₁₀ and denoted ${\displaystyle m_{6}}$.

A given minterm n gives a true value (i.e., 1) for just one combination of the input variables. For example, minterm 5, a b' c, is true only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 1.

Given the truth table of a logical function, it is possible to write the function as a "sum of products". This is a special form of disjunctive normal form. For example, if given the truth table for the arithmetic sum bit u of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci:

Observing that the rows that have an output of 1 are the 2nd, 3rd, 5th, and 8th, we can write u as a sum of minterms ${\displaystyle m_{1},m_{2},m_{4},}$ and ${\displaystyle m_{7}}$. If we wish to verify this: ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)}$ evaluated for all 8 combinations of the three variables will match the table.

Each maxterm is assigned an index based on the opposite conventional binary encoding used for minterms. The maxterm convention assigns the value 0 to the direct form ${\displaystyle (x_{i})}$ and 1 to the complemented form ${\displaystyle (x'_{i})}$. For example, we assign the index 6 to the maxterm ${\displaystyle a'+b'+c}$ (110) and denote that maxterm as M₆. Similarly M₀ of these three variables is ${\displaystyle a+b+c}$ (000) and M₇ is ${\displaystyle a'+b'+c'}$ (111).

It is apparent that maxterm n gives a false value (i.e., 0) for just one combination of the input variables. For example, maxterm 5, a′ + b + c′, is false only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 0.

If one is given a truth table of a logical function, it is possible to write the function as a "product of sums". This is a special form of conjunctive normal form. For example, if given the truth table for the carry-out bit co of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci:

Observing that the rows that have an output of 0 are the 1st, 2nd, 3rd, and 5th, we can write co as a product of maxterms ${\displaystyle M_{0},M_{1},M_{2}}$ and ${\displaystyle M_{4}}$. If we wish to verify this:

${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}=(ci+x+y)(ci+x+y')(ci+x'+y)(ci'+x+y)}$

evaluated for all 8 combinations of the three variables will match the table.

A set of 8 NOR gates, if their inputs are all combinations of the direct and complement forms of the 3 input variables ci, x, and y, always produce minterms, never maxterms—that is, of the 8 gates required to process all combinations of 3 input variables, only one has the output value 1. 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.

The reason this is not a problem is the duality of minterms and maxterms, i.e. each maxterm is the complement of the like-indexed minterm, and vice versa.

In the minterm example above, we wrote ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}}$ but to perform this with a 4-input NOR gate we need to restate it as a product of sums (PoS), where the sums are the opposite maxterms. That is,

${\displaystyle u(ci,x,y)=\mathrm {AND} (M_{0},M_{3},M_{5},M_{6})=\mathrm {NOR} (m_{0},m_{3},m_{5},m_{6}).}$

In the maxterm example above, we wrote ${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$ but to perform this with a 4-input NOR gate we need to notice the equality to the NOR of the same minterms. That is,

${\displaystyle co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0},m_{1},m_{2},m_{4}).}$

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. There's no difficulty about the addends x and y in this respect, because they are static throughout the addition and thus are normally held in latch circuits that routinely have both direct and complement outputs. (The simplest latch circuit made of NOR gates is a pair of gates cross-coupled to make a flip-flop: the output of each is wired as one of the inputs to the other.) There is also no need to create the complement form of the sum u. However, the carry out of one bit position must be passed as the carry into the next bit position in both direct and complement forms. The most straightforward way to do this is to pass co through a 1-input NOR gate and label the output co′, but that would add a gate delay in the worst possible place, slowing down the rippling of carries from right to left. An additional 4-input NOR gate building the canonical form of co′ (out of the opposite minterms as co) solves this problem.

${\displaystyle co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3},m_{5},m_{6},m_{7}).}$

The trade-off to maintain full speed in this way includes an unexpected cost (in addition to having to use a bigger gate). If we'd just used that 1-input gate to complement co, there would have been no use for the minterm ${\displaystyle m_{7}}$, and the gate that generated it could have been eliminated. Nevertheless, it is still a good trade.

Now we could have implemented those functions exactly according to their SoP and PoS canonical forms, by turning NOR gates into the functions specified. A NOR gate is made into an OR gate by passing its output through a 1-input NOR gate; and it is made into an AND gate by passing each of its inputs through a 1-input NOR gate. However, this approach not only increases the number of gates used, but also doubles the number of gate delays processing the signals, cutting the processing speed in half. 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. That's the "top-down" way to design the digital circuit for this function, but is it the best way? 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. In such a case, a designer may develop the canonical-form design as a baseline, then try a bottom-up development, and finally compare the results.

The bottom-up development involves noticing that u = ci XOR (x XOR y), where XOR means eXclusive OR [true when either input is true but not when both are true], and that co = ci x + x y + y ci. One such development takes twelve NOR gates in all: six 2-input gates and two 1-input gates to produce u in 5 gate delays, plus three 2-input gates and one 3-input gate to produce co′ in 2 gate delays. The canonical baseline took eight 3-input NOR gates plus three 4-input NOR gates to produce u, co and co′ in 2 gate delays. If the circuit inventory actually includes 4-input NOR gates, the top-down canonical design looks like a winner in both gate count and speed. 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. Does that design simply never need the direct form of the carry out? Well, yes and no. 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). That's because those calculations overlap, each in what amounts to its own little pipeline without affecting when the next bit position's sum bit can be calculated. 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. But using 3-input NOR gates, the bottom-up design is very nearly as fast for doing parallel addition on a non-trivial word length, cuts down on the gate count, and uses lower fanouts ... so it wins if gate count and/or fanout are paramount!

We'll leave the exact circuitry of the bottom-up design of which all these statements are true as an exercise for the interested reader, assisted by one more algebraic formula: u = ci(x XOR y) + ci′(x XOR y)′]′. Decoupling the carry propagation from the sum formation in this way is what elevates the performance of a carry-lookahead adder over that of a ripple carry adder.