2 added 86 characters in body
source | link

The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF for the same formula.

Perhaps what you want is, given a formula, find the smallest circuit that uses only XOR and AND logic gates. In general, that circuit won't necessarily be in algebraic normal form. (For instance, $B_1 (B_2 \oplus B_3)$ is not in ANF; the ANF of that formula is $B_1 B_2 \oplus B_1 B_3$.) That's called "logic minimization" or "logic synthesis" or "circuit minimization". Most prior work has considered how to use a gate basis of NAND or {AND, OR, NOT}; you are looking for an algorithm that uses the basis {AND, XOR}.

If you want to minimize the total number of gates, I'd suggest you do a literature search on the literature on logic minimization, looking for methods that work with an arbitrary basis, or that work with the basis {AND, XOR}. (One possibly buzzword or phrase to search for is exclusive-or sum-of-products minimization; this covers the special case of circuits that have multi-input AND gates on the first level and a single multi-input XOR gate at the second level.)

In general, essentially all of these circuit minimization isproblems are NP-hard, so you shouldn't expect any efficient algorithm that will always work. Instead, people rely on heuristics that sometimes work or are sometimes efficient.

You can find people who have studied a similar problem in the cryptography world, because Yao-style garbled circuits naturally support AND and XOR gates. Cryptographers have studied how to implement various functions efficiently using only AND and XOR gates. However, in that world, for various reasons we can make XOR gates effectively free, so they generally try to minimize the "multiplicative complexity", i.e., the minimum number of AND gates needed in any circuit over the basis {AND,XOR}. I couldn't tell whether that was what you wanted or not. If it is, you might enjoy the following page, which lists circuits of minimal multiplicative complexity for a variety of functions of cryptographic interest:

http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/CMT.html

Perhaps this will help you articulate a more precisely defined question.

The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF for the same formula.

Perhaps what you want is, given a formula, find the smallest circuit that uses only XOR and AND logic gates. In general, that circuit won't necessarily be in algebraic normal form. (For instance, $B_1 (B_2 \oplus B_3)$ is not in ANF; the ANF of that formula is $B_1 B_2 \oplus B_1 B_3$.) That's called "logic minimization" or "logic synthesis" or "circuit minimization". Most prior work has considered how to use a gate basis of NAND or {AND, OR, NOT}; you are looking for an algorithm that uses the basis {AND, XOR}.

I'd suggest you do a literature search on the literature on logic minimization, looking for methods that work with an arbitrary basis, or that work with the basis {AND, XOR}. (One possibly buzzword or phrase to search for is exclusive-or sum-of-products minimization; this covers the special case of circuits that have multi-input AND gates on the first level and a single multi-input XOR gate at the second level.)

In general, circuit minimization is NP-hard, so you shouldn't expect any efficient algorithm that will always work. Instead, people rely on heuristics that sometimes work or are sometimes efficient.

You can find people who have studied a similar problem in the cryptography world, because Yao-style garbled circuits naturally support AND and XOR gates. Cryptographers have studied how to implement various functions efficiently using only AND and XOR gates. However, in that world, for various reasons we can make XOR gates effectively free, so they generally try to minimize the "multiplicative complexity", i.e., the minimum number of AND gates needed in any circuit over the basis {AND,XOR}. I couldn't tell whether that was what you wanted or not. If it is, you might enjoy the following page, which lists circuits of minimal multiplicative complexity for a variety of functions of cryptographic interest:

http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/CMT.html

Perhaps this will help you articulate a more precisely defined question.

The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF for the same formula.

Perhaps what you want is, given a formula, find the smallest circuit that uses only XOR and AND logic gates. In general, that circuit won't necessarily be in algebraic normal form. (For instance, $B_1 (B_2 \oplus B_3)$ is not in ANF; the ANF of that formula is $B_1 B_2 \oplus B_1 B_3$.) That's called "logic minimization" or "logic synthesis" or "circuit minimization". Most prior work has considered how to use a gate basis of NAND or {AND, OR, NOT}; you are looking for an algorithm that uses the basis {AND, XOR}.

If you want to minimize the total number of gates, I'd suggest you do a literature search on the literature on logic minimization, looking for methods that work with an arbitrary basis, or that work with the basis {AND, XOR}. (One possibly buzzword or phrase to search for is exclusive-or sum-of-products minimization; this covers the special case of circuits that have multi-input AND gates on the first level and a single multi-input XOR gate at the second level.)

In general, essentially all of these circuit minimization problems are NP-hard, so you shouldn't expect any efficient algorithm that will always work. Instead, people rely on heuristics that sometimes work or are sometimes efficient.

You can find people who have studied a similar problem in the cryptography world, because Yao-style garbled circuits naturally support AND and XOR gates. Cryptographers have studied how to implement various functions efficiently using only AND and XOR gates. However, in that world, for various reasons we can make XOR gates effectively free, so they generally try to minimize the "multiplicative complexity", i.e., the minimum number of AND gates needed in any circuit over the basis {AND,XOR}. I couldn't tell whether that was what you wanted or not. If it is, you might enjoy the following page, which lists circuits of minimal multiplicative complexity for a variety of functions of cryptographic interest:

http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/CMT.html

Perhaps this will help you articulate a more precisely defined question.

1
source | link

The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF for the same formula.

Perhaps what you want is, given a formula, find the smallest circuit that uses only XOR and AND logic gates. In general, that circuit won't necessarily be in algebraic normal form. (For instance, $B_1 (B_2 \oplus B_3)$ is not in ANF; the ANF of that formula is $B_1 B_2 \oplus B_1 B_3$.) That's called "logic minimization" or "logic synthesis" or "circuit minimization". Most prior work has considered how to use a gate basis of NAND or {AND, OR, NOT}; you are looking for an algorithm that uses the basis {AND, XOR}.

I'd suggest you do a literature search on the literature on logic minimization, looking for methods that work with an arbitrary basis, or that work with the basis {AND, XOR}. (One possibly buzzword or phrase to search for is exclusive-or sum-of-products minimization; this covers the special case of circuits that have multi-input AND gates on the first level and a single multi-input XOR gate at the second level.)

In general, circuit minimization is NP-hard, so you shouldn't expect any efficient algorithm that will always work. Instead, people rely on heuristics that sometimes work or are sometimes efficient.

You can find people who have studied a similar problem in the cryptography world, because Yao-style garbled circuits naturally support AND and XOR gates. Cryptographers have studied how to implement various functions efficiently using only AND and XOR gates. However, in that world, for various reasons we can make XOR gates effectively free, so they generally try to minimize the "multiplicative complexity", i.e., the minimum number of AND gates needed in any circuit over the basis {AND,XOR}. I couldn't tell whether that was what you wanted or not. If it is, you might enjoy the following page, which lists circuits of minimal multiplicative complexity for a variety of functions of cryptographic interest:

http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/CMT.html

Perhaps this will help you articulate a more precisely defined question.