02.7 Logic synthesis -- Minterms - Maxterms

Minterms

For a function of $n$ variables, a product term where each variable appears exactly once is called a minterm $m_i$

A $n$-variable minterm can be represented on $n$ bits

If the variable is equal to 0, it appears in the minterm as complemented, else it’s uncomplemented

Example

$n=3,i=5$ → $m_5=x_1\overline{x_2}{x}_3$ because $5=(101{)}_2$

Maxterms

For a function of $n$ variables, a sum term where each variable appears exactly once is called a maxterm $M_i$

Can also be mapped to a $n$ bit integer

If the variable is equal to $0$, then it appears as uncomplemented

Example

$n=3,i=5$ → $M_5=\overline{x_1}+x_2+\overline{x_3}$

Maxterm ←> Minterm

A minterm is the complement of the maxterm, and vice-versa

$m_i={\bar{M}}_i⟺M_i={\bar{m}}_i$

The transformation using DeMorgan’s theorem

Logic synthesis

For a function in the form of a truth table, we have a logic expression obtained by

• The rows in the table where $f=1$ → sum of minterms
• The rows in the table where $f=0$ → product of maxterms

Sum-of-Products (SoP)

SoP: a logical expression consisting of products (AND) that are summed (OR)

(if each product is a minterm : it is canonical)

A good way to estimate the cost of a logical circuit → sum the amount of gates and inputs

Product-of-Sums (PoS)

Similar to SoP, but “reversed”

(if each sum is a maxterm: it is canonical)

So which of the two is better ?

Generally, we look at the cost of the both, and choose which one is less expensive. They won’t necessarily have the same cost

02.8 NAND and NOR Logic Networks