Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top