2
$\begingroup$

Is there something like the sum of products form of a circuit which uses AND and XOR instead of AND and OR?

I know that you can create an OR gate from AND and XOR (but i can't remember or find the details of that at the moment), but am wondering if there is anything more straightforward, as in an actual form that uses AND and XOR?

$\endgroup$
3
$\begingroup$

You're looking for Reed-Müller forms. The introduction to this paper summarizes some families of these forms:

An arbitrary n-variable function $f(x_1,x_2,...,x_n)$ can be represented using the positive polarity Reed-Muller form (PPRM)

$f(x_1,x_2,...,x_n) = a_0\oplus a_1x_1\oplus a_2x_2\oplus\ldots\oplus a_{12}x_1x_2\oplus a_{13}x_1x_3\oplus\ldots\oplus a_{n-1,n}x_{n-1}x_n\oplus\ldots\oplus a_{12\ldots n}x_1x_2\ldots x_n$.

For each function $f$, the coefficients $a_i$ are determined uniquely, so PPRM is a canonical form. If we used either only the positive literal ($x_i$) or only the negative literal ($\overline{x_i}$) for each variable in Eq. (4)1, we get the FPRM. There are $2^n$ possible combinations of polarities and as many FPRMs for any given logical function.

If we freely choose the polarity of each literal in Eq. (4), we get a GRM. In GRMs, contrary to FPRMs, the same variable can appear in both positive and negative polarities. There are $n2^{n-1}$ literals in Eq. (4), so there are $2^{n2^{n-1}}$ polarities for an $n$-variable function and as many GRMs. Each of the polarities determines a unique set of coefficients, and thus each GRM is a canonical representation of a function.


1 It's not clear from the text, but equation 4 is the generic PPRM equation included in the quote

$\endgroup$
  • $\begingroup$ If you work over $\mathbb{F}_2^n$, then this just states that every function can be represented (uniquely) as a multilinear polynomial. $\endgroup$ – Yuval Filmus Mar 29 '16 at 9:27
3
$\begingroup$

Yes. You want algebraic normal form. Every formula in algebraic normal form has the form of an xor of products.

Because xor is the same as addition when working modulo 2 (i.e., when working in the finite field $\mathbb{F}_2$), this basically comes down to expressing the function as a multivariate polynomial over $\mathbb{F}_2[x_1,x_2,\dots,x_n]$ -- in fact, a multilinear polynomial.

There are efficient algorithms to derive the algebraic normal form of any function. They are efficient in the sense that the running time is roughly proportional to the size of the resulting ANF expansion.

$\endgroup$

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.