If I have a boolean expression made up of ANDs and XORs in algebraic normal form, are there any algorithms which can minimize the circuit further?

I'm looking to minimize AND gates specifically.

I'm building ANF from a truth table, so if there's a different way to go about getting a circuit made from XORs and ANDs starting with a truth table that has a minimal number of ANDs that'd be helpful too.

Thank you for any help you can provide!!

Edit: to be more explicit, I'm limited to using xor and and gates.

  • \$\begingroup\$ The only realistic answer is "maybe". \$\endgroup\$ – Andy aka Apr 13 '16 at 14:42
  • \$\begingroup\$ Karnot maps perhaps? Also, the best way to make a complex table would be multiplexor. \$\endgroup\$ – b degnan Apr 13 '16 at 14:45
  • \$\begingroup\$ ANF = what precisely? \$\endgroup\$ – placeholder Apr 13 '16 at 15:17
  • \$\begingroup\$ Algebraic normal form. en.m.wikipedia.org/wiki/Algebraic_normal_form \$\endgroup\$ – Alan Wolfe Apr 13 '16 at 15:18
  • \$\begingroup\$ XOR can be made to function like an inverter if you wire one input high. This means you can convert an AND gate to a NAND gate by putting an XOR inverter on the output. So solve for the NAND minimum solution using Karnough map. Then use one AND plus one XOR for each NAND gate. \$\endgroup\$ – mkeith Apr 13 '16 at 18:16

There is an enormous amount of information about achieving minimal logic with only NAND or only NOR, both of which are functionally complete by themselves. The reason for this is that NAND and NOR can be made with a minimum number of transistors. I don't know if there is literature on minimum logic with AND and XOR. But you could use a minimum NAND solution to leverage this body of knowledge. A NAND gate for you would be an AND gate followed by an XOR based inverter. (XOR with one input wired high is an inverter). Initially I was not planning to answer this question as it is not an area where I have deep knowledge, but nobody else provided a high quality answer, so I am giving it a shot.

  • \$\begingroup\$ Thanks mkeith. My concern with using nand or anything else is that when I translate back to and/xor it won't be minimal anymore. However, you've given me info where I had non otherwise so thank you for that! \$\endgroup\$ – Alan Wolfe Apr 17 '16 at 0:20
  • \$\begingroup\$ Yes, it is certainly not guaranteed to be minimal anymore. Maybe you can find some literature on minimal formulations with XOR and AND. Someone's thesis or something. \$\endgroup\$ – mkeith Apr 17 '16 at 1:33

Only optimisation will be possible through Karnaugh map. see link,


  • 1
    \$\begingroup\$ Is it possible to use karnaugh maps with ANF which only has XOR and AND gates? I thought they could only work with OR and AND? \$\endgroup\$ – Alan Wolfe Apr 13 '16 at 15:10
  • \$\begingroup\$ I updated my question but I'm limited to xor and and gates. \$\endgroup\$ – Alan Wolfe Apr 13 '16 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.