Minimisation and Canonical Forms

Doing More with Fewer Gates

A boolean function can be written in many equivalent forms, and a simpler expression means a cheaper, faster circuit — fewer gates, less delay, less power. Minimisation is finding an equivalent expression with as few terms and literals as possible.

Two canonical forms name a function unambiguously. Sum-of-products (SOP) is an OR of AND terms (like $A\overline{B} + \overline{A}B$). Product-of-sums (POS) is an AND of OR terms. Canonical forms are useful as a starting point, but they are usually not minimal.

Two tools do the simplifying:

• Boolean algebra applies the identities directly. For instance, $AB + A\overline{B} = A(B + \overline{B}) = A \cdot 1 = A$ — two terms collapse to one because the $B$ variable is redundant.
• The Karnaugh map (K-map) is a visual method: a grid arranged so that adjacent cells differ in exactly one variable. You circle groups of adjacent 1s (in powers of two: 1, 2, 4, 8 cells), and each group becomes one simplified term. Larger groups eliminate more variables, so bigger circles mean simpler expressions. K-maps make it easy to spot simplifications the eye would miss in algebra.

The payoff is concrete: a function that naively needs a dozen gates may reduce to three. In an era of billions of transistors this still matters — minimisation reduces power and delay at every level, and the same idea (finding the simplest equivalent form) recurs throughout computing.

Common pitfall: in a Karnaugh map, circling groups whose size is not a power of two, or missing the map's wrap-around adjacency (the left and right edges, and top and bottom, are neighbors). Valid K-map groups must contain exactly $1, 2, 4, 8, \dots$ cells and may wrap around the edges — overlooking either yields a non-minimal or incorrect result.