Minimizing systems of boolean functions as per specific gate costs

[ellipsis]

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?

 

[Greg Bernhardt]

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?

 

[ellipsis]

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.

 

[jedishrfu]

What about this tool?

http://www.logicminimizer.com/

In its writeup it says it includes XOR gates.

 

[ellipsis]

What about this tool?

http://www.logicminimizer.com/

In its writeup it says it includes XOR gates.

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.

 

[mfb]

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.

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.

 

[jedishrfu]

I found a reference to the KGPMIN tool but can't find any way to download it:

http://dl.acm.org/citation.cfm?id=2299214