The exercise from "Introduction to computer systems" textbook. At first, I figured out this arrangement:

But in the case of A=1, B=1, and C= 0 →

It short circuited to the ground. So then i figured out following arrangement:

But in the case of A=1, B=0, C=1 there isn't way to the ground since lower B gates open. Is it okay or this is also faulty case and i should always provide the pass to the ground in the zero out case?

 

I don't think your last diagram is quite correct. You're provided at least 3 states you know are valid. Your configuration must satisfy those before you fill in the rest of the table. Obviously, I won't give you the answer right out, but I will provide some clues and say this: In your last diagram, I agree with your assignment of transistor 3 and 4.

Here's a hint: transistors in parallel to each other will have different net assignments. For instance: transistor 5 wouldn't be "B," as that condition is already satisfied by the transistor in parallel to it. Likewise, transistor 1 also wouldn't be "B."

Let's walk through the logic:
For state 011, the bottom half should have an "open" somewhere (which is accomplished by transistor 4 = A), and the top half should be able to be shorted through (also accomplished by transistor 3 = A).

For state 100, the bottom half should be "open" somewhere, while the top half should be able to be shorted through. That means transistor 2 should either be B or C, as putting A there would make the top circuit open, so OUT would still be zero. But if transistor 4 = A, then transistor 5 will either be B or C in order to keep the bottom half "open" so OUT = 1 (because you don't want to short the bottom half to ground; that'd draw a ton of current and set your OUT = 0). Based on the hint I mentioned, I'll let you make a guess as to, based on this, which assignment transistor 5 should be.

For state 101, by this point you only have transistors 1 and 2 left. In this case, the bottom half will need to be shorted to ground, while the top half open. Transistor 3 = A will make that branch open, but Transistor 4 = A will only provide part of the short to ground you need. The bottom B branch will be open as well, as B = 0, so that transistor is not the path to ground. This state will confirm the assignment of Transistor 5 from the previous state, but leaves us with the top half still. The known "B" in the top half will allow us to say that there's a path from supply to transistor 2, based on B's current state. We already have assigned Transistor 3 to A, so that, like I said, is open, so the short in the top needs to come from the other branch, so Transistor 2 needs to correspond to the state that will short it. Which one of A, B, or C will short Transistor 2 in the final state? This will let you assign Transistor 2.

Now what's Transistor 1? Well, use the hint I mentioned earlier. We can (roughly) say that transistors 1, 3, and the top "B" are all in parallel, so what's the remaining option?


Edit: I want to add: if I did my own work correctly, I agree at least with the truth table you filled out. It's just that the chosen net labels are incorrect to generate that result.

 

@Edman83: The answer to the question at the end of your post is explicitly stated in the problem.

But in the case of A=1, B=0, C=1 there isn't way to the ground since lower B gates open. Is it okay or this is also faulty case and i should always provide the pass to the ground in the zero out case?

The problem states:



In general, unless there is a specific reason to do otherwise, you want the output of a logic circuit to be connected to exactly one logic state, either HI or LO. The exception is if you are intentionally implementing three-state logic, which is not the case here.

The approach that you appeared to take was to more or less randomly pick and assignment and see if it worked. While this will eventually yield a solution, it is extremely inefficient and does not scale well -- the number of possible signal assignments grows exponentially. Even in this circuit, you have five unassigned transistors and three available signals. There are thus 3^5, or 243 possible assignments (not including the possibility that one or more of them are hard tied to HI or LO, which would blow that up to over 3,000 possibilities, but the problem statement, as worded, precludes this since it specifically says that each gate is to be labeled with one of the three signal names).

You should approach this like you would something like Sudoku. Look at the constraints and see what decisions can be made with absolute certainty. Then look at the constraints that those decisions impose and repeat this process. You should only guess at something if there is no other choice and then you should guess at one thing and pursue it with an eye to determining if it is inconsistent with the problem and, if so, go back to that point and make a different guess.

Some other things to consider for this kind of problem. The equation that governs the top part is the complement of the equation that governs the bottom part (hence the name 'Complementary' MOS logic). Because of the difference in polarity of the logic between top and bottom, that also means that DeMorgan's Theorems are you friend.

Another thing to consider: The pulldown circuit has three transistors, while the pullup section has four. This means that the pullup section isn't as "simple" as it can be. This likely means that one of those transistors can be removed without affecting the circuit (but note that this does NOT mean that it can have just any input signal applied to it, but it's very possible that it can have one of a particular subset of input signals applied -- i.e., there may well be more than one correct solution to the problem).

Here is what I would recommend doing:

1) Focus first on the pulldown section (since it has fewer transistors).
2) Assign 'X' to one of the unassigned transistors and 'Y' to the other.
3) Write out the equation for OUTb (out-bar) in terms of X, Y, and B.
4) See if the partial truth table let's you determine the correct assignment for either X or Y. It may or may not.
5) Use DeMorgan's to change the equation for OUTb into an equation for OUT (i.e., take it's complement).
6) Compare this equation to the topology of the pullup section and see if you can determine any of the assignments that it requires. Not allows, but requires.

Before you do the above, you might see if you can find some low hanging fruit.

For instance, in the pullup section, Transistor #3 will force the output HI whenever the signal driving it is LO. Is this behavior inconsistent with the truth table for any of the inputs?

Similarly, when B is HI, are there any lines in the truth table for which the output must be HI? If so, you know that Transistor #4 must be off under those conditions. What does that tell you about which signals can possibly be applied to #4?

 

I don't think your last diagram is quite correct. You're provided at least 3 states you know are valid. Your configuration must satisfy those before you fill in the rest of the table. Obviously, I won't give you the answer right out, but I will provide some clues and say this: In your last diagram, I agree with your assignment of transistor 3 and 4.

Here's a hint: transistors in parallel to each other will have different net assignments. For instance: transistor 5 wouldn't be "B," as that condition is already satisfied by the transistor in parallel to it. Likewise, transistor 1 also wouldn't be "B."

Let's walk through the logic:
For state 011, the bottom half should have an "open" somewhere (which is accomplished by transistor 4 = A), and the top half should be able to be shorted through (also accomplished by transistor 3 = A).

For state 100, the bottom half should be "open" somewhere, while the top half should be able to be shorted through. That means transistor 2 should either be B or C, as putting A there would make the top circuit open, so OUT would still be zero. But if transistor 4 = A, then transistor 5 will either be B or C in order to keep the bottom half "open" so OUT = 1 (because you don't want to short the bottom half to ground; that'd draw a ton of current and set your OUT = 0). Based on the hint I mentioned, I'll let you make a guess as to, based on this, which assignment transistor 5 should be.

For state 101, by this point you only have transistors 1 and 2 left. In this case, the bottom half will need to be shorted to ground, while the top half open. Transistor 3 = A will make that branch open, but Transistor 4 = A will only provide part of the short to ground you need. The bottom B branch will be open as well, as B = 0, so that transistor is not the path to ground. This state will confirm the assignment of Transistor 5 from the previous state, but leaves us with the top half still. The known "B" in the top half will allow us to say that there's a path from supply to transistor 2, based on B's current state. We already have assigned Transistor 3 to A, so that, like I said, is open, so the short in the top needs to come from the other branch, so Transistor 2 needs to correspond to the state that will short it. Which one of A, B, or C will short Transistor 2 in the final state? This will let you assign Transistor 2.

Now what's Transistor 1? Well, use the hint I mentioned earlier. We can (roughly) say that transistors 1, 3, and the top "B" are all in parallel, so what's the remaining option?


Edit: I want to add: if I did my own work correctly, I agree at least with the truth table you filled out. It's just that the chosen net labels are incorrect to generate that result.

Your hint about transistor 1 is wrong. I was wrong only in choice of transistor 5. The final correct arrangement is:

It satisfies all requirements for each input from the table. Your hint implies transistor 1 should be C, but in this case state 110 would be short circuited:

 

@Edman83: The answer to the question at the end of your post is explicitly stated in the problem.



The problem states:

View attachment 347144

In general, unless there is a specific reason to do otherwise, you want the output of a logic circuit to be connected to exactly one logic state, either HI or LO. The exception is if you are intentionally implementing three-state logic, which is not the case here.

The approach that you appeared to take was to more or less randomly pick and assignment and see if it worked. While this will eventually yield a solution, it is extremely inefficient and does not scale well -- the number of possible signal assignments grows exponentially. Even in this circuit, you have five unassigned transistors and three available signals. There are thus 3^5, or 243 possible assignments (not including the possibility that one or more of them are hard tied to HI or LO, which would blow that up to over 3,000 possibilities, but the problem statement, as worded, precludes this since it specifically says that each gate is to be labeled with one of the three signal names).

You should approach this like you would something like Sudoku. Look at the constraints and see what decisions can be made with absolute certainty. Then look at the constraints that those decisions impose and repeat this process. You should only guess at something if there is no other choice and then you should guess at one thing and pursue it with an eye to determining if it is inconsistent with the problem and, if so, go back to that point and make a different guess.

Some other things to consider for this kind of problem. The equation that governs the top part is the complement of the equation that governs the bottom part (hence the name 'Complementary' MOS logic). Because of the difference in polarity of the logic between top and bottom, that also means that DeMorgan's Theorems are you friend.

Another thing to consider: The pulldown circuit has three transistors, while the pullup section has four. This means that the pullup section isn't as "simple" as it can be. This likely means that one of those transistors can be removed without affecting the circuit (but note that this does NOT mean that it can have just any input signal applied to it, but it's very possible that it can have one of a particular subset of input signals applied -- i.e., there may well be more than one correct solution to the problem).

Here is what I would recommend doing:

1) Focus first on the pulldown section (since it has fewer transistors).
2) Assign 'X' to one of the unassigned transistors and 'Y' to the other.
3) Write out the equation for OUTb (out-bar) in terms of X, Y, and B.
4) See if the partial truth table let's you determine the correct assignment for either X or Y. It may or may not.
5) Use DeMorgan's to change the equation for OUTb into an equation for OUT (i.e., take it's complement).
6) Compare this equation to the topology of the pullup section and see if you can determine any of the assignments that it requires. Not allows, but requires.

Before you do the above, you might see if you can find some low hanging fruit.

For instance, in the pullup section, Transistor #3 will force the output HI whenever the signal driving it is LO. Is this behavior inconsistent with the truth table for any of the inputs?

Similarly, when B is HI, are there any lines in the truth table for which the output must be HI? If so, you know that Transistor #4 must be off under those conditions. What does that tell you about which signals can possibly be applied to #4?

Thank you very much, the key was to start from the pulldown section. I didn't choose gates randomly, but i was starting from the pullup section. But frankly, i don't understand how DeMorgan's law works in the final arrangement:

By DeMorgan's law transistor 1 should be C, but it doesn't work:

And probably by DeMorgan transistor 2 should be A, that also doesn't work:

 

Thank you very much, the key was to start from the pulldown section.

View attachment 347159

That is ONE of the possible solutions. What would the truth table be if 'A' were applied to Transistor #1? Or if that transistor's gate were tied HI? Or if that transistor was simply removed? (Note that the latter two options, while physically viable, would violate the stipulation that each transistor's gate be driven by one of the input signals).

That the transistor is extraneous is apparent because both of those top two transistors are in parallel and driven by the same signal. One of them is therefore redundant by the Idempotent property that B+B = B.

But frankly, i don't understand how DeMorgan's law works in the final arrangement:

So let's walk through it.

I've given each unknown input a variable name for ease of reference:



Ignoring the low-hanging fruit, which would allow us to immediately see that X=L=A, and starting from basic CMOS requirements:

The logic equation for the pulldown section is

\(
\overline{OUT} \; = \; X \left( B\;+\;Y \right)
\)

Now apply DeMorgans to this, and you get

\(
\overline{\overline{OUT}} \; = \; \overline{X \left( B\;+\;Y \right)} \\
OUT \; = \; \overline{X} + \overline{\left( B\;+\;Y \right)} \\
OUT \; = \; \overline{X} + \overline{\left( B\;+\;Y \right)} \\
OUT \; = \; \overline{X} + \overline{B} \cdot \overline{Y}
\)

The OR is accomplished by placing transistors in parallel, so the pullup section has a single transistor between power and the output that is driven by X (i.e., L=X).

The AND is accomplished by placing transistors in series, so the pullup section has a path between power and the output that goes through B and Y. This means that K=Y.

At this point, we can see that Transistor #1 is extraneous. But since it has to be connected to one of the signals, which options are available?

It is in parallel with B, so it combines via OR.

\(
OUT \; = \; \overline{X} \;+\; \left( \overline{B} \;+\; \overline{J} \right) \cdot \overline{Y} \\
OUT \; = \; \overline{X} \;+\; \overline{B} \cdot \overline{Y} \;+\; \overline{J} \cdot \overline{Y}
\)

If J=B, it reduces immediately, by idempotence.

But if J=X, then the last term gets absorbed by the first term, so this is also a viable choice.

Notice that, up to this point, we haven't made a single reference to the truth table. We've only looked at the constraints imposed by the CMOS equations for the two sections.

Now let's consider the truth table.

We are given that the output is HI for ABC = 011. But since B is HI, that means that X must be LO to disable the pulldown section, which requires that X=A (that's the low hanging fruit I was referring to).

Next, the output is LO for ABC = 101. But since B is LO, that means that both of the other two transistors must be HI. That can actually be accomplished by setting Y=A or Y=C, so this doesn't tell us absolutely what Y has to be, but we know it can't be B.

But we've already determines that L=X, so L=A. That allows us to determine that the top half of the truth table is all HI.

I have to leave for the day, so I will leave it here and let you see if you can reason out the rest.


Which has to be the logic equation for the pullup section.

Now apply DeMorgans to this, and you get

 

Your hint about transistor 1 is wrong. I was wrong only in choice of transistor 5. The final correct arrangement is:
View attachment 347154
It satisfies all requirements for each input from the table. Your hint implies transistor 1 should be C, but in this case state 110 would be short circuited:
View attachment 347155

Ah, my bad. I’ll have to check my work again; I must’ve missed this issue with this particular state when running through the currents in my head.

 

Ah, my bad. I’ll have to check my work again; I must’ve missed this issue with this particular state when running through the currents in my head.

I just now got home from work and had the chance to check my notes. I figured out the confusion - I set transistor 2 to B, not C. So I had transistor 1 = C, and 2 = B. However, with that said, I still erred because the 101 case I had would be shorted to ground instead (through my assignment of transistor 5). So I was still mistaken, but in a different way. What's particularly embarrassing is that I had even mapped the currents for that case and had even noted that there was a path to ground. WBahn's method is much more reliable.

 

That is ONE of the possible solutions. What would the truth table be if 'A' were applied to Transistor #1?

Indeed, you're absolutely right, 'A' in transistor #1 meets to all the requirements! And looks like 'A' is more appropriate (not Idempotent) since doesn't repeat itself like in case with 'B'. But i have some questions to your explanation:


Where did you find out that DeMorgan's laws can be applied to only one variable (OUT)? The original statement implies two variables:
Not (A and B) is the same as Not A or Not B.

Not (A or B) is the same as Not A and Not B.
In case of X*(B+Y) we can imagine B+Y like one variable Z (for example). But what about single OUT?

The OR is accomplished by placing transistors in parallel, so the pullup section has a single transistor between power and the output that is driven by X (i.e., L=X).

The AND is accomplished by placing transistors in series, so the pullup section has a path between power and the output that goes through B and Y. This means that K=Y.

Where did you find out that logical operations correspond to transistors arrangement? I’m curious where you learned these concepts, because the book (" Introduction To Computing Systems: From Bits & Gates To C/C++ & Beyond (3rd Edition) ") this exercise is from doesn’t mention them at all.

 

Indeed, you're absolutely right, 'A' in transistor #1 meets to all the requirements! And looks like 'A' is more appropriate (not Idempotent) since doesn't repeat itself like in case with 'B'. But i have some questions to your explanation:

View attachment 347314
Where did you find out that DeMorgan's laws can be applied to only one variable (OUT)? The original statement implies two variables:
Not (A and B) is the same as Not A or Not B.

Not (A or B) is the same as Not A and Not B.
In case of X*(B+Y) we can imagine B+Y like one variable Z (for example). But what about single OUT?

DeMorgan's is being applied to the right-hand side.

The first line is simply negating both sides of the original logic equation. The second line, on the left, is simply applying complementarity to the left side to remove the double negation.

Where did you find out that logical operations correspond to transistors arrangement? I’m curious where you learned these concepts, because the book (" Introduction To Computing Systems: From Bits & Gates To C/C++ & Beyond (3rd Edition) ") this exercise is from doesn’t mention them at all.

If you have two switches, A and B, that are in series with a battery and a light bulb. What is the logical relationship between a switch being True (ON) and the light being True (ON)?

Simple, both switches must be ON in order for the light to be ON. That's a logical AND, right? What is the two switches are in parallel? Now the light will be ON if either (or both) switch is ON. That's a logical OR, right?

Don't make things harder than they are.