Showing posts with label mux. Show all posts
Showing posts with label mux. 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.

gates from mux's

OR gate from 2:1 MUX:
's' is the select line for the mux.
'I0 and I1' be the input data lines of the mux.
'Z' be the ouput of the Mux.

a,b inputs of the OR gate.

method 1 >>
Connect the input b to the select line 's' of mux.
Connect input 'a' to the 'I0' line input of mux.
Connect the 'I1' line input of mux to LOGIC 1(VCC).
Now ur mux out 'z' will be "a or b"

method 2>>
in this method instead of connecting the I1 line of the mux to VCC, connect(short) it to the Select line "s" of mux.

XOR gate from 2:1 mux:
Connect input 'b' to select line.
Then connect 'a' to I0, and connect 'a' to I1 using an inverter ( negation of a to I1).

If u reverse, (inverted a to I0, and a to I1 , you will get XNOR operation.)