Algorithm for simplifying ANF or polynomials?

I have some digital logic circuits in Algebraic Normal Form, and am limited to using XOR and AND logic gates.

For instance:

$B_{out} = B_1 B_2 \oplus B_1 B_3$

I was wondering, are there any algorithms to simplify ANF to use a smaller number of gates? I'm looking to minimize ANDs specifically.

The above equation would ideally become this:

$B_{out} = B_1 (B_2 \oplus B_3)$

Since AND and XOR act like multiplication and addition respectively, it also seems like the answer could be in algorithms which minimize operations in polynomials. If that is the case, I'm specifically looking to minimize multiplications (which is the equivelant of ANDs in ANF).

One person suggested i use a Karnaugh map, but am unsure how (or if it's possible) to use a Karnaugh map with XOR/AND instead of OR/AND. I could convert OR/AND back and forth to XOR/AND terms as needed, but in that case I don't believe the result is garaunteed (or likely) to be minimal anymore.

Are there algorithms for this? I feel like there has to be, but I haven't been able to find any.

1 Answer

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.

• thank you for all the wonderful info! I too am trying to avoid the AND gates more than the XOR gates. Homomorphic encryption in my case (: Apr 16, 2016 at 1:08