-
Notifications
You must be signed in to change notification settings - Fork 7
Mux Gate
Jason Bazalar edited this page Mar 2, 2016
·
17 revisions
The following will show you how to go about solving the Multiplexor (aka Mux) Gate using a Canonical strategy.
a b sel | out
0 0 0 | 0
0 1 0 | 0
1 0 0 | 1 *
1 1 0 | 1 *
0 0 1 | 0
0 1 1 | 1 *
1 0 1 | 0
1 1 1 | 1 *
From the Mux truth table above we see that there are four instances where the output is equal to 1:
a b sel
1 0 0
1 1 0
0 1 1
1 1 1
We can then start setting up the canonical representation of these:
100 OR 110 OR 011 OR 111
Which then gets translated into the following:
a'b's OR ab's OR 'abs OR abs // 100 becomes a'b's, 110 becomes ab's, etc.
a'b's + ab's + 'abs + abs // replace OR with a plus sign
- a for a, b for b, s for sel
- ' (single quote) in front of a letter to denote NOT
- + to denote OR
We can then group them together and start to simplify them:
a'b's + ab's + 'abs + abs
( a'b's + ab's ) + ( 'abs + abs )
( a's('b+b) ) + ( 'abs + abs ) // Left side has a's in common, we bring those out
( a's('b+b) ) + ( bs('a+a) ) // Right side has bs (lol) in common, we can bring those out
( a's(1) ) + ( bs(1) ) // 'b+b = 1 as does 'a+a = 1
( a's ) + ( bs ) // a's(1) = a's, same idea for bs.
a's + bs // a and not s OR b and s
aNot(s) + bs
And(a,Not(s)) + And(b,s)
Or( And(a,Not(s)) , And(b,s) ) // Final simplification
From the last line in the last section (Final Simplification) we see that we'll need:
Not(s) = nots
And(a,nots) = and1
And(b,s) = and2
Or(and1,and2) = out
So we can construct it as follow:
CHIP Mux {
IN a, b, sel;
OUT out;
PARTS:
Not(in=sel,out=nots);
And(a=a,b=nots,out=and1);
And(a=b,b=sel,out=and2);
Or(a=and1,b=and2,out=out);
}