Logic Simplification with K-maps

Abstract

Two-level logic simplification minimizes the literal and gate count of Boolean functions to reduce physical silicon area, power dissipation, and propagation delay. The fundamental mechanism driving simplification is the Uniting Theorem ($A{B}^{\prime }+AB=A$). Geometric abstractions—such as Boolean Cubes and Karnaugh Maps (K-Maps) utilizing Gray code ordering—allow adjacent minterms that differ by a single variable to be combined visually. By incorporating Don’t Care ($X$) conditions and systematically identifying Prime Implicants (PIs) and Essential Prime Implicants (EPIs), complex switching functions can be reduced to minimal Sum-of-Products (SOP) forms.

---

Key to Simplification: The Uniting Theorem

The algebraic cornerstone of all two-level logic minimization is the Uniting Theorem:

$$A\cdot B^{\prime }+A\cdot B=A(B^{\prime }+B)=A\cdot (1)=A$$

The Uniting Principle

If two product terms in the ON-set differ in exactly one variable (one appears in true form, the other in complemented form), that varying variable can be eliminated, leaving a single product term with one fewer literal to represent both elements.

Visualizing the Uniting Theorem combining two terms differing in a single bit.

---

Geometric Abstraction: Boolean Cubes

A Boolean Cube is a geometric representation of an $n$-variable Boolean space as an $n$-dimensional hypercube ($n$-cube):

• Vertices (Nodes): Represent individual minterms ($2^n$ nodes for $n$ variables).
• Edges: Connect nodes that differ by exactly one variable bit (Hamming distance = 1).
• Node Types:
  • ON-set ($1$): Represented as solid nodes.
  • OFF-set ($0$): Represented as empty nodes.
  • DC-set ($X$): Represented as X’d nodes.

1-cube, 2-cube, 3-cube, and 4-cube topologies.

Applying the Uniting Theorem to merge adjacent solid nodes into subcube faces.

---

Karnaugh Maps (K-Maps) & Gray Code Adjacency

A Karnaugh Map (K-Map) is a flattened 2D planar projection of a Boolean hypercube designed to make adjacencies visually obvious.

Gray Code Indexing

K-Map rows and columns are arranged using Gray code sequences (where adjacent cells differ by only one bit), rather than standard binary count order:

$$\text{Gray Code Sequence: }00\to 01\to 11\to 10$$

Boundary Wraparound

Adjacency in a K-Map wraps around the outer borders. The leftmost column is adjacent to the rightmost column, and the top row is adjacent to the bottom row. The four corners of a 4-variable map are also mutually adjacent.

3-Variable K-Map layout showing Gray Code column indexing ($00,01,11,10$).

3-Variable K-Map highlighting a 2-cube subcube representing the literal $A$.

---

Incompletely Specified Functions & Don’t Cares ($X$)

In many digital circuits, certain input combinations either cannot occur or their outputs do not affect system behavior. These conditions are represented as Don’t Care ($X$) values.

Sources of Don’t Cares

1. Unused Input Patterns: BCD (Binary Coded Decimal) uses 4 bits to represent decimal digits $0\dots 9$; the binary patterns $1010_2\dots 1111_2$ (10–15) never occur.
2. Ignored Outputs: A decoder driving a 7-segment display does not care about output values for illegal inputs $>9$.

Optimization Role

Don’t cares ($X$) can be treated as either $1$ or $0$:

• Assign $X=1$ if it helps group $1$s into a larger subcube (eliminating literals).
• Assign $X=0$ if it does not contribute to forming a larger subcube.

Specifying Boolean Functions

A Boolean function is fully specified by declaring any 2 out of 3 sets:

• ON-set ($\Sigma m$): All input conditions yielding output $1$.
• OFF-set ($\Pi M$): All input conditions yielding output $0$.
• Don’t Care set ($DC$ / $d$): All input conditions yielding output $X$.

$$F(A,B,C,D)=\Sigma m(1,3,7,11)+d(0,2,5)$$

---

Subcubes, Dimensionality & Literal Reduction

Groupings of adjacent cells in a K-Map are called subcubes. Every subcube must contain a number of cells equal to a power of 2 ($1,2,4,8,16\dots$).

For an $n$-variable function, an $m$-dimensional subcube ($m\le n$) contains $2^m$ cells and reduces the literal count of that product term to $n-m$ literals:

Subcube Dimension ($m$)	Number of Cells ($2^m$)	Literal Count in Term	Visual Representation (3-Variable / 4-Variable)
0-cube	$1$	$n$ literals	Single isolated minterm node
1-cube	$2$	$n-1$ literals	Line of 2 adjacent cells
2-cube	$4$	$n-2$ literals	Rectangle/Square plane of 4 cells
3-cube	$8$	$n-3$ literals	Block of 8 cells
$n$-cube	$2^n$	$0$ literals	Full map (constant function $F=1$)

Golden Rule of Grouping

To achieve minimal hardware, find the smallest number of the largest possible subcubes that completely cover the ON-set.

---

Fundamental Implicant Terminology

Term	Definition	Key Characteristics
Implicant	Any single cell or valid subcube grouping ($2^m$ cells) composed strictly of ON-set ($1$) and/or DC-set ($X$) elements.	Represents a valid product term that implies the function.
Prime Implicant (PI)	An implicant that cannot be combined with any adjacent subcube to form a larger subcube.	Represents a maximally expanded product term (minimum literals).
Essential Prime Implicant (EPI)	A Prime Implicant that covers at least one ON-set ($1$) element that is not covered by any other Prime Implicant.	Must be included in every minimal SOP expression.

Don't Cares and Essentiality

Don’t Care ($X$) cells are used to expand implicants into Prime Implicants, but a PI that covers only $X$ cells (and no unique $1$ cell) is never essential and is excluded from the final cover.

---

Systematic Algorithm for Two-Level Logic Simplification

To find the minimum SOP expression from a K-Map:

flowchart TD
    Start([Start K-Map Minimization]) --> Step1["1. Locate all 1s and Xs on the map"]
    Step1 --> Step2["2. Form all PRIME IMPLICANTS (PIs)<br/><i>Expand 1s into largest subcubes of 1s/Xs in powers of 2</i>"]
    Step2 --> Step3["3. Identify ESSENTIAL PRIME IMPLICANTS (EPIs)<br/><i>Find 1s covered by ONLY ONE Prime Implicant</i>"]
    Step3 --> Step4["4. Add all EPIs to final SOP expression"]
    Step4 --> Decision{"5. Are all 1s covered?"}

    Decision -- Yes --> Done([Done: Output Minimal SOP])
    Decision -- No --> Step6["6. Select MINIMAL set of remaining PIs<br/><i>Cover remaining 1s prioritizing maximum overlap</i>"]
    Step6 --> Done

Algorithmic Execution Steps

1. Find All Prime Implicants (PIs):
   • For every $1$ on the map, construct all maximal groupings of adjacent $1$s and $X$s (considering edges, columns, rows, and 4-corner wraps).
2. Identify Essential Prime Implicants (EPIs):
   • Inspect each $1$ cell on the map. If a $1$ is covered by exactly one PI, that PI is Essential.
   • Mark all EPIs and include them in the final equation.
3. Cover Remaining Uncovered $1$s:
   • Mark all $1$s already covered by the selected EPIs.
   • If any $1$s remain uncovered, select the smallest set of remaining PIs that covers all remaining $1$s.

---

Related Notes

• Number Systems and Boolean Algebra
• Combinational Logic Design
• Canonical Representation
• Mux & Demux
• Encoder & Decoder
• Adders & Subtractors
• Digital Systems