half subtractor, full subtractor, overflow

Thread Starter

PG1995

Joined Apr 15, 2011
832
Hi

Please have a look on the attachment. It has my three questions. Please help me with them. Please note AAC automatically resized the image to lower resolution so I believe you would have difficulty in reading the text in the attachment, therefore you can also have a look on full sized image here. Thanks.

Regards
PG
 

Attachments

Georacer

Joined Nov 25, 2009
5,182
Okay, moving on to adders/subtractors.

A half adder/subtractor is a unit that does an operation between two bits, disregarding the result of previous bits in the same numbers (carries, results).
A full adder/subtractor takes into account borrowed units from previous bits, allowing for a fully scalable system.

Let's examine addition first. Say we want to add 11+01. If we used a half adder in both bits the result would be:
LSB=1+1=0 and 1 carry
MSB=1+0=1
Sum=10, which is clearly wrong. It is wrong because we didn't take the carry of the LSB operation into account. But the half adder can't take all three inputs (MSBa, MSBb, carry) into account because it has only two inputs.

There is where the full adder comes into play. It is constructed from two half adders and has three inputs, to read all three info bits, two addendums and the carry from the previous step.

The same operation would then be:
LSB=(1+1+0)=0 and carry-out=1. In the LSB we always set carry-in=0
MSB=(1+0+carry-in)=(1+0+1)=0 and carry-out=1. The last carry-out of the addition is the overflow bit.
Thus the result is 100, which is the correct one.

So, in short, the half adder/subtractor has two inputs, one sum output and one carry-out output.
The full adder/subtractor has three inputs (bit1, bit2, carry-in) and two outputs (result, carry-out). The carry in is the carry-out of the previous step. The carry-out will be used as a carry-in in the next step.

The table you have highlighted is the boolean function of the full subtractor. It is read like this:
eg line 3 (in orange): When we have the operation 0-1 and we have a carry-in from the previous step, the result will be 0 and the carry-out will be 1. In other words 0-1-1=0 and carry-out=1

You can Google easily many resources about full adders/subtractor, or try Wikipedia. The topic is exhaustively discussed with many examples.


About your Q3, read the text after the highlighted lines once again. What it says essentially is this. If you do an operation among two signed numbers and there is an overflow, the MSB bit (bit 8 in your case) will now be part of the number itself, and the overflow bit is now the new sign bit. You can verify this by looking at the two examples given in the page.
But since your system can only "see" 8 bits in a number, whenever you have overflow in an operation the result it will see will be invalid.

Ask further after you research a bit for the full adders and subtractors. AAC has a page on full subtractors too (http://www.allaboutcircuits.com/vol_4/chpt_9/3.html)

Then come back with your questions.
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Thank you, GeoRacer,

I understand the function of subtractor now. Could you please have a look on the attachment and let me know what you think about the comment I made there? Thanks a lot.

Best wishes
PG
 

Attachments

Georacer

Joined Nov 25, 2009
5,182
That schematic isn't very helpful, but we 'll make do. This schematic implements the operation of multiplication:

The yellow lines aren't carries. In the first row, the yellow line with the value 0 is to fill the MSB for the addition x3x2x1+y3y2y1y0=ct3t2t1t0 (temporary).
In the second, the yellow line is the carry out of the above operation, and the new operation is ct3t2t1+z3z2z1z0=c6c5c4c3.
In the last line the yellow bit is the carry out of that previous operation.
 

Attachments

Thread Starter

PG1995

Joined Apr 15, 2011
832
Hi

Please have a look on the attachment and let me know if I have it correct. I haven't done it completely. Thank you.

Regards
PG
 

Attachments

Georacer

Joined Nov 25, 2009
5,182
Not quite right. You should write that D0'=E'+A0+A1 eq D0=EA0'A1'. Same for the rest.

Since you are required to use only NAND or NOR gates, I would make the NOT gates out of these gates too.
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Thank you very much.

Not quite right. You should write that D0'=E'+A0+A1 eq D0=EA0'A1'. Same for the rest.
Did you write complement of D0, "D0'", on purpose?


Since you are required to use only NAND or NOR gates, I would make the NOT gates out of these gates too.
Okay. We can use a NAND gate to implement a NOT gate, can't we?

Please clarify the above points. Thank you.

Best wishes
PG
 

Georacer

Joined Nov 25, 2009
5,182
It was on purpose. In the first K-map, you grouped the 0s, thus the result is an SoP expression for D0', not D0.
The correct SoP is D0'=E'+A0+A1 which is equivalent to D0=EA0'A1'.

A NOT gate can be built by a NAND gate with common inputs or a NOR gate with common inputs.
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Thank you.

It was on purpose. In the first K-map, you grouped the 0s, thus the result is an SoP expression for D0', not D0.
The correct SoP is D0'=E'+A0+A1 which is equivalent to D0=EA0'A1'.
To me, it look there is little confusion. Actually under the K-map I have both SoP and PoS expressions. Please have a look again. Do you still find it incorrect? Please let me know. Thanks a lot.

Best wishes
PG
 

Attachments

Georacer

Joined Nov 25, 2009
5,182
Think about it. You write that D0=EA1'A2'=E'A0A1. Is that possible? No, it's not.

You have forgotten how to extract the PoS form. Let's revise it.

We start forming the SoP form of the D0'. That means that we group the 0s of D0. The SoP form of the 0s is D0'=E'+A0+A1. Then, we complement that expression to get the PoS form of D0. D0=(D0')'=(E'+A0+A1)'=EA0'A1'.

It might be confusing, but in this case the SoP and PoS forms are identical. This is because we have only one minterm to deal with.

Remember that both NAND-NAND SoP form and NOR-NOR PoS form require a two-level circuit.
That means that for the SoP form you must NAND the term EA1'A0' and then invert the result.
On the other hand in the PoS form (D0=(E)(A1')(A0')) you must invert the sums E, A1' and A0' and then feed them into the final NOR gate.

Is it a bit more clear?

Try to have a bit more comfort by knowing this is what I 'm trying to understand for my next exercise: http://projecteuclid.org/DPubS/Repo...w=body&id=pdf_1&handle=euclid.aoms/1177729586
I 'll probably take a shortcut and read here instead: http://en.wikipedia.org/wiki/Stochastic_approximation
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Think about it. You write that D0=EA1'A2'=E'A0A1. Is that possible? No, it's not.

You have forgotten how to extract the PoS form.
I'm sorry but I still don't see any error. I always follow this when converting between PoS and SoP (see the last paragraph,or check this related thread).

Here I have "1" in only one cell which stands for a single minterm. But I want PoS form to use NOR implementation. After simplification, I end up with this PoS expression: D0=E'A0A1.

Where am I going wrong? Please help me with it. Thank you very much.

Best wishes
PG
 

Georacer

Joined Nov 25, 2009
5,182
OK, let's forget about SoP and PoS. Look at the functions EA0'A1' and E'A0A1. Are they equivalent? Put them in a truth table and you will see that they are not.

A Boolean function, either it is expressed as SoP or PoS must have the same truth table. A truth table is a unique representation of a function. If two functions have the same truth table they are equal. If they don't, they aren't.

I think we both agree that the SoP of D0 is EA0'A1'. So far so good?

As we have said before, we extract the PoS expression by grouping the 0s of a K-map. That way, we build an SoP expression of D0' first.

Then, we invert that expression to obtain the PoS expression of D0.

So for the two steps above, we have:
D0'=Σ(0,1,2,3,5,6,7)=E'+A0+A1, which is a SoP form.

D0=(D0')'=(E'+A0+A1)'=EA0'A1', which is a PoS form and has the following circuit:


Do you agree with me? Up to which point?
 

Attachments

Thread Starter

PG1995

Joined Apr 15, 2011
832
I'm not disagreeing with you. Rather, you and Floyd are at disagreement. Here, Floyd says something different about conversion between SoP and PoS. When you say that when we group all the cells which contain 0's we get SoP of F'. That's I understand and there is no conflict. But when you say that to get PoS you have take complement of F'. In the thread I also referred to what Morris Mano says. I believe your approach is closer to his. But is Floyd wrong then? Please help me with it. Thank you.

Best wishes
PG
 

Thread Starter

PG1995

Joined Apr 15, 2011
832
Oh!!!

I did it wrongly. Floyd isn't wrong. I just checked it again. You see in PoS when the variable is "0" which write without a complement and when it's "1" it's written with complement. Just see my grouping. I didn't follow the rules. So sorry for all this. I should have been more careful. Many, many thanks.

Best regards
PG
 

Georacer

Joined Nov 25, 2009
5,182
Your problem is that Floyd doesn't say anything about complementing any function, right?

You are probably getting confused because Floyd extracts the PoS of F in one step fro the Karnaugh Map. He uses the 0s of F to create maxterms of F not minterms, which is the same as creating minterms of F' and then complementing them.

Notice that the groups for the 0s in the positions 2 and 3 in your old attachment result to A+B+C', which is a maxterm of F, not a minterm of F'.

Does that help?

And please stop pleading for help, it's getting awkward. Thx :D
 
Top