Skip to content

Logic Optimization#

Definition: Complete Cover

Let \(f: \{0,1\}^n \to \{0, 1\}\) be a Boolean function.

A complete cover of \(f\) by implicants is a set of implicants \(\{P_1, \dotsc, P_m\}\) of \(f\) whose disjunction computes \(f\):

\[ f = \sum_{k = 1}^m P_k \]

A complete cover of \(f\) by implicates is a set of implicates \(\{C_1, \dotsc, C_l\}\) of \(f\) whose conjunction computes \(f\):

\[ f = \prod_{k = 1}^l C_k \]

A complete cover of \(f\) is either a complete cover by implicants or a complete cover by implicates.

Definition: Minimality

A complete cover by implicants is minimal if it satisfies the following conditions:

A complete cover by implicates is minimal if it satisfies the following conditions:

In general, minimal complete covers by implicants and minimal complete covers by implicates are not unique. Moreover, the number of terms literals can be different between a minimal complete cover by implicants and a minimal complete cover by implicates.

Theorem: Quines Theorem

Let \(f: \{0,1\}^n \to \{0,1\}\) be a Boolean function.

If \(\sum_{k = 1}^p P_k\) is a minimal complete cover by implicants for \(f\), then all of \(P_k\) are prime implicants.

If \(\prod_{k = 1}^c C_k\) is a minimal complete cover by implicates for \(f\), then all of \(C_k\) are prime implicates.

Proof

TODO

Definition: Minimal Boolean Expression

A minimal Boolean expression for a Boolean function \(f: \{0,1\}^n \to \{0, 1\}\) is a minimal complete cover by implicants or minimal complete covers by implicates which satisfies the following conditions:

Given a Boolean function \(f: \{0,1\}^n \to \{0, 1\}\), logic optimization is the process of finding a minimal complete cover by implicants or minimal complete cover by implicates for \(f\).

Algorithm: Quine–McCluskey Minimization (DNF)

We are given a Boolean function \(f: \{0,1\}^n \to \{0,1\}^n\) and want to find a minimal complete cover by implicants for it.

  1. Find a CDNF for \(f\):

$\(f = \sum_{k = 1}^p P_k\)$

  1. Group the minterms \(P_1, \dotsc, P_p\) based on the Hamming weight of their binary representation, i.e. the group \(G_k\) contains the minterms whose binary representations contain exactly \(i\) ones.

  2. For each pair of consecutive groups \(G_k\) and \(G_{k+1}\), compare each product term \(t_i \in G_k\) with each product term \(t_j' \in G_{k+1}\). If they differ in exactly one bit, create a new term \(t_{\text{new}}\) by replacing this bit with a dash (-) and add it to a new list. Mark \(t_i\) and \(t_j'\) as "checked".

  3. Recursively repeat steps 2 and 3 until no more merges are possible.

  • For newly generated terms to be mergeable, they need to have dashes in the exact same position and they must differ by exactly one bit.
  • At the end, the product terms which are not marked as "checked" are the prime implicants of \(f\).

  1. Create a table whose rows represent the prime implicants of \(f\) and whose columns represent the minterms in the original CDNF for \(f\).
    - If a prime implicant covers a minterm, then mark the corresponding cell.
    - If at the end a column has only one marked cell, then the row of this cell corresponds to an essential prime implicant.

  2. Remove all rows which correspond to the essential prime implicants and all columns which are covered by essential prime implicants.

  3. Select the fewest possible remaining rows which cover all remaining columns.
  4. The sum of all essential prime implicants and all prime implicants from step 7 is a minimal complete cover by implicants for \(f\).
Example

TODO

Algorithm: Quine–McCluskey Minimization (CNF)

We are given a Boolean function \(f: \{0,1\}^n \to \{0,1\}^n\) and want to find a minimal complete cover by implicates for it.

  1. Find a CDNF for \(f\):

$\(f = \prod_{k = 1}^c C_k\)$

  1. Group the maxterms \(C_1, \dotsc, C_c\) based on the Hamming weight of their binary representation, i.e. the group \(G_k\) contains the maxterm whose binary representations contain exactly \(i\) ones.

  2. For each pair of consecutive groups \(G_k\) and \(G_{k+1}\), compare each clause \(t_i \in G_k\) with each clause \(t_j' \in G_{k+1}\). If they differ in exactly one bit, create a new term \(t_{\text{new}}\) by replacing this bit with a dash (-) and add it to a new list. Mark \(t_i\) and \(t_j'\) as "checked".

  3. Recursively repeat steps 2 and 3 until no more merges are possible.
    - For newly generated terms to be mergeable, they need to have dashes in the exact same position and they must differ by exactly one bit.
    - At the end, the clauses which are not marked as "checked" are the prime implicates of \(f\).

  4. Create a table whose rows represent the prime implicates of \(f\) and whose columns represent the maxterms in the original CCNF for \(f\).

  1. Remove all rows which correspond to the essential prime implicates and all columns which are covered by essential prime implicates.
  2. Select the fewest possible remaining rows which cover all remaining columns.
  3. The sum of all essential prime implicates and all prime implicates from step 7 is a minimal complete cover by implicates for \(f\).
Example

TODO