Source code for pyeda.boolalg.minimization

"""
The :mod:`pyeda.boolalg.minimization` module contains interface functions for
two-level logic minimization.

Interface Functions:

* :func:`espresso_exprs`
* :func:`espresso_tts`
"""

from pyeda.boolalg import boolfunc
from pyeda.boolalg.expr import exprvar, Expression, Or, And
from pyeda.boolalg.table import TruthTable, PC_ZERO, PC_ONE, PC_DC

# FIXME: This is a hack for readthedocs Sphinx autodoc
try:
    from pyeda.boolalg.espresso import (
        FTYPE, DTYPE, RTYPE,
        set_config, espresso,
    )
except ImportError:
    pass


CONFIG = dict(
    single_expand=False,
    remove_essential=True,
    force_irredundant=True,
    unwrap_onset=True,
    recompute_onset=False,
    use_super_gasp=False,
)

[docs]def espresso_exprs(*exprs): """Return a tuple of expressions optimized using Espresso. The variadic *exprs* argument is a sequence of expressions. For example:: >>> from pyeda.boolalg.expr import exprvar >>> a, b, c = map(exprvar, 'abc') >>> f1 = ~a & ~b & ~c | ~a & ~b & c | a & ~b & c | a & b & c | a & b & ~c >>> f2 = f2 = ~a & ~b & c | a & ~b & c >>> f1m, f2m = espresso_exprs(f1, f2) >>> f1m Or(And(~a, ~b), And(a, b), And(~b, c)) >>> f2m And(~b, c) """ for f in exprs: if not (isinstance(f, Expression) and f.is_dnf()): raise ValueError("expected a DNF expression") support = frozenset.union(*[f.support for f in exprs]) inputs = sorted(support) # Gather all cubes in the cover of input functions fscover = set() for f in exprs: fscover.update(f.cover) ninputs = len(inputs) noutputs = len(exprs) cover = set() for fscube in fscover: invec = list() for v in inputs: if ~v in fscube: invec.append(1) elif v in fscube: invec.append(2) else: invec.append(3) outvec = list() for f in exprs: for fcube in f.cover: if fcube <= fscube: outvec.append(1) break else: outvec.append(0) cover.add((tuple(invec), tuple(outvec))) set_config(**CONFIG) cover = espresso(ninputs, noutputs, cover, intype=FTYPE) return _cover2exprs(inputs, noutputs, cover)
[docs]def espresso_tts(*tts): """Return a tuple of expressions optimized using Espresso. The variadic *tts* argument is a sequence of truth tables. For example:: >>> from pyeda.boolalg.bfarray import ttvars >>> from pyeda.boolalg.table import truthtable >>> X = ttvars('x', 4) >>> f1 = truthtable(X, "0000011111------") >>> f2 = truthtable(X, "0001111100------") >>> f1m, f2m = espresso_tts(f1, f2) >>> f1m Or(x[3], And(x[0], x[2]), And(x[1], x[2])) >>> f2m Or(x[2], And(x[0], x[1])) """ for f in tts: if not isinstance(f, TruthTable): raise ValueError("expected a TruthTable instance") support = frozenset.union(*[f.support for f in tts]) inputs = sorted(support) ninputs = len(inputs) noutputs = len(tts) cover = set() for i, point in enumerate(boolfunc.iter_points(inputs)): invec = [2 if point[v] else 1 for v in inputs] outvec = list() for f in tts: val = f.pcdata[i] if val == PC_ZERO: outvec.append(0) elif val == PC_ONE: outvec.append(1) elif val == PC_DC: outvec.append(2) else: raise ValueError("expected truth table entry in {0, 1, -}") cover.add((tuple(invec), tuple(outvec))) set_config(**CONFIG) cover = espresso(ninputs, noutputs, cover, intype=FTYPE|DTYPE|RTYPE) inputs = [exprvar(v.names, v.indices) for v in inputs] return _cover2exprs(inputs, noutputs, cover)
def _cover2exprs(inputs, noutputs, cover): """Convert a cover to a tuple of Expression instances.""" fs = list() for i in range(noutputs): terms = list() for invec, outvec in cover: if outvec[i]: term = list() for j, v in enumerate(inputs): if invec[j] == 1: term.append(~v) elif invec[j] == 2: term.append(v) terms.append(term) fs.append(Or(*[And(*term) for term in terms])) return tuple(fs)