Boolean Optimization

• Irredundant Sum: A sum of products that cannot be reduced by any product term anymore
• Implicant
  • A product that fulfills $\forall X:p(X)=1⟹z(X)=1$
    • $X$ is an assignment of the variables $X_i(0,1)$
    • Any minterm of $p$ is also a minterm of $z$
    • An implicant can cover multiple 1s in the truth table of $z$
  • Simplified definition: A product term for which the value of the function is 1 in the truth table or in the Karnaugh-Map
• Prime Implicant: An implicant that cannot be further reduced
  • Let E be a minimal SOP expression for a function Z, then any product term of E is a prime implicant of Z
• Minimization of Two Level Logic
  1. Find all the prime implicants
  2. Find the minimum number of prime implicants, which cover all minterms of the function (covering problem)
     • If there are many possibilities, then chose the ones that produces the minimum number of literals (cost function)
• Approaches
  • Boolean Algebra Rules
  • Karnaugh-Map: Graphical method for very small cases (up to 5 variables)
  • Quine-McCluskey: tabular method, used to compute exact solution of minimization problem (also efficient for small number of variables but can be used for more)

Karnaugh Map

• Is a special graphical representation of the truth table for an n-variable function
• $2^n$ cells, each of which correspond to a row of the truth table
• Each literal is associated with a row or a column
• A cell ha a unique address (numbering)
  • Defined through cell-column/cell-row or through a binary number, which is defined by literals in the column and row
• Neighbor cells differ by only 1 bit
• Build by entering the value 1 in the address defined by the corresponding minterm from the truth table
• Steps
  1. Construct a K-map
  2. Identify all prime implicants
     • Prime implicants are rectangular blocks of $2^{n-k}$ cells. $0\le k\le n$ not contained in other blocks
     • Prime implicants can overlap
  3. Select a minimal number of prime implicants that covers all K-Map 1‘s
     • In case there are many alternatives, select the one with the minimum number of literals
• Essential prime implicant: A prime implicant that covers a minterm that no other implicant can cover (must be in the solution)
  • Nonessential: Covers something already covered (but might be included because it includes something it only covers)
  • Absolute nonessential: Everything that it covers must already be covered by other prime implicants

Quine-McCluskey

• Steps
  1. Identification of Prime Implicants
     1. Make a list $L_1$ of all minterms, sorted in groups $G_h,0\le h\le n$, where $G_h$ consists of all minterms with $h$ 1s in their code-word
     2. Using list $L_i$, compare all elements $E^{\prime }$ in $G_h$ with $E^{\prime \prime }$ in $G_{h+1}$ if $E^{\prime }=Ex$ and $E^{\prime \prime }=E\overline{x}$. Apply the minimization theorem. Mark $E^{\prime }$ and $E^{\prime \prime }$. Insert $E$ in the group $G_h$ of a new list $L_{i+1}$ if not included
     3. If $L_{i+1}$ is not empty, set $i=i+1$ and go to step 2. If empty, then the non-market inputs $L_1,\dots ,L_i$ are prime implicants
  2. Compute the minimum sum of all prime implicants
     1. Make a coverage table $T$ in which rows represent prime implicants and columns minterms. Mark all cells $T_{ij}$ in the table with an X if the prime implicant in row $i$ covers minterm column $j$
     2. Identify all essential rows of T and insert the corresponding prime implicants to the solution. Reduce $T$ by erasing the essential row. Reduce T further by erasing dominant column and dominated rows (see below).
     3. Apply step 2 until $T$ cannot be further reduced. If $T$ is empty, then solution is $S$. If not, go to step 4
     4. Apply distributive law to compute a minimal SOP-form for the remaining rows of $T$
• Dominance Rules
  • Row dominance: Row $P_i$ dominates row $P_j$ if $P_i$ has X in any column in which $P_j$ also has X
    • A dominated row can be removed from the coverage table if it contains more literals than the dominant row
    • Random choice if they have the same number of literals
  • Column dominance: Column $m_i$ dominates $m_j$, if $m_i$ has X in any row in which $m_j$ also has X
    • A dominant column can be erased since every coverage of $m_j$ is also a coverage of $m_i$
    • Chose any to erase if two columns are identical