Implement the boolean function using only a multiplexer

Thread Starter

popeyes

Joined Feb 25, 2013
6
Given logic signal a,b and c, along with their complements

Using only a mux to perform the function below:



It doesn't say any restriction on multiplexer, but assuming the simpler the better. It kind drive me nuts....I guess 2to1 mux will not work anyway, right?
 

WBahn

Joined Mar 31, 2012
29,978
If the restriction is that you can use "only a mux" ('a' mux, as in 'one' mux), then no, you can't use a 2:1 mux, in general, for a function of three variables. There are SOME functions of three variable in which you can, but not in general.

In general, a 2^N:1 mux can implement ANY function of (N+1) variables or less and some functions of more than (N+1) variables
 

WBahn

Joined Mar 31, 2012
29,978
if you are using 2:1 mux, you will need 3 levels or seven units.
if you are using 8:1 mux, you can use just one.
Using 2:1 muxes you only need two levels with three muxes and possibly an inverter.

Using 4:1 muxes you only need one mux and possibly an inverter.
 

thatoneguy

Joined Feb 19, 2009
6,359
Have you diagrammed the truth table?

A|B|C|Out
x|x|x|x|x
x|x|x|x
x|x|x|x
x|x|x|x
x|x|x|x
x|x|x|x
x|x|x|x
x|x|x|x


Here's a blank 8:1 mux
I0-I7 are Mux Inputs, S2-S0 are selectors

S 2 |S 1 |S 0 |I 0 |I 1 |I 2 |I 3 |I 4 |I 5 |I 6 |I 7 |Out
0|0|0| | | | | | | |x|x
0|0|1| | | | | | |x| |x
0|1|0| | | | | |x| | |x
0|1|1| | | | |x| | | |x
1|0|0| | | |x| | | | |x
1|0|1| | |x| | | | | |x
1|1|0| |x| | | | | | |x
1|1|1|x| | | | | | | |x




Quote the post, fill in the Truth Table (swap numbers for each 'x'), post results, then fill in MUX entries.
 
Last edited:

WBahn

Joined Mar 31, 2012
29,978
Just curious about how to do it in 4:1 mux....
Think about how you would implement a 2-input function using just a 2:1 mux. You have two inputs, A and B. Use one of them to select which channel of the mux to use. So let's use A for that. You now need to bring a signal into input D0 of the mux that is the correct signal given A=0 and, likewise, you need to bring in the signal into input D1 of the mux that is the correct signal given A=1. In either case, the signal can only depend on B and there are only four possibilities:

B||0|1|B|B'
0||0|1|0|1
1||0|1|1|0

Use the one you need.

It can help to write the truth table for your 2-input function this way

B|A=0|A=1
0|1|1
1|1|0

So we tie the D0 input HI and apply B' to D1. The result is a 2-input NAND gate.
 

thatoneguy

Joined Feb 19, 2009
6,359
Since Panic Mode just posted the answer, I'll fill this in. I did the truth table quick, so unsure if it is correct, but you get the idea.



Function:
A'C+A'B+AB'C'

A|B|C|Out
0|0|0|0
0|0|1|1
0|1|0|1
0|1|1|1
1|0|0|1
1|0|1|0
1|1|0|0
1|1|1|0


Here's a blank 8:1 mux
I0-I7 are Mux Inputs, S2-S0 are selectors

S 2 |S 1 |S 0 |I 0 |I 1 |I 2 |I 3 |I 4 |I 5 |I 6 |I 7 |Out
0|0|0| | | | | | | |0|0
0|0|1| | | | | | |1| |1
0|1|0| | | | | |1| | |1
0|1|1| | | | |1| | | |1
1|0|0| | | |1| | | | |1
1|0|1| | |0| | | | | |0
1|1|0| |0| | | | | | |0
1|1|1|0| | | | | | | |0

--ETA: DOH!, I messed it up, but somebody can fix it, I don't want to re-do that table. :(
 

WBahn

Joined Mar 31, 2012
29,978
As you say, since panic mode has posted the solution, we can go further.

It would be nice if we had a simple way to get the mux inputs by just Boolean manipulation. Well, we can. First, expand things into SOP form:

A'(B + C) + (A' + B + C)'
A'B + A'C + AB'C'

Now choose all but one of the variables to be your select lines.

If A and B are the select lines, then we need something of the form:

A'B'(?) + A'B(?) + AB'(?) + AB(?)

This is the function for a 4:1 MUX. Each ? will be replaced with 0, 1, C, or C'

So expanding our function, we get

A'B + A'C + AB'C'
A'B + A'(B+B')C + AB'C'
A'B + A'BC + A'B'C + AB'C'
A'B(1+C) + A'B'C + AB'C'
A'B + A'B'C + AB'C'
A'B(1) + A'B'(C) + AB'(C') + AB(0)

So I get

A'B'(C) + A'B(1) + AB'(C') + AB(0)

Now panic mode used CB as the two channel selects, so for that choice it would be

C'B'() + CB'() + C'B() + CB()

A'B + A'C + AB'C'
A'B(C+C') + A'(B+B')C + AB'C'
A'BC + A'BC' + A'B'C + B'C + AB'C'
AB'C' + A'BC' + (1+A')B'C + A'BC
AB'C' + A'BC' + B'C + A'BC

Reordering the factors in each term to match the pattern:

C'B'(A) + C'B(A') + CB'(1) + CB(A')

Which is not quite the solution panic mode had.

Where we differ is CB'A, where his solution has that outputing a 0 and mine has it outputting a 1.

Looking back at the original expression

A'(B + C) + (A' + B + C)'

It appears that panic mode is correct and mine has an error. Looking back, the error is pretty obvious and, upon fixing it, you can eliminate the two lines that follow it. But I'm going to leave finding it as an exercise for the reader (at least for now).
 
Top