Mux Proof?

[Haiduc]

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!

[cadet1620]

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

[Haiduc]

Thanks for the tips, and thank you for the example.  The right sequence of Mux, Xor, And seems to reproduce the truth table :)

[cadet1620]

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

[ammarr]

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

[James]

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?

[cadet1620]

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).

Mux			a
	0	0	1	1
sel	0	1	1	0
		b

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

[James]

Thanks for the reply i think i get it now. the way i setup the K-map was different then yours i had it as
     
                AB
       00 | 01 | 10 | 11
       -----------------
        0  |  0  | 1  |  1
sel:   0  |  1  |  0 |  1

i see now that i could have switched the AB '10' column with the '11' column without affecting the results.  Is there some way to know ahead of time the most optimal way to setup the K-map for the future in the case of more complex versions?

Thanks cadet!

[cadet1620]

For Karnaugh maps to work correctly, the rows and columns must be arranged in a specific order so that when you move between adjacent cells left/right or up/down only one variable changes state. When you label the rows or columns in binary, you need to use Gray code order, not normal counting order.

2-bit Gray code is: 00 01 10 11
3-bit Gray code is: 000 001 011 010 110 111 101 100

--Mark