Glossary

English NameMeaningExample
cubeA subset of a space containing $2^n$ vertices, where each vertex represents an assignment for $n$ variables.For $\{x_0, x_1\}$, the vertices in the cube are ${(0,0), (0,1), (1,0), (1,1)}$
mintermA single vertex in a cube, which can be expressed as a product term where all variables are included either in their true form or negated.For $(0, 1)$, it can be expressed as $\neg x0 \cdot x1$
implicantFor a logical formula $F$, if there exists a product term $P$ such that $(P = 1) \rightarrow (F = 1)$ is always true, then $P$ is an implicant of $F$.If $f = xy + yz$, then $xy$ and $yz$ are implicants of $f$, but $x$ alone is not.
prime implicantAn implicant such that we cannot remove any literal from it and still have it remain an implicant.If $f = x \cdot y + z$, then $x \cdot y$ and $z$ are prime implicants of $f$, while $x \cdot y \cdot z$ is an implicant but not a prime implicant.
coverA sum-of-products representation of a Boolean function.$f = AB + A\neg B$ is a cover of itself, and its simplified form $f=A$ is also a cover.
parts of f covered by gIf $g\rightarrow f$, the parts of $f$ covered by $g$ are the parts where $g$ is true.
irredundant coverFor any cover, if we cannot remove any term/implicant from it and still have it remain a cover, then it is an irredundant cover.If $f = AB + AC$, it is an irredundant cover itself, but $AB + AC + ABC$ is not (though it is a cover).
Prime-Irredundant CoverAn irredundant cover composed of prime implicants.

Algorithm

The purpose of Minato's algorithm is to find a prime-irredundant cover for a Boolean function. In other words:

  • We want to find a Sum of Products (SOP) form of the original Boolean function.
  • Each product term is a prime implicant, meaning it contains no literals that can be removed, or in other words, the term is minimal.
  • Removing any product term will make the SOP incomplete (unable to represent the original function).

Let's solve these problems one by one.

Sum of Products

The simplest way to write any Boolean function in SOP form is through Shannon expansion:

  • Fix a variable's value to 0 and calculate the value of the Boolean function.
  • Fix a variable's value to 1 and calculate the value of the Boolean function.
  • Combine the results by multiplying (ANDing) with the variable or its negation.

That is, for a Boolean function $f(x_0,\cdots, x_n)$, we can recursively apply:

$$ f(x_0, x_1, \cdots, x_n) = \neg x_0 \cdot (f(0, x_1, \cdots, x_n)) + x_0 \cdot (f(1, x_1, \cdots, x_n)) $$

until the parameters of $f$ are completely determined.

The result of this expansion is obviously a cover, but it is neither guaranteed to be prime nor irredundant.

Prime and Irredundant

We improve upon the Shannon expansion: Suppose the two parts of the Shannon expansion of $f$ are $f_0(x_1, \cdots, x_n) = f(0, x1, \cdots, x_n)$ and $f_1(x_1, \cdots, x_n) = f(1, x1, \cdots, x_n)$.

If a set of $x_1, \cdots, x_n$:

  • is 1 under $f_0$ but 0 under $f_1$, it means this set of $x$ can only make the original function 1 when $x_0$ is 0. The corresponding term needs to be multiplied by $\neg x_0$ to become an implicant.
  • is 1 under $f_1$ but 0 under $f_0$, it means this set of $x$ can only make the original function 1 when $x_0$ is 1. The corresponding term needs to be multiplied by $x_0$ to become an implicant.
  • is 0 under $f_0$, it means that if $x_0$ is 0, the entire original function cannot be 1. The corresponding term cannot contain $\neg x_0$, otherwise it cannot be an implicant.
  • is 0 under $f_1$, it means that if $x_0$ is 1, the entire original function cannot be 1. The corresponding term cannot contain $x_0$, otherwise it cannot be an implicant.
  • is 1 under both $f_1$ and $f_0$, $x_0$ cannot affect the value of the original function. In this case, the corresponding term does not contain $x_0$ or $\neg x_0$.

Here's the translated table:

$f_0$$f_1$Information
00Cannot cover any minterm
01Must contain minterms of the form $x_0\cdot\varphi$
10Must contain minterms of the form $\neg x_0\cdot\varphi$
11Contains no minterms of $x_0$ or $\neg x_0$

From the analysis above, we can see that except for the case where both $f_0$ and $f_1$ are 1, the other three cases can directly determine a part of the corresponding implicants. Of course, to get the final result, we still need to recursively convert $f_1$ and $f_0$ into prime-irredundant covers.

For the case where both $f_0$ and $f_1$ are 1, we just need to discard $x_0$ and continue to judge from the $x_1$ part.

The result obtained according to this process is a prime-irredundant cover.

Efficient Implementation

Data Structure

We use BDDs to represent logic formulas.

For the found cover, although it can also be represented by a BDD, a more efficient representation is a Zero-Suppressed Binary Decision Diagram (ZDD).

Zero-Suppressed Binary Decision Diagram (ZDD)

Compared to BDDs, ZDDs are more suitable for representing sets of sets, such as a cover of a logic expression, where each term is a set, and the whole is a set of these sets.

The method of using ZDD to represent the cover of a logic expression is as follows:

  • Except for the bottom layer, which consists of two special nodes $\{ \varnothing \}$ ($\top$) and $\varnothing$ ($\bot$), each layer represents an atomic variable or its negation $\neg x$. Therefore, for a logic formula with k atomic variables, at most 2k + 1 layers of zdd are needed to represent it.
  • For each node in the layer representing the atomic variable $x$ or its negation $\neg x$, its low branch represents the set that does not contain $x$, and its high branch represents the set that contains $x$.

For more information about ZDD, see this page.

Algorithm

// `f`: The Boolean function for which to generate a cover
// `fd`: The union of `f` and the don't care set (can be covered or not)
//   If there is no don't care set, just input two f's
fn irr_sop(f: BDD, fd: BDD) -> ZDD {
  if (f == BDD::Bottom) return {};
  if (fd == BDD::Top) return {{}};

  let f_top: BDDVariable = top_variable(f);
  let fd_top: BDDVariable = top_variable(fd);
  let x: BDDVariable = f_top < fd_top ? f_top : fd_top;

  let (f0, f1): (BDD, BDD) = decompose_bdd(f, x);
  let (fd0, fd1): (BDD, BDD) = decompose_bdd(fd, x);

  // g0: The part that must be covered by terms containing !x
  let g0: BDD = f0 - fd1;
  let r0: ZDD = irr_sop(g0, fd0);

  // g1: The part that must be covered by terms containing x
  let g1: BDD = f1 - fd0;
  let r1: ZDD = irr_sop(g1, fd1);

  // h: The part that was not successfully covered by r0 and r1
  let h: BDD = (f0 - BDD(r0)) + (f1 - BDD(r1));
  let hd: BDD = fd0 & fd1;
  let r2: ZDD = irr_sop(h, hd);

  !x・r0 + x・r1 + r2
}

where $f - g = f \cdot (\neg g)$

Example

Suppose we have the following function (represented by a truth table):

ABCOutput
0000
0011
0101
0110
1001
1010
1101
1110

By taking out the minterms directly, we can get the simplest function representation:

$$ \neg A \neg B C + \neg A B \neg C + A \neg B \neg C + A B \neg C $$

Substitute it into f and fd:

  • $x = A$
  • $f_0 = fd_0 = \neg B C + B \neg C$
  • $f_1 = fd_1 = \neg B \neg C + B \neg C$
  • $g_0 = f_0 - fd_1 = (\neg B C + B \neg C) \cdot \neg (\neg B \neg C + B \neg C) = \neg BC$
  • $g_1 = f_1 - fd_0 = (\neg B \neg C + B \neg C) \cdot \neg (\neg B C + B \neg C) = \neg B \neg C$
  • Recursively calculate r_0 = irr_sop(g_0, fd_0) = irr_sop(!B・C, !B・C + B・!C)
    • $x = B$
    • $f_0 = C$
    • $fd_0 = C$
    • $f_1 = 0$
    • $fd_1 = \neg C$
    • $g_0 = f_0 - fd_1 = C \cdot \neg (\neg C) = C$
    • $g_1 = f_1 - fd_0 = 0$
    • Recursively calculate r_0 = irr_sop(g_0, fd_0) = irr_sop(C, C)
      • $x = C$
      • $f_0 = fd_0 = 0$
      • $f_1 = fd_1 = 1$
      • $g_0 = f_0 - fd_1 = 0$
      • $g_1 = f_1 - fd_0 = 1$
      • Recursively calculate r_0 = irr_sop(g_0, fd_0) = irr_sop(0, 0) = 0.
      • Recursively calculate r_1 = irr_sop(g_1, fd_1) = irr_sop(1, 1) = 1.
      • $h = 0 \cdot \neg 0 + 1 \cdot \neg 1 = 0$
      • $hd = 0 \cdot 1 = 0$
      • Recursively calculate r_2 = irr_sop(h, hd) = irr_sop(0, 0) = 0.
      • Return $r_0 = \neg C・0 + C・1 + 0 = C$
    • Recursively calculate r_1 = irr_sop(g_1, fd_1) = irr_sop(0, !C) = 0
    • $h = C \cdot \neg C + 0 \cdot \neg 0 = 0$
    • $hd = C \cdot \neg C = 0$
    • Recursively calculate r_2 = irr_sop(h, hd) = irr_sop(0, 0) = 0.
    • Return $r_0 = \neg B・C + B・0 + 0 = \neg BC$
  • Recursively calculate r_1 = irr_sop(g_1, fd_1) = irr_sop(!B・!C, !B・!C + B・!C)
    • $x = B$
    • $f_0 = \neg C$
    • $fd_0 = \neg C$
    • $f_1 = 0$
    • $fd_1 = \neg C$
    • $g_0 = f_0 - fd_1 = \neg C \cdot \neg (\neg C) = 0$
    • $g_1 = f_1 - fd_0 = 0 \cdot \neg (\neg C) = 0$
      • Recursively calculate r_0 = irr_sop(g_0, fd_0) = irr_sop(0, !C) = 0
      • Recursively calculate r_1 = irr_sop(g_1, fd_1) = irr_sop(0, !C) = 0
      • $h = (\neg C - 0) + (0 - 0) = \neg C$
      • $hd = \neg C$
      • Recursively calculate r_2 = irr_sop(h, hd) = irr_sop(!C, !C) = !C
      • Return $r_1 = \neg B \cdot 0 + B \cdot 0 + \neg C = \neg C$
  • $h = (\neg B C + B \neg C - \neg BC) + (\neg B \neg C + B \neg C - \neg C) = B \neg C$
  • $hd = (\neg B C + B \neg C) \cdot (\neg B \neg C + B \neg C) = B \neg C$
  • Recursively calculate r_2 = irr_sop(h, hd) = irr_sop(B・!C, B・!C) = B・!C.
  • Return the final result $\neg A \neg B C + A \neg C + B \neg C$