Friday, September 18, 2009 11:19 PM,
A student writes:
Professor Patt:
Im a student in your 306 class. And I was working with my group
on the problem set and we had a question concerning problem 6B.
One of the conditions of the problem is to not use a "NOT GATE".
Do you mean by that like dont use INVERTERS on our muxes?
Thanks
<<name withheld to protect the student wanting to use INVERTERS>>
Actually, the problem is even more restrictive than that. You are being asked
to implement a logic circuit consisting of ONLY two 2to1 MUXes that provides
at the output A XOR B. You are not allowed to use inverters, AND gates, OR
gates or any other gates. Just two 2to1 muxes.
Recall that a two2one MUX has two sources X and Y, one output Z, and one
select line S. X, Y, and S can be either A, B, 0, 1 or the output of the
other MUX.
We put this problem into the problem set because some students like the
challenge of a tricky problem. The fact is, we would never put a problem like
this on an exam because in addition to testing your understanding of MUXes and
the XOR function, you have to see the trick. And, we have far too much
understanding to test to bother putting trick questions on an exam.
However, for homework, we thought we would provide the opportunity for joy for
those who solve 6b. If this is not you, feel free to use more than two
2to1 MUXes (but ONLY 2to1 MUXes), which removes the trick from the problem.
I apologize for not labeling Problem 6b with a warning: THIS IS A TRICK
QUESTION for those who like to solve tricky puzzles. For the rest of you,
feel free to use a third 2to1 MUX.
Let me also supply a hint for using MUXes to implement arbitrary logic
functions.
If you recognize that only one input combination can be present at one time,
one could use the input variables for the Select lines, and the output for
that input combination as the source when the Select lines are so chosen.
_ _ _ _
For example, suppose we want to implement f(a,b,c) = abc + abc + abc
That is, the truth table looks like:
a b c | f
------|---
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 0
1 1 1 | 0
We can implement this with an 8to1 MUX as shown below:
0 0 1 1 0 1 0 0
| | | | | | | |
| | | | | | | |
v v v v v v v v
-------------------------
3 \ /
a,b,c --/-->\ /
\ /
-------------------
|
|
V
f(a,b,c)
Now, your job: Problem 6b. Implement A XOR B using ONLY 2to1 MUXes, and
if you can't do it with two of them, use three and get full credit.
Good luck with the rest of the problem set as well.
Yale Patt