Showing posts with label Xor. Show all posts
Showing posts with label Xor. Show all posts

Mux out of an XOR



Here is some background and a step to solve the problem:

A set of {+, . , '} is functionally complete because every function can be expressed by operations from this set.

By Demorgan's law can be shown that {+, '} is also functionally complete.
x . y = (x' + y')'

Same holds for {., '} because x + y = (x' . y')'

It can be shown that (x nor y) is also functionally complete:
x nor y = x' x' = x'
(x nor y) nor (x nor y) = (x'y') nor (x'y') = x + y

It can be shown for xor that: x' = x xor 1 , so the inverter is O.K., we need to show that (x + y) or even (x.y) can be built from xor. If we can do that then we are done. I have not found a way to do it yet, so the answer can be Not possible.

proof with new approach.

The question "can a mux be built from XOR only" is the same as "can an arbitrary logic function be implemented with XOR only", given that mux is universal. So, we only need to show that some simple function cannot be implemented (as a counterexample). Let's try AND.

Suppose x.y could be implemented with XOR only. Then x.y would be the output of some XOR gate in the circuit. Let's call the inputs of this XOR gate f(x,y) and g(x,y). The truth tables for f and g will look like:

x y f g
------------
0 0 a a
0 1 b b
1 0 c c
1 1 d d'

If you expand this truth table to the 16 possible cases, you will see that either f or g will be an AND or OR function in each case. OR is basically an AND with complemented inputs and output; so, effectively, an AND function is needed to synthesize AND. This will go on ad infinitum, so the task is impossible. So, a mux cannot be built with XOR gates only.