# Mux Proof? Classic List Threaded 9 messages Open this post in threaded view
|

## Mux Proof?

 So... the canonical representation of the Mux looked a bit like overkill as a specification, and sure enough, after staring at the truth table for a few minutes a much simpler specification popped out, and lo and behold, it works :). I know I'm supposed to be embracing ignorance ;) but the proof of why the simpler implementation is equivalent to the canonical representation is eluding me (it's over 20 years since I studied any mathematics).  I'm thinking ahead to more complex designs where a simpler specification is non-obvious.  Can anyone recommend a reference/text for what I'm trying to achieve?  Should I just invest some time learning the laws of Boolean algebra and work through examples of those... Cheers!
Open this post in threaded view
|

## Re: Mux Proof?

 Administrator In general, it's enough that two functions have the same truth table to prove that they are the same. Since we don't want to give away the Mux, consider instead the "Greater than or equal to 2" function. This function outputs 1 if two or more of its inputs are 1.     a b c | out     0 0 0 |  0     0 0 1 |  0     0 1 0 |  0     0 1 1 |  1     1 0 0 |  0     1 0 1 |  1     1 1 0 |  1     1 1 1 |  1 The canonical representation of this function would be             _    _    _     out = abc + abc + abc + abc Unless we write 3-input And and 4-input Or, this is going to take quite a bit of HDL — 3 Nots, 8 Ands and 3 Ors.   The usual way to optimize canonical representations is using a Karnaugh Map. See http://www.facstaff.bucknell.edu/mastascu/elessonshtml/Logic/Logic3.html for a good introduction. For this function, the optimized representation is     out = ab + ac + bc A formal proof using Boolean algebra might run something like             _    _    _     out = abc + abc + abc + abc             _    _    _     out = abc + abc + abc + abc + abc + abc              _            _            _     out = (abc + abc) + (abc + abc) + (abc + abc)              _         _         _     out = ab(c+c) + ac(b+b) + bc(a+a)     out = ab + ac + bc This is much easier to do in HDL — 3 Ands and 2 Ors.   There is an even better optimization from the TECS nested abstractions point of view. Study the truth table above and see if you can find the 3-line implementation using a Mux and two other gates. --Mark
Open this post in threaded view
|

## Re: Mux Proof?

 Thanks for the tips, and thank you for the example.  The right sequence of Mux, Xor, And seems to reproduce the truth table :)
Open this post in threaded view
|

## Re: Mux Proof?

 Administrator This post was updated on . Haiduc wrote Thanks for the tips, and thank you for the example. The right sequence of Mux, Xor, And seems to reproduce the truth table :) I don't see your Mux/Xor/And solution. I'll have to take another look after my morning coffee. What I was thinking was that the top half of the truth table is bc and the bottom half is b+c. [A bit later in the day...] The coffee seems to have done it's job. Thinking about using Xor, I've managed to get the GE2 circuit down to just an Xor and a Mux! I added an a Xor b column along side the output and then looked for the values I needed in the b and c columns.     a b c | out a^b out'     0 0 0 |  0   0   b     0 0 1 |  0   0   b     0 1 0 |  0   1   c     0 1 1 |  1   1   c     1 0 0 |  0   1   c     1 0 1 |  1   1   c     1 1 0 |  1   0   b     1 1 1 |  1   0   b Note that a and b are interchangeable. --Mark
Open this post in threaded view
|

## Re: Mux Proof?

 In reply to this post by Haiduc I have read allot about how to implement Mux, actually how to develop a method to understand how to implement any chip and this post was the most useful combining canonical with Boolean algebra Thanks again --- here my method below (am replacing sel with the letter c) Mux truth Table     a b c | out 1) 0 0 0 |  0 2) 0 1 0 |  0 3) 1 0 0 |  1 4) 1 1 0 |  1 5) 0 0 1 |  0 6) 0 1 1 |  1 7) 1 0 1 |  1 8) 1 1 1 |  1 so i converted the truth table into canonical line by line 1) out = a.b.c 2) out = a.b.c 3) out = a.~b.~c 4) out = a.b.~c 5) out = a.b.c 6) out = ~a.b.c 7) out = a.b.c 8) out = a.b.c so the end result will be all (a.b.c) will cancel each other and will just use one out = (a.b.c) + (~a.b.c) + (a.b.~c)  + (a.~b.~c) out = b.c(a+~a) + a.~c(b+~b) out = b.c + a.~c and then i implemented the out = b.c + a.~c and it worked Mux = b.c + a.~c hope this helps
Open this post in threaded view
|

## Re: Mux Proof?

 i have a question i calculated Mux using a karnaugh map but what i ended up getting was out = a.~c + a.b + ~a.b.c so my question is how come using the kmap did i not come to the simplest solution: Mux = b.c + a.~c? i thought the purpose of the kmap was to find the simplest form?? what did i do wrong?
Open this post in threaded view
|

## Re: Mux Proof?

James wrote
i have a question i calculated Mux using a karnaugh map but what i ended up getting was out = a.~c + a.b + ~a.b.c

so my question is how come using the kmap did i not come to the simplest solution: Mux = b.c + a.~c? i thought the purpose of the kmap was to find the simplest form?? what did i do wrong?

Your K-map should have come out looking like this (depending on how you ordered the variables).

 a sel Mux 0 0 1 1 0 1 1 0

You can cover all the 1s with the a.~sel term in the upper row and the b.sel term in the lower row.

--Mark