- #1
ellipsis
- 158
- 24
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?
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?