Heuristic Based Minimization of Boolean Functions

Overview of Two-Level Minimization

• Minimum Cover: This refers to the cover of a Boolean function consisting of the minimum possible number of implicants. Finding a minimum cover is a global optimum problem.

• Minimal Cover (Irredundant Cover): This is a cover of a function that is not a proper superset of any other cover. In a minimal cover, no single implicant can be removed while still maintaining the coverage of the function's original minterms. This represents a local optimum.

• Minimal w.r.t. 1-Implicant Containment Cover: A weaker local optimum where no single implicant is contained within another single implicant in the cover.

Function Examples and Implementations

• Example Function 1: $f_1 = a'b'c' + a'b'c + ab'c + abc + abc'$

• Example Function 2: $f_2 = a'b'c + ab'c$

• Visual Mappings: The transcript references cube representations (Karnaugh-map-like structures) to visualize covers:

  • Vertices are indexed by binary strings (e.g., $000$, $001$, $010$, $011$, $100$, $101$, $110$, $111$).

  • The covers are identified by Greek letters $\alpha$, $\beta$, $\gamma$, $\delta$, and $\epsilon$.

Fundamental Definitions and Prime Implicants

• Prime Implicant: An implicant that is not contained by any other implicant of the function. Removing any literal from a prime implicant would result in it covering minterms that are not part of the original function.

• Prime Cover: A cover consisting entirely of prime implicants.

• Essential Prime Implicant: A prime implicant that covers at least one minterm which is not covered by any other prime implicant. Essential prime implicants must be included in any minimum cover of the function.

Exact and Heuristic Minimization Methods

• Exact Methods:

  • Goal: Compute the absolute minimum cover.

  • Characteristics: These methods are often computationally difficult or impossible to perform on extremely large functions due to exponential complexity.

  • Fundamental Approach: Most are based on the Quine-McCluskey method.

• Heuristic Methods:

  • Goal: Compute minimal covers, with the hope that they might be the minimum cover.

  • Characteristics: Designed for large-scale practical applications where exact methods fail.

  • Notable Programs: MINI, PRESTO, and ESPRESSO.

• Quine's Theorem: States that there is a minimum cover that consists solely of prime implicants.

  • Consequence: The search space for a minimum cover can be restricted exclusively to the set of prime implicants.

  • Quine-McCluskey Method: Involves two main steps: computing all prime implicants and subsequently determining the minimum cover through a covering table.

Shannon's Decomposition (Boole’s Expansion Theorem)

• Boole's Expansion Theorem: A function $f(x_1, x_2, \dots, x_i, \dots, x_n)$ can be expanded relative to a variable $x_i$ as:

  • $f = x_i f_{x_i=1} + x'_i f_{x_i=0}$

  • This theorem is also widely credited to Claude Shannon.

• Cofactors:

  • Cofactor w.r.t. $x_i$: Represented as $f_{x_i=1} = f(x_1, x_2, \dots, x_i = 1, \dots, x_n)$.

  • Cofactor w.r.t. $x'_i$: Represented as $f_{x_i=0} = f(x_1, x_2, \dots, x_i = 0, \dots, x_n)$.

• Example Calculation: Given $f = ab + bc + ac$:

  • $f_a = b + c$

  • $f_{a'} = bc$

  • Litmus Test: The original function should be reconstructible using the cofactors: $f = a f_a + a' f_{a'}$.

Unateness in Boolean Functions

• Definition: Given a function $f(x_1, x_2, \dots, x_i, \dots, x_n)$.

• Positive Unate: A function is positive unate in $x_i$ if $f_{x_i} \ge f_{x'_i}$.

• Negative Unate: A function is negative unate in $x_i$ if $f_{x_i} \le f_{x'_i}$.

• Unate Function: A function is considered positive/negative unate if it is positive/negative unate in all its variables, respectively.

Boolean Operators and Functional Derivatives

• Boolean Difference (Boolean Derivative): The change of function $f$ with respect to variable $x_i$:

  • $\frac{df}{dx_i} = f_{x_i} \oplus f_{x'_i}$

• Consensus: The product of the cofactors:

  • $C_{x_i} = f_{x_i} \cdot f_{x'_i}$

• Smoothing: The sum of the cofactors:

  • $S_{x_i} = f_{x_i} + f_{x'_i}$

• Example Application ($f = ab + bc + ac$):

  • Boolean Difference w.r.t. $a$: $(b+c) \oplus (bc) = b'c + bc'$

  • Consensus w.r.t. $a$: $(b+c) \cdot (bc) = bc$

  • Smoothing w.r.t. $a$: $(b+c) + (bc) = b + c$

Generalized Expansion Theorem

• Generalized Expansion: A function $f$ can be represented using an orthonormal set of functions $\phi_i$ (where $i = 1, 2, \dots, k$).

  • $f = \sum_{i=1}^k \phi_i \cdot f_{\phi_i}$

  • Here, $f_{\phi_i}$ is the generalized cofactor. Note that generalized cofactors are not unique.

• Complex Operator Expansion: For two functions $f$ and $g$ and a Boolean operator $\odot$:

  • $f \odot g = \sum_{i=1}^k \phi_i \cdot (f_{\phi_i} \odot g_{\phi_i})$

Matrix Representation and Positional Cube Notation

• Logic Minimizer Formats: Minimizers generally use matrix-based formats, typically with one row per implicant.

• Symbols: Standard symbols used are $0$, $1$, and $*$ (don't care).

• Encoding Scheme:

  • $00$: Void (Empty set)

  • $01$: Logic $1$

  • $10$: Logic $0$

  • $11$: Don't Care ($*$)

• Positional Cube Notation (PCN):

  • Uses two bits per symbol.

  • This is more efficient than using standard character types (like bytes).

  • Enables fast, parallelized binary operations:

    • Intersection: Performed using bitwise AND.

    • Supercube: Performed using bitwise OR.

• Example PCN Mapping ($f = a'd' + a'b + ab' + ac'd$):

  • Variables labeled $a, b, c, d$:

  • $a'd' \rightarrow 10\,11\,11\,10$

  • $a'b \rightarrow 10\,01\,11\,11$

  • $ab' \rightarrow 01\,10\,11\,11$

  • $ac'd \rightarrow 01\,11\,10\,01$

Computing Cofactors in PCN

• Recursive Paradigm: Logic cover operations often involve expanding about a variable, applying operations to cofactors, and merging results.

• Step-by-Step Cofactor Computation (Example $f = a'b' + ab$ w.r.t. variable $a$):

  • Represent variable $a$ in binary notation for bits $(a, b)$: $01\,11$.

  • Represent implicant $a'b'$ as $10\,10$.

  • Intersection: Perform bitwise AND between implicant segment and constraint segment.

    • $10\,10$ AND $01\,11 = 00\,10$.

    • Since the first field ($a$) results in $00$, this is Void. This implicant does not contribute to the cofactor.

  • Successful Intersection: For implicant $ab$ ($01\,01$) and constraint $a$ ($01\,11$):

    • $01\,01$ AND $01\,11 = 01\,01$.

  • Inversion and OR: To finalize the cofactor and remove the variable dependency being cofactored, invert the variable bitmask and OR it.

    • The constraint was $a$ ($01$ in the first field). Inverting this field gives $10$.

    • Perform OR on the first field: $01$ OR $10 = 11$ (Don't care/Remove variable).

    • Resulting cofactor row: $11\,01$, which represents variable $b$.

Recursive Tautology Determination

• Objective: To determine if a Boolean function (logic cover) is always TRUE.

• Recursive Paradigm:

  1. Expand about a variable.

  2. If all resulting cofactors evaluate to TRUE, then the overall function is a tautology.

• Criteria for Recursive Tautology:

  • Tautology Found: If the cover matrix contains a row consisting entirely of $1$s (a Tautology Cube).

  • No Tautology: If the cover has any column consisting entirely of $0$s (meaning a specific variable value can never be reached).

  • Single Variable Dependency: If the cover depends on only one variable and there is no column of $0$s in that variable's field, it is a tautology.

• Unate Heuristics: Operations on unate functions are more efficient. Variables are often selected specifically to drive cofactors toward unate functions.

• Decomposition Rule: If a cover can be split into two sub-covers that rely on disjoint sets of variables, check tautology in both sub-covers independently.