Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
circuit minimization
1 view
Skip to first unread message
Alex Mizrahi
Dec 31, 2011, 10:30:17 AM12/31/11
to
What is the best news group to discuss circuit minimization topic?
As it is related to math logic, I'll start here.
I have a huge-ass boolean function of a cryptographic nature (SHA-256)
expressed in form of a DAG where each node is one of logic operations
like OR, NOT, AND, XOR. I want to speed up computation by re-writing
parts of graph so that it has less nodes.
I've read about some simple optimization strategies, but I doubt that
they will work on that scale.
BDD works fairly well on fringe nodes which have few variable
dependencies, but not on graph in general.
Here's a particular example of a subgraph I'm working with:
A and B are 32-bit numbers:
A = a0, a1,..a31
B = b0, b1...b31
C = (A + B) mod 2^32.
C = c0, c1...c31.
c0 = a0 XOR b0
c1 = (a1 XOR b1) XOR (a0 AND b0)
c2 = (a2 XOR b2) XOR ((a1 AND b1) OR ((a1 OR b1) AND (a0 AND b0)))
...
The task is to find
x = c0 OR c1 or ... c31.
I believe that there is a cheaper way to compute x than to compute all
c0..c31 and OR them together, but general structure of solution escapes me.
This is also related to boolean satisfiability problem (SAT), so maybe
some SAT-solving methods can help, although I have no idea what can work
on a huge-ass graph.
As it is related to math logic, I'll start here.
I have a huge-ass boolean function of a cryptographic nature (SHA-256)
expressed in form of a DAG where each node is one of logic operations
like OR, NOT, AND, XOR. I want to speed up computation by re-writing
parts of graph so that it has less nodes.
I've read about some simple optimization strategies, but I doubt that
they will work on that scale.
BDD works fairly well on fringe nodes which have few variable
dependencies, but not on graph in general.
Here's a particular example of a subgraph I'm working with:
A and B are 32-bit numbers:
A = a0, a1,..a31
B = b0, b1...b31
C = (A + B) mod 2^32.
C = c0, c1...c31.
c0 = a0 XOR b0
c1 = (a1 XOR b1) XOR (a0 AND b0)
c2 = (a2 XOR b2) XOR ((a1 AND b1) OR ((a1 OR b1) AND (a0 AND b0)))
...
The task is to find
x = c0 OR c1 or ... c31.
I believe that there is a cheaper way to compute x than to compute all
c0..c31 and OR them together, but general structure of solution escapes me.
This is also related to boolean satisfiability problem (SAT), so maybe
some SAT-solving methods can help, although I have no idea what can work
on a huge-ass graph.
0 new messages