# 4 to 1 MUX K-Map

Discussion in 'Homework Help' started by Lurid, Nov 26, 2010.

1. ### Lurid Thread Starter New Member

Nov 24, 2010
9
0
I've been trying to do this problem for the past 5 hours... I can't figure out how to do it. I've looked at online references and posted powerpoints about multiplexers, but I've never found any help with solving a problem like this.

I attempted to draw out the decoder with two inputs S0 and S1 going to AND gates with lines I0-I3 going into those AND gates then the outputs of those AND gates OR'd w/ each other to represent the inside of the multiplexer, but after I got some sort of a visual representation of the problem, I encountered a problem with only 8 outputs 0 - 7 excluding 8 and 9 because in the problem, it says S(0,2,3,4,5,7,8,9) which is representative of the SOP based on 16 outputs 0 - 15. Then I became puzzled how to get outputs 0 - 15 with only 3 bits, I(n) S1 and S0, which is impossible. You can't make a number greater than 7 with three bits...

So I decided to try to make a K-map of the SOP given, but then I encountered the problem if you had a 4x4 K-map then you're missing a fourth variable to represent the most significant place value of the numbers from 0 - 15.

Then I got stuck and tried reviewing more resources...

2. ### Lurid Thread Starter New Member

Nov 24, 2010
9
0
Sorry for double-posting, but I made a representation of the k-map I drew up in mspaint.

The red represents another solution. I'm sure I didn't do this right, but if someone can correct me, this is what I thought I needed to do.

Thanks.

=)

3. ### Georacer Moderator

Nov 25, 2009
5,151
1,266
Don't be fooled: you do have 4 variables and you can use a MUX, but a few gates will still be needed. A 4-to-1 MUX can implement by its own (no gates needed) only a 3 variable function as you said.

Let's assume that your function depends on the variables A,B,C,D, that is F=F(A,B,C,D). Make a truth table of the function. The first two columns of the table will contain A and B permutations. Use A and B as your MUX select inputs.

Now you have another three columns containing permutations of C and D and the function output. Notice that A and B change every 4 rows. That means that a group of 4 rows corresponds to one MUX input. That input will accept the boolean subfunction that is formed by the subtable containing the 4 rows of the variables C and D and the output.

Post the truth table and I'll tell you more.

4. ### Lurid Thread Starter New Member

Nov 24, 2010
9
0
Here is the truth table:

5. ### Lurid Thread Starter New Member

Nov 24, 2010
9
0
I realized now that to use a 4 to 1 MUX, I'm going to have to basically build more circuitry on the outside of the MUX before lines I0 - I3 right?

And the boolean expressions in SOP (canonical form) modeling the truth table would be:

(A'B'C'D') + (A'B'CD') + (A'B'CD) + (A'BC'D') + (A'BCD) + (AB'C'D') + (AB'C'D)

which can be implemented using a series of ORs and AND gates, but how do I answer the question which asks, "Give the inputs I0 to I3 so that a 4-to-1 MUX will implement the following function when connection C and D to S1 and S0 respectively."

My question rephrased would be how would I take the boolean expression and use it to find the inputs to I0 - I3? Or do I find a reoccurring pattern in the truth table?

6. ### Georacer Moderator

Nov 25, 2009
5,151
1,266
Check rows 0-3. These have {S1,S0}={0,0} and therefore refer to input 0 of the MUX. This input will have the boolean funtion that is defined by C,D and F for the first 4 rows, that is F0=(C+D').

When A,B point to the first MUX input the output of the MUX will be C+D'. Check the truth table. Isn't that what we want?

Do the same for the 3 remaining groups of 4 rows.

7. ### Lurid Thread Starter New Member

Nov 24, 2010
9
0
Interesting, so the next groups are:

S0 S1 : F1=(C'+D)
0 1

S0 S1 : F2=(AC') *Question: Are you allowed to use A and B to find F2??? I can't seem to find another way to get the outputs for F2 if I don't use A ANDed with C'?
1 0

S0 S1 : F3=(A(x)B) *Same for this one... I'm not seeing the combination of C and D.
1 1

EDIT: Am I limited to only using C and D and AND and OR operations? or can I use XOR or XNOR or NAND operations?

RE-EDIT: I took a break and came back to it and I realized I was overthinking it... F2=C' and F3=0

Are my answers in the re-edit correct?

Last edited: Nov 27, 2010
8. ### Skynt New Member

Nov 27, 2010
3
0
I think you have the wrong selectors on the truth table judging by the question, since it mentions C and D and not A and B as the selectors S1 and S0.

Using the truth table, the way you want to look at these is starting with $I_{0}$. Simply look at the entries for C and D that are 0 and 0, and construct a karnaugh map based on these.

For example, here's the truth table for A and B when C and D are both 0.

Code ( (Unknown Language)):
1.
2.   A  |  B  |   F
3. ------------------
4.   0     0      1
5.   0     1      1
6.   1     0      1
7.   1     1      0
8.
Now just create a 2-variable karnaugh map and you've got your expression for $I_{0}$. Looking at this one using a program real quick, $I_{0}$= A' + B'. You just continue that process for all the inputs.

EDIT: It ruined my format for the table

Last edited by a moderator: Nov 27, 2010
9. ### Lurid Thread Starter New Member

Nov 24, 2010
9
0
Thank you both very much. I was able to solve the question. I understand how to do it now.

10. ### Georacer Moderator

Nov 25, 2009
5,151
1,266
Your subfunctions are all correct (after the revisions). I know we solved them with A and B being the selector inputs, but that's ok. Just replace all As and Bs with Cs and Ds and vice versa on the final circuit.

11. ### Lurid Thread Starter New Member

Nov 24, 2010
9
0
Thanks very much Geo.