Gate-Level Minimization#

Review#

We can use sum of minterm create logic equation, and we can use it to draw a schematic.

For example, we want to determine whether the input is a prime number ( $n<16$ ), we can have the following sum of minterm Canonical Form:

f = \sum_{(d, c, b, a)}m(1, 2, 3, 5, 7, 11, 13)

Futhermore, we can draw a schematic logic diagram like this: Can we optimize the number of gates that we need to use?

Gate-level Minimization#

Refers to the design task of finding an optimal gate-level implementaition of Boolean functions describing a digital circuit.

The strategy is finding a design represented as a collection of primitive logic gates and functions and the connections between them.

Two-Level Logic#

For example, SOP/POS is a two-level logic circuit. You can see both of them only have two layers.

Now, we try to simplify our boolean function, i.e., we try to write Sum Of Products (or Product Of Sum) in the simplest form.

Logic minimization method#

Using truth table and boolean algebra’s theorem to simplify our function, but it lacks specific rules.

Kamaugh map#

A diagram made up of squares, each square represents one minterm. Here is its properties:

A simple straight forward procedure
A pictorial form of a truth table
Applicable if the # of variables < 7

K - Map#

Every square that is adjacent to four directions are different in only one digit (gray code).
For more variables, if we are able to draw a rectangle with edges that its lengths are $2^n$ (for example, (1, 4), (2, 8), …), then we can simplify this term.

Two variables#

For two variables, we will have $2^2=4$ minterms.

X\Y	0	1
0	$m_0 = \bar X\bar Y$	$m_1 = \bar XY$
1	$m_2 = X\bar Y$	$m_3 = XY$

For example, we want to simplify

G=\bar XY+X\bar Y+XY

then we first draw a K-map: Second, we draw valid rectangles to simplify:

So the following result will be:

G = X+Y

Three variables#

For three variables, we will have $2^3=8$ minterms.

X\YZ	00	01	11	10
0	$m_0 = \bar X\bar Y\bar Z$	$m_1 = \bar X\bar YZ$	$m_3 = \bar XYZ$	$m_2 = \bar XY\bar Z$
1	$m_4 = X\bar Y\bar Z$	$m_5 = X\bar YZ$	$m_7 = XYZ$	$m_6 = XY\bar Z$

For example, we want to simplify

G=\Sigma m(0, 2, 4, 5, 6)

so first we draw K-map: Second, still draw valid rectangle, here, we can add spporting description (gray text) to figure out what is the outcome of any rectangle:

So the following result will be:

G=XY'+Z'

Four variables#

For four variables, we will have $2^4=16$ minterms.

WX\YZ	00	01	11	10
00	$m_0 = \bar W\bar X\bar Y\bar Z$	$m_1 = \bar W\bar X\bar YZ$	$m_3 = \bar W\bar XYZ$	$m_2 = \bar W\bar XY\bar Z$
01	$m_4 = \bar WX\bar Y\bar Z$	$m_5 = \bar WX\bar YZ$	$m_7 = \bar WXYZ$	$m_6 = \bar WXY\bar Z$
11	$m_{12} = WX\bar Y\bar Z$	$m_{13} = WX\bar YZ$	$m_{11} = WXYZ$	$m_{10} = WXY\bar Z$
10	$m_8 = W\bar X\bar Y\bar Z$	$m_9 = W\bar X\bar YZ$	$m_{15} =W\bar XYZ$	$m_{14} = W\bar XY\bar Z$

For example, we want to simplify

F(W,X,Y,Z)=\Sigma m(0, 1, 2, 3, 4, 5, 6, 8, 9, 12, 13, 14)

so first we draw K-map:

Second, still draw valid rectangle, still using spporting description (gray text) to figure out what is the outcome of any rectangle:

So the following result will be:

F(W, X, Y, Z)=W'X'+XZ'+Y'

Extra definition#

Since the rectangle we draw may be arbitrary, so we have these few definitions: Info:

Minterm A product term that includes every input variable or its complement. It is actually every square on K-map.
Implicant A product term that if true implies the function is true. Shortly speaking, it is the rectangle we draw.
Prime Implicant (PI) An implicant that cannot be made any larger and still be an implicant.
Essential Prime Implicant (EPI) The only prime implicant that contains a particular minterm of the function.
Redundant Prime Implicant (RPI) The prime implicants for which each of its minterm is covered by some essential prime implicant.
Selective Prime Implicant (SPI) The prime implicants for which are neither essential nor redundant prime implicants.

Here, lets look at some examples: $\begin{cases}PI = 1, 2, 3, 4, 5 \\EPI = 1, 2, 3, 4 \\RPI = 5 \\SPI =\end{cases}$

$\begin{cases}PI = 1, 2, 3, 4, 5, 6 \\EPI = \\RPI = \\SPI =1, 2, 3, 4, 5, 6 \end{cases}$

Strategy of cover a function#

Success:

Start with an empty cover.
Add all EPI to the cover.
For each remaining uncovered minterm, add the largest implicant to cover it.

With this strategy, we can obtain Good cover, which is no guarantee it is the lowest-cost cover.

Don’t cares#

Sometimes, the value of some function is not specified for certain combinations of variables, we call this function Incompletely Specified Function. The don’t care conditions can be utilized in logic minimization. (use $\Sigma d$ to represent) Let’s look at an example:

Simplify the following function:

F(W,X,Y,Z)=\Sigma m(1, 3, 7, 11, 15)+\Sigma d(0, 2, 5)

First, draw a K-map: Remember, a don’t care means that we can regard it as 1 or 0, so we can circle it or not. What’s more, we can also circle like this: We know that $W'Y+YZ\neq W'X'+YZ$ , but in this situation(with don’t cares), both method is corrent for simplifying this function. Hence, we can get the simplified function:

F(W,X,Y,Z)=W'Y+YZ=W'X'+YZ

Simplified POS#

As we can see, using K-map method we can obtain a simplified output in terms of SOP, so if we want to get the simplified function in terms of POS, we need to do this: Info:

We want to simplified $F$ in terms of POS. Using K-map to find the simplified SOP of $F'$ , the add a negation, then we will have a simplified $F$ in terms of POS.

In shorts, we can do K-map on F but rather than gathering 1, we gathering 0. Here is an example: we want to simplify $F(W,X,Y,Z)$ in terms of POS.

F(W,X,Y,Z)=\Sigma m(0, 1, 2, 3, 4, 5, 6, 8, 9, 12, 13, 14)

First , we draw K-map, but this time we focus on 0. Thus, we can draw a circle like this: So we can rewrite $F'$ :

F(W,X,Y,Z)'=XYZ+WX'Y

We add a negation on it, then we will have:

(F(W,X,Y,Z)')'=F(W,X,Y,Z)=(X'+Y'+Z')(W'+X+Y')

Then we have the answer!

Example — Prime Detector#

Simplify#

As we have in the beginning, we want to design a prime detector for $1$ ~ $2^4-1$ , we can have the SOP form:

f = \sum_{(d, c, b, a)}m(1, 2, 3, 5, 7, 11, 13)

Thus, we use Kmap to simplify our function. Anything is the same as the Kmap above, but here is an implement detail.

In verilog, we will use 0, 1, x to represent the situation of each bit, so for any implicant, we can write it as the situation for each bit.

So we can write the function as:

\begin{align} f(d, c, b, a) &= d'c'b + cb'a + c'ba + d'a\\ &=001x + x101 + x011 + 0xx1 \end{align}

Then we can design a circuit to implement it!

Circuit diagram#

First, lets try to use AND-OR gate. In practice, CMOS gates are always inverting, so the real circuit might use NAND-NAND design instead of AND-OR.

Multi-output circuit optimization#

As we mentioned above, we will try to get as large implicant as possible, but sometimes, if we have multiple output, then non-prime implicants may be shaerd advantageously.

Here is an example: Consider these two function: