Sun, 22 Sep 2013, 21:21

A student writes:

 
> Hello Dr. Patt,
> 
> I'm emailing to ask for some clarification on #7B from Problem Set 2. The
> problem is quite difficult, and I've spent probably 2 hours total (by
> myself and with my study group) trying to figure out how to implement XOR
> with only two muxes. My study group and I were under the assumption that
> the only thing you could use was just two multiplexers. However, we have
> yet to find a solution that only uses two muxes and satisfies all 4
> inputs/outputs of the XOR function (we have multiple solutions that satisfy
> 3 of the inputs). Finally, we were able to come up with a solution that
> uses 2 muxes and an OR gate. Looking at the wording, you say we are not
> allowed to use an inverter, which may imply that other gates are at our
> disposal as long as we also use only 2 muxes (as opposed to using other
> gates and 3 muxes). Were we correct in our assumption that the only gates
> we can use is two muxes? I apologize if this question is redundant.


 
> <<name withheld to protect the student who noticed 7B is quite difficult>>


I am happy to hear that you and your study group are tackling this problem.
Yes, it can be done with two 2-input muxes and nothing else.

You are absolutely correct.  It is a tricky problem.  Every so often I like
to put a tricky problem in the homework to get you thinking way outside the
box.  I would not put it on an exam since I can not give you a problem on
an exam that is hard to solve in 2 hours even with the help of your study 
group.  But on a problem set, why not!

In fact, even if you don't get it, when you see the answer, the fact that you
made an honest effort at doing it yourself will result in even deeper 
understanding of the logic structures.

I suppose I could give you a couple of hints.

1. How many inputs does a 2-input mux have?  Be careful!
2. What are all the possible values an input can have?  Some values are
logical variables, some are logical constants.  Answer: A,B,0,1.

Hope this helps.
Yale Patt