4. Canonical Forms and Minimization // Switching Theory and Logic Design // bhaswanth

4.1 SOP and POS: the two canonical forms

Any Boolean function of $n$ variables can be written in two standardized ways.

Sum-of-products (SOP) is an OR (sum) of ANDs (products). Each product is a minterm, an AND of every variable in either true or complemented form. A 3-variable function can have minterms $\bar{A}\bar{B}\bar{C}$ , $\bar{A}\bar{B}C$ , …, $ABC$ . There are $2^n$ possible minterms; we list only the ones for which the function is 1. Sum them with OR.

Example: $f(A,B,C) = \bar{A}\bar{B}C + \bar{A}B\bar{C} + ABC$ , which is the same as $f = m_1 + m_2 + m_7$ , or compactly $f = \sum m(1, 2, 7)$ . The numbering encodes the input combination as a binary index.

Product-of-sums (POS) is an AND (product) of ORs (sums). Each sum is a maxterm, an OR of every variable. We list the maxterms for which the function is 0 and AND them. (The duality of SOP and POS is exact: minterms and maxterms are complementary.)

Same function: $f = (A + B + C)(A + \bar{B} + \bar{C})(\bar{A} + B + C)(\bar{A} + B + \bar{C})(\bar{A} + \bar{B} + C)$ , listing the five input combinations where $f = 0$ .

Why two forms? Because either maps directly to a two-level gate-level realization. SOP becomes AND gates feeding an OR gate (or NAND-NAND after De Morgan). POS becomes OR gates feeding an AND gate (NOR-NOR after De Morgan). When silicon area or speed budgets favor one form, we pick that one. Most textbooks lean SOP because it tends to read more naturally; POS sometimes gives smaller results for functions that are mostly 1.

4.2 Karnaugh maps (K-maps)

A K-map is a graphical aid for minimizing functions of up to about 5 or 6 variables. It is a 2D grid where adjacent cells differ in only one variable. We mark the cells corresponding to minterms that should be 1, then group those 1s into rectangular blocks of size 1, 2, 4, 8, 16. Each block becomes a single product term in the simplified expression.

The Gray-code ordering is what makes the trick work. In a 3-variable map for $f(A, B, C)$ , the columns are labeled BC = 00, 01, 11, 10 (Gray order) rather than 00, 01, 10, 11 (natural binary order). The Gray ordering guarantees that horizontally adjacent cells differ in only one of B or C, and vertically adjacent cells differ only in A. So any rectangle of size $2^k$ cells corresponds to a product term where exactly $k$ variables drop out (because they vary across the rectangle) and the remaining $n - k$ stay constant.

3-variable K-map:

plaintext

          BC=00 | BC=01 | BC=11 | BC=10
   A=0  |  m0   |  m1   |  m3   |  m2
   A=1  |  m4   |  m5   |  m7   |  m6

4-variable K-map:

plaintext

              CD=00 | CD=01 | CD=11 | CD=10
   AB=00 |   m0   |  m1   |  m3   |  m2
   AB=01 |   m4   |  m5   |  m7   |  m6
   AB=11 |  m12   |  m13  |  m15  |  m14
   AB=10 |   m8   |   m9  |  m11  |  m10

The map wraps around at the edges. The cell at AB=00 / CD=00 is logically adjacent to AB=00 / CD=10 (right edge wraps to left), and AB=00 / CD=00 is adjacent to AB=10 / CD=00 (top wraps to bottom). Conceptually, the map is a torus, a donut. A rectangle that wraps from the right edge around to the left edge, or top to bottom, is just as valid a group as one in the middle.

Procedure:

Mark 1s in the cells corresponding to minterms.
Group adjacent 1s into rectangles of size $2^k$ . Bigger rectangles win: they eliminate more variables.
Every 1 must be covered by at least one rectangle.
Each rectangle becomes a product term: variables that are constant across the rectangle stay (in true form if they are 1, complemented if they are 0); variables that vary drop out.
OR the product terms.

Worked example. $f(A, B, C) = \sum m(0, 1, 2, 3, 5, 7)$ . Fill the K-map:

plaintext

          BC=00 | BC=01 | BC=11 | BC=10
   A=0  |   1   |   1   |   1   |   1
   A=1  |   0   |   1   |   1   |   0

The whole top row (4 ones) groups together as one big rectangle. Across the rectangle, $A = 0$ stays constant; $B$ and $C$ both vary. So the rectangle gives the term $\bar{A}$ .

The right pair of cells in the bottom row, $m_5$ and $m_7$ , group: $A = 1$ and $C = 1$ in both, $B$ varies. Term: $AC$ .

So $f = \bar{A} + AC$ . By absorption ( $X + \bar{X}Y = X + Y$ , applied with $X = \bar A$ and $Y = C$ ), this further reduces to $\bar{A} + C$ . Compare to the original 6-term canonical SOP: dramatically simpler.

rendering diagram...

4.3 Implicants and prime implicants

Some vocabulary, because it shows up in synthesis tools and exam questions:

An implicant is any product term that, when 1, forces $f$ to be 1. Every minterm of $f$ is an implicant; so is any group covering only 1s on the K-map.
A prime implicant is an implicant that cannot be merged into a larger implicant by combining with adjacent ones. On the K-map, a prime implicant is a rectangle that cannot be made bigger.
An essential prime implicant is a prime implicant that covers a 1 not covered by any other prime implicant. You must include essential prime implicants in the minimal solution because that 1 has no other home.

Minimization strategy: identify all prime implicants, then select essential ones first. Cover any remaining 1s with the smallest set of additional prime implicants.

4.4 Don't-care conditions

Sometimes the function value is irrelevant for certain inputs. Maybe those input combinations cannot occur in the system, or maybe you simply do not care what the output is for them. Mark these cells with X. When grouping, you can include X cells if it helps form a bigger group, or exclude them if it does not.

Worked example: BCD-to-7-segment decoder. A BCD digit takes values 0–9, so cells 10–15 of a 4-input K-map are don't-cares. Including these X's in groups can dramatically simplify the equations for each segment. The 74LS47 chip's logic was designed exactly this way: each of the seven outputs has a K-map in which the don't-cares were ruthlessly exploited.

Don't-cares are gold. Every digital designer learns to milk them. They appear naturally whenever an input space is larger than the legal subset of inputs.

4.5 The Quine-McCluskey algorithm

For functions of more than 5–6 variables, K-maps become unwieldy (a 6-variable map is two 5-variable maps stacked, which is two 4-variable maps stacked, which is hard to draw, and 7+ variables is hopeless on paper).

The Quine-McCluskey algorithm systematizes minimization in tabular form:

List all minterms of the function in binary, grouped by their number of 1s.
Compare adjacent groups. Any pair that differs in exactly one bit can be merged (the differing bit becomes a "-"). This is the K-map adjacency rule, generalized.
Repeat until no more merges are possible. The remaining unmerged terms are the prime implicants.
Build a prime-implicant chart: rows are prime implicants, columns are original minterms. Mark which prime implicants cover which minterms.
Identify essential prime implicants (those covering a minterm uniquely) and select. Cover remaining minterms with the smallest additional set of primes.

Quine-McCluskey is what synthesis tools used to use. Modern tools use Espresso, an heuristic descendant developed at IBM and Berkeley in the 1980s, that scales to thousands of variables. You will rarely run Quine-McCluskey by hand outside an exam, but it is worth doing once, on a 4-variable example, to see how it produces the same answer as a K-map without any visual pattern recognition.

4.6 A security note on minimization

Minimization affects more than gate count. Different circuit topologies for the same logical function leak different amounts of information through side channels. A heavily-minimized AES S-box implementation might toggle fewer transistors per round, drawing characteristic power that correlates well with intermediate values. A "wasteful" implementation with redundant logic might toggle more uniformly and leak less.

Side-channel-resistant logic styles (WDDL, MDPL, dual-rail logic) deliberately use more gates than minimal, ensuring every signal transition has a complementary transition that balances power draw. The minimal SOP form is the worst case: every cube is a sharp pulse of activity tied to one input pattern. Whenever you see a hardware crypto implementation use seemingly redundant logic, that is the reason.