

Hello, I am having trouble with the gate implementation. So basically, I think I missed something and that I am over complicating things. For example, My last gate that I finally managed to create was the MUX gate. I ended up creating it from 7 AND gates 3 NOT gates and 3 OR gates. I can tell you maybe my thought process or how I make the gates. First I get the Truth Table and then I add the Boolean algebra and in the end I end up having like 13 gates. Like this:
a b sel out
0 0 0 0
0 1 0 0
1 0 0 1 ((a) AND (Not b)) AND (Not sel) OR
1 1 0 1 ((a) AND (b) AND (Not sel) OR
0 0 1 0
0 1 1 1 (Not(a) AND (b)) AND (sel) OR
1 0 1 0
1 1 1 1 ((a) and (b)) and (sel))
I am asking this because after a finished I looked up a solution from another guy and he had 4 gates in total. So what am I doing wrong?
P.S English is not my first language. Sorry for mistakes.

Administrator

You aren't doing anything 'wrong' and your approach is completely valid; for this course, all that really counts is getting an implementation that functions correctly. This is not a logic design course, so there is no expectation that you be able to do logic minimization or apply more efficient design techniques such as Karnaugh maps. In fact, the very premise of designing everything using 2input NAND gates defeats any attempt at coming up with the 'best' implementations from most standpoints such as speed, power, or cost optimization. But that's fine, because the purpose of the premise is to teach a logical progression of concepts, not actually implement a high performance processor.
To underscore that, the Xor design that the authors offer in Figure 1.5 uses the exact same approach you did and it makes the conceptual link between the gate's functionality and implementation very apparent, but it is a horrible design from just about any other conceivable metric. But that doesn't matter because the objective was specifically to make that conceptual link easy to see and understand  job accomplished.
Having said that, your desire to understand how to do a better job of designing the gate logic is laudable and worthwhile. A good place to start is to study the 4gate design you found and confirm for yourself that it does correctly implement the logic by building up the truth table for it. While you are doing that, identify which parts of the circuit are implementing which portions of the truth table and then look at how those portions are being brought together.
Your approach is a very bottomup, algorithmic one which has the advantage that it will always work on any arbitrary logic function. The disadvantage is that it leads to correct, but very inefficient designs.
Another approach is to come at it from the top down and base your design on the functional goals of the part in question. For instance, with a Mux the goal is to have two channels  an A channel and a B channel  that are combined into a single output.
Now consider what an Or gate does from a functional standpoint. Yes, it's output is HI if and only if at least one of it's inputs is HI, but that's too lowlevel a description. Consider this alternative: If one of the inputs is LO, then the output is equal to the other input (but if that first input is HI, the output is forced HI). So now I have a description that lets me see how to use an Or gate to combine two channels as long as I have a way to force the channel that I'm not interested in to be LO.
So now I have a simpler problem. Given a data signal, how can I use another signal to either let the output be equal to the data signal or force the output signal to be LO? Well, let's consider a functional description of an And gate. Again, describing it as a gate in which the output is HI if and only if all of its inputs are HI is too lowlevel. Instead, consider that if one input is HI, the output is equal to the other input (but if that first input is LO, the output is forced LO). Sounds like just what we need.
Now I just need to be able to take the select input and make it so that whatever control signal is sent to one channel, the opposite control signal is sent to the other. That's a description of what a Not gate does.
So now I can put together a Mux using one Not gate, two And gates, and one Or gate. Is that the design you found. If so, it might sound like a winner, but it is still pretty bad considering that an And gate requires two Nand gates and the Or gate probably uses three. So now you are at eight Nand gates. But the design can be done using just four Nand gates.
Bottom line is that while exploring how to make better implementation decisions is a worthwhile objective, don't let pursuing it interfere with progressing down the primary objectives of this course, which is to build increasingly complex logic constructs that work (regardless of how 'well' they might work) from simpler ones.


Wow, thank you for your quick and thorough reply. My only concern was, that it will be much complicated to solve the upcoming gates, with much more input pins, but I see now that it wont, because the 16 bit input could be viewed as "one" input(I hope I am going in the right direction with this). Regarding the efficiency, performance, speed and so on, was not a big issue for me, because I didn't started this course to for those reasons, I started it because I wanted to have a better understanding of how computers function, so I could ultimately learn a programming language and be good at it. Every course I've done so far, didn't get me the satisfaction of deep understanding, and I have a huge issue if I don't see the whole picture. Thank you once again for your reply.


Hello again, I just found out a more "elegant" solution for the Mux gate, and I think sharing it here can be helpful to others also. So instead of looking at the whole truth table, i started of with the shortened version of it, which looks like this:
sel out
0 a
1 b
so what this basically means is
if sell==0
out = a
else
out = b
meaning we only have two options for our output, which are:
1. Option : out = NOT(sel) AND a
OR
2. Option: out= sel AND b
With this solution, I get only one NOT gate, two AND gates, and one OR gate.
Very easy actually, and much easier to follow then having 7 AND gates, 3 NOT gates, and 3 OR gates. I hope this will be helpful to others.

