Expansion, reduction and removal of redundant terms in truth table

Question

What steps take left truth-table to right truth-table? In general, what are general rules to follow in transformations of truth-table?

Answer 1

While it is not possible to infer the precise algorithm from one example, it's a reasonable bet to assume that we are looking at some variation of the Espresso algorithm. A reasonably short explanation can be found in R. Rudell, A. Sangiovanni-Vincentelli, Multiple-Valued Minimization for PLA Optimization, IEEE Transactions on CAD, vol. CAD-6, No 5, Sep. 1987, pp. 727-750. The longer version (without multi-valued extensions) is in R. Brayton, G. Hachtel, C. McMullen, A. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, Kluwer, 1984.

The basic idea of the Espresso algorithm, and in part of its variants and predecessors (e.g., Hong and Ostapko's MINI), is to alternate three operations: reduction, expansion, and elimination of redundant cubes.

Espresso (you may still be able to find the C code of Rick Rudell's implementation around) is a rather sophisticated heuristic-search algorithm. The sophistication is needed to get a good chance to climb out of local minima. To give an example, in the irredundancy step, Espresso solves a minimum set-cover problem. It remains feasible even for practically interesting inputs because the set of implicants considered is not the full set. Espresso makes essential use of the complement of the given function to guide the expansion and reduction processes.

There are also "naive" versions of the algorithm, useful for educational purposes, and there's a chance that an example that shows one bit change after the other is just an illustration of how local search may be used to move from one cover to another, not an illustration of a specific algorithm.

---

In the case of the example above, Espresso would work roughly as follows. First it will detect that no implicant is essential. (It's easy to verify that in this case by drawing K-maps of $f$ and $g$. Espresso, if memory serves, uses a technique due to T. Sasao to identify essential primes.)

It will then find that $11-$, and $-01$ may be expanded from $g$ to $f$ and $g$, while $1-1$ may be expanded from $f$ to $f$ and $g$ (output expansions). No other expansion is possible. In particular, no input expansion is possible, as one can verify on the K-maps of $f$ and $g$. After this expansion, either $1-1$ or $11-$ is redundant because it is jointly covered by the other cubes. Espresso throws away one of the two.

The resulting solution is a local minimum, whose cubes can be neither expanded nor reduced. Hence minimization terminates. The steps you linked to produce a solution of equal cost, but they are not exactly what Espresso would do. (Again, if memory serves.) The main difference is that no removal of redundant cubes takes place after the initial expansion phase.