1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minimizing systems of boolean functions as per specific gate costs

  1. Oct 22, 2014 #1
    I've been grappling with this problem for a long time, but I think someone on this forum may know about this.

    Minimizing the joint number of products of a system of boolean equations is well-studied, and has various software implementations. Those are the Quine-McCluskey and Espresso algorithms. This is the problem of creating a circuit with N inputs, M outputs, while using the minimum number of OR, NOR, AND, and NOT gates. (Or, alternatively, their functional counterparts with an arbitrary number of temporary variables). I use the program "Logic Friday" to do this.

    My problem is similar, but it includes a different set of gates (OR, AND, NOT, XOR), and un-equal costs associated with each gate - specifically, the cost of an OR is zero, while the cost of AND, NOT, and XOR, are equal.

    What I want is to be able to define a truth table, and get returned a circuit diagram with the minimum number of ANDs, NOT,s and XORs, with any number of ORs.

    No boolean minimizer software I've found ever generates a circuit or equation with XOR in it. Does anyone know of a program that can solve this problem, or a way to generalize the existing algorithms to match my problem?
  2. jcsd
  3. Oct 27, 2014 #2
    Thanks for the post! Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
  4. Oct 28, 2014 #3
    Unfortunately, I haven't been able to make much progress on the problem. Maybe nobody's been posting because I described the problem in terms of electrical engineering, rather than algebra theory.
  5. Oct 28, 2014 #4


    Staff: Mentor

  6. Oct 28, 2014 #5
    Unfortunately, it does not do joint optimization - it can only handle one boolean function (output) at a time. Not to mention it's disreputable license. Thanks anyway, jedish.
    Last edited: Oct 28, 2014
  7. Oct 28, 2014 #6


    User Avatar
    2017 Award

    Staff: Mentor

    It is clear what you mean in terms of mathematics, that is not an issue.
    I watch the thread because I think the question is interesting, but I don't have an answer.
  8. Oct 28, 2014 #7


    Staff: Mentor

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook