2
$\begingroup$

The other day someone mentioned to me that you could take an arbitrary digital circuit which mapped N input bits to M output bits, and replace it with a layer of OR gates and a layer of AND gates. I believe he said there would be 2^N ANDs and ORs each. I haven't been able to find any more information about this though.

Is this true?

And are there similar techniques for say using only XOR and AND gates?

$\endgroup$
2
$\begingroup$

Yes, it's true. You can use conjunctive normal form to express the circuit in two layers, where the first layer has OR gates and the second layer consists of $m$ (multi-input) AND gates. However, there's a catch: you have to have a way to complement (negate) some of the inputs to the OR gates for free. If you want to count the OR gates as a separate layer, then it takes three layers; if you imagine that your OR gates actually allow you to complement any subset of their inputs (e.g., the gate can compute $x \lor y$, $x \lor \neg y$, $\neg x \lor y$, or $\neg x \lor \neg y$), then it's just two layers.

Or, you can use disjunctive normal form to build a two-layer circuit where the first layer uses AND gates and the second layer contains $m$ (multi-input) OR gates. Again, the same catch applies: you need to be able to complement the inputs to the AND gates "for free".

You can use disjunctive normal form to build a circuit where at most one input to any OR gate will ever be true at a time. This means that you can replace the OR gate with an XOR gate without changing its functionality. Therefore, yes, you can built a two-layer digital circuit where the first layer has only AND gates and the second layer has only XOR gates -- assuming you can complement some of the inputs to the AND gates for free.

For "XOR-of-ANDs", you can actually write any N-to-1-bit circuit as an XOR of ANDs, without any complementation at the input, if you allow the final XOR to optionally include an additional input that's held at the constant 1 (or, equivalently, if you allow the final gate to be either a XOR or a NXOR). In particular, given any boolean function $f:\{0,1\}^N \to \{0,1\}$, you can write it as a multivariate polynomial $f(x_1,\dots,x_N)$ modulo 2. Now $x^2=x \pmod 2$, so since everything is modulo 2, that means that you can eliminate all powers of two or higher: every multivariate polynomial can be expressed in the form

$$f(x_1,\dots,x_N) = \sum_S c_S \prod_{i \in S} x_i \pmod 2,$$

for some constants $c_S$, where $S$ ranges over all subsets $S \subseteq \{1,\dots,N\}$. (For example, we might have $f(x_1,x_2,x_3) = x_1 x_2 + x_2 x_3 + x_3 + 1 \pmod 2$ as an example of such a polynomial.) Now note that product modulo 2 is AND, and sum modulo 2 is XOR, so we get a XOR-of-AND representation of any boolean circuit.

As your colleague mentioned, in the worst case these circuits might need approximately $2^N$ gates, so this can be highly inefficient in some cases.

I don't know if it is possible to write every circuit as an AND-of-XORs (with some complements or constants somewhere).

$\endgroup$
  • $\begingroup$ Thanks for the solid and detailed info! Another efficiency I wanted to point out is that this is seemingly a great way to limit the depth of a circuit if that is a concern - such as when doing homomorphic encryption (my usage case). $\endgroup$ – Alan Wolfe Nov 26 '15 at 22:01
  • $\begingroup$ AND-of-XORs are unable to represent even a two-input OR (after the layer of XOR, the two cases 0, 0 and 1,1 are not distinguishable). BTW, I'm used to a circled + for xor and uncircled + for or, so your f is for me a constant 1. Is the reverse notation common? $\endgroup$ – AProgrammer Nov 27 '15 at 7:59
  • $\begingroup$ @AProgrammer, thanks for the example. If we don't allow any kind of complementation or constant inputs to the gates and if you don't allow single-input XORs, then I agree with what you say. But I'm not sure whether that's ultimately the right formulation of the question: if we impose similar restrictions then AND-of-ORs, OR-of-ANDs, and XOR-of-ANDs become impossible as well. In practice it might be plausible to allow complementation or constant inputs to some gates. $\endgroup$ – D.W. Nov 27 '15 at 18:09
  • $\begingroup$ As far as notation: Thanks for pointing that out. I'm assuming we're working modulo 2, so $+$ and $\oplus$ are the same operator ($1+1=2=0=1 \oplus 1$). I'll edit the answer to make this clearer. $\endgroup$ – D.W. Nov 27 '15 at 18:09
  • $\begingroup$ @D.W., even with negated inputs and one input gates (allowing constant one does not add more possibilities) you can't get a two-input OR from an AND-of-XORs. There is only one 0 in that truth table so the AND function does not help in building it so you would have to get the end result directly as the output of a XOR. You can get it by complementing the output of the AND ($A \vee B = \overline{\overline A \land \overline B}$). If you allow the optional negation of output then you can generate the 16 two-input functions, I don't know if that implies anything for more inputs. $\endgroup$ – AProgrammer Nov 27 '15 at 21:45
2
$\begingroup$

D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1})\oplus h(x_1,\dots,x_{n-1})\land x_n$$ with $g$ and $h$ defined as

$$ g(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0) $$

$$ h(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \land \bar x_n) \lor (f(x_1,\dots,x_{n-1},1) \land x_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x_1,\dots,x_n)} = (\overline{f(x_1,\dots,x_{n-1},0)} \lor x_n) \land (\overline{f(x_1,\dots,x_{n-1},1)} \lor \bar x_n)$$

in other words:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \lor x_n) \land (f(x_1,\dots,x_{n-1},1) \lor \bar x_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, The Art of Computer Programming, volume 4A, Combinational Algorithms part 1.

$\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.