Can I simplify this to a 2-to-1 multiplexer?

I have the following 4-to-1 multiplexer circuit: simulate this circuit – Schematic created using CircuitLab

With this truth table:

S0 S1 S2 | L
------------
0  0  0 | 0
0  0  1 | 1
0  1  0 | 1
0  1  1 | 0
1  0  0 | 1
1  0  1 | 0
1  1  0 | 0
1  1  1 | 1

I can see that I only need 2 inputs to the 4-to-1 mux, but I don't think I can get away with just 1 selector. It seems if S1 = 0 then it wouldn't know to pick d0 or d1. Same with S2 = 0. Is there some way to simplify this circuit to single 2-to-1 multiplexer?

• a couple of exclusive or gates would work. – Andy aka Oct 4 '13 at 8:18
• There is no S2 on your circuit and no S0 in your truth table so this circuit makes no sense - please correct it. – JIm Dearden Oct 4 '13 at 10:29

Building L using a single 2-to-1 mux... and other logic

First, it is useful to construct the Karnaugh map based on your already constructed truth table:

S0 \ S1 S2
| 00 01 11 10
0  |  0  1  0  1
1  |  1  0  1  0

Solving for the minimum sum of products form we get

$L = S_0 \overline{S_1} \overline{S_2} + S_0 S_1 S_2 + \overline{S_0} \overline{S_1} S_2 + \overline{S_0} S_1 \overline{S_2}$

And note that the equation for a 2-to-1 mux would be

$y = x_1 x_2 + \overline{x_1} x_3$ simulate this circuit – Schematic created using CircuitLab

It is not possible to simplify L into the form for y. There is simply no way to do it, even if you invert any combination of the inputs. If you were allowed to use additional logic it would be possible. For example, we simplify

$L = S_0 \overline{S_1} \overline{S_2} + S_0 S_1 S_2 + \overline{S_0} \overline{S_1} S_2 + \overline{S_0} S_1 \overline{S_2}$

By factoring out the $S_0$ and $\overline{S_0}$ terms:

$L = S_0 (\overline{S_1} \overline{S_2} + S_1 S_2) + \overline{S_0} (\overline{S_1} S_2 + S_1 \overline{S_2})$

Simplifying the inner terms with the XOR and XNOR functions:

$L = S_0 (\overline{S_1 \oplus S_2}) + \overline{S_0} (S_1 \oplus S_2)$

Which is pretty straightforward to build this circuit: simulate this circuit

This is the closest I could get to what I think you are asking for.

An interesting simplification

Notice that the inner terms are complementary:

$L = S_0 (\overline{S_1 \oplus S_2}) + \overline{S_0} (S_1 \oplus S_2)$

If we set the inner term as another variable, $A$,

$A = S_1 \oplus S_2$

Then the equation for L becomes:

$L = S_0 \overline{A} + \overline{S_0} A$

Fascinating. Do you see it? Its again the equation for XOR:

$L = S_0 \oplus A$

Expanding $A$ we get

$L = S_0 \oplus (S_1 \oplus S_2)$

$L = S_0 \oplus S_1 \oplus S_2$ simulate this circuit

• Thank you for making my question more professional and your detailed explanation. We were to solve it for XOR's previous but then they wanted us to do it using the "most simple mux" and I thought maybe a 2-to-1 might be done but I see now a 4-to-1 is the only way. – ParoX Oct 4 '13 at 16:28
• @BHare, I always appreciate a logic puzzle, even if the expected solution doesn't exist. The 4-to-1 mux you had originally must be the correct solution. Oh and make sure to check that your tables and diagrams match. In your original post you used S1 S2 S3 in the table but accidently used S0 S1 S3 in the diagram! – travisbartley Oct 5 '13 at 0:01
• From the original table, you can see that L is simply the parity of the three inputs, 0 for even parity and 1 for odd. The is reflected in your three terms XOR'ed together. – tcrosley Oct 5 '13 at 0:09
• @tcrosley, that's true, an XOR function will always give 0 for an even number of 1's at the input, and a 1 for an odd number of 1's at the input, no matter how many inputs. Its also worth saying that an XOR function always has a checkerboard patterned K-map. So if you draw the K-map and see that pattern, looking for the XOR simplification might speed up the solution. – travisbartley Oct 5 '13 at 0:18

You'll probably need more than two 2:1 multiplexers to do this but the logic can be reduced to two exclusive or gates: - If you feed S2 and S3 to the inputs of the EX-OR gate your output pattern is correct for the lowest four states. If you take the output and feed it into another EX-OR gate with S1 on the other input you get what you want.