Minimizing systems of boolean functions as per specific gate costs

Click For Summary

Discussion Overview

The discussion revolves around minimizing systems of boolean functions with specific gate costs, particularly focusing on the challenge of incorporating XOR gates into circuit designs while managing unequal costs associated with different gates. The scope includes theoretical aspects of boolean minimization and practical applications in circuit design.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant describes the problem of minimizing boolean equations using various algorithms, specifically mentioning the Quine-McCluskey and Espresso algorithms, but notes the challenge of including XOR gates with specific cost considerations.
  • Another participant suggests a tool, Logic Minimizer, which claims to support XOR gates but highlights its limitation of only handling one boolean function at a time and concerns about its licensing.
  • Some participants express frustration over the lack of responses and speculate that the framing of the problem in electrical engineering terms may be a barrier to engagement.
  • A participant mentions the KGPMIN tool as a potential resource but indicates difficulty in finding a way to download it.

Areas of Agreement / Disagreement

Participants generally agree on the complexity of the problem and the limitations of existing tools, but there is no consensus on a specific solution or tool that adequately addresses the posed challenge.

Contextual Notes

Some limitations include the dependence on specific definitions of gate costs and the unresolved nature of how to effectively incorporate XOR gates into existing minimization algorithms.

ellipsis
Messages
158
Reaction score
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?
 
Mathematics news on Phys.org
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?
 
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 said:
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.
 
Last edited:
ellipsis said:
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.
 

Similar threads

Engineering Circuit Realization of XOR function with Three inputs
  • · Replies 4 ·
Replies
4
Views
5K
Cryptographic attacks as minimization of degree 4 polynomial
  • · Replies 7 ·
Replies
7
Views
2K
Optimization algorithm to apply to my system?
  • · Replies 2 ·
Replies
2
Views
1K
Optimizing Dimensions to minimize Cost
  • · Replies 2 ·
Replies
2
Views
3K
Programs How good is this applied math program?
  • · Replies 13 ·
Replies
13
Views
4K
Is Alan Turing given too much credit when it comes to computers?
  • · Replies 29 ·
Replies
29
Views
6K
Writing a program to play this game?
  • · Replies 3 ·
Replies
3
Views
2K
Linear Programming Exam Question
  • · Replies 1 ·
Replies
1
Views
7K
Graduate How to solve a system of linear inequalities with absolute magnitudes?
  • · Replies 1 ·
Replies
1
Views
3K
Why Does My C Program Segmentation Fault Without a Filename?
  • · Replies 5 ·
Replies
5
Views
4K