New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

espresso_exprs() inverts expression #75

Closed
Harnesser opened this Issue Mar 22, 2014 · 5 comments

Comments

Projects
None yet
2 participants
@Harnesser
Contributor

Harnesser commented Mar 22, 2014

Hi!

I think I may have found a bug with the espresso_expr() function. I don't know enough about your program to trace the root cause, but I've created a testcase to reproduce it.

I was running espresso_exprs() to optimise a simple expression. Afaict, if I check the input and the output of espresso_exprs() for equivalence, they should be the same, right?

Testcase test_espresso_2 can be found at:
https://github.com/Harnesser/pyeda/blob/master/pyeda/boolalg/test/test_espresso.py
In this case, the function seems to be getting inverted!?

PS: Found your project in Coursera's VLSI-CAD forums! Looking forward to some BDD documentation as kbdd isn't open source... :)

@cjdrake

This comment has been minimized.

Owner

cjdrake commented Mar 22, 2014

Thanks for the bug report!

Indeed you are correct. Best clue as to root-cause is that your expression is just a single And term--so most likely the minimization module doesn't convert degenerate forms correctly. Will look into it.

@cjdrake

This comment has been minimized.

Owner

cjdrake commented Mar 23, 2014

Confirmed. Internally, the espresso_exprs function converts the function ~b & x to the following cover:

{ ((1, 3), (1,)),
  ((3, 2), (1,)) }

The "cover" type is an implicant table. This particular cover has two implicants, both of which have one literal. The (1, 3) in the first means ~b, and the (3, 2) in the second means x. The 1, 2, 3 are positional cube notation. 1 means the literal appears inverted in this term, 2 means the literal appears in this term, and 3 means the literal does not appear in this term. Therefore, this particular implicant table describes the function ~b | x.

The correct implicant table would be:

{ ((1, 2), (1,)) }

which describes one implicant with literals ~b and x.

@cjdrake

This comment has been minimized.

Owner

cjdrake commented Mar 23, 2014

@Harnesser, can you please create a pull request with your test case?

Addendum:
I would like to merge a fast-forward commit, so please do something like this:

$ git remote add upstream https://github.com/cjdrake/pyeda.git
$ git fetch upstream
$ git rebase upstream/master master
$ git push --force origin master

Then submit a pull request of your master onto mine.

cjdrake added a commit that referenced this issue Mar 23, 2014

@cjdrake

This comment has been minimized.

Owner

cjdrake commented Mar 23, 2014

Never mind all that. I just grabbed the commit from your repo. Thanks for the help :).

@cjdrake cjdrake closed this Mar 23, 2014

cjdrake added a commit that referenced this issue Mar 23, 2014

@Harnesser

This comment has been minimized.

Contributor

Harnesser commented Mar 23, 2014

Wow - that was quick! Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment