"""
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)