Determining the sign bit of adder alu

If the sum of both inputs is large and has an overflow then wouldn't it be possible that my sign bit could change although it should be the opposite of what it's changed to. And then showing a positive when it should be a negative. If that makes any sense. Or have I just not followed this through fully?

Thanks for the reply

There certainly can be an overflow.  If this happens, then the sign bit won't reflect the sign, and you won't have a way of knowing how many bits were "overflowed" and were lost.  For this reason, when an overflow is detected on an arithmetic operation, the result is bogus and an error condition is raised.

    Am I missing the point of your question?
     -dZ.

No that's right, so how do I get around this.

What I want to do is: in my language I have two different instructions for adding or subtracting signed and unsigned words. And so:

If it is a signed calculation then I want to perform the calculation on the mantissa [First 7 bits] and set the sign bit to what it should be. Negative or positive depending on the calculation.

The only thing I have come across in relation to this is a statement saying that the "two words need to be compared in order to determine the sign bit!. But the site I saw that (berkeley.edu) had no further explanation or logic gate examples.

Hum, I must be missing something.  It seems to me that you want to retain the sign bit regardless of an overflow.  Why is this?

To avoid overflow, you just need higher resolution (more bits), or emulate it by splitting the inputs into smaller chunks and adding the parts in series, feeding the carry of each part to the next one.

Can you offer a link to the document to which you refer so that I may further understand what you are trying to do?

     -dZ.

Here's the link: http://inst.eecs.berkeley.edu/~cs150/fa05/Lectures/23-ArithI.ppt#261,6,Number Systems

Although it doesn't say a whole lot.

Attached is an image, basically three standard adders strung together with an XOR on the B input which allows for addition and subtraction. As you can see in the image it isn't working.

But from everything I read this is just a standard setup for performing addition / subtraction.

So i need to add the two Words together determining if the result is a negative or positive number somehow and set the MSB (Sign bit) to the relevant bit for a negative or positive result. Also if the penultimate bit has a carry then if performing signed calculation this carry should be spat out wherever (Overflow register), obviously this will need some selection mechanism to determine that we are calculating a signed number and if so not to perform calculation on the sign bit and to take the overflow from the penultimate bit instead.

It's making sense in my head it's just explaining it that i'm not too good at, my apologies.

Perhaps your circuit design is faulty.  I'm a bit rusty on logic circuits, but I thought that a full adder should look like this:

http://en.wikipedia.org/wiki/Image:Full-adder.svg

(Sorry, I submitted before I finished the comment.)

That image I sent was a quick composite of 4 full adders I just made, and it's missing the XOR gate to allow for addition and subtraction.

    -dZ.

Silly mistakes hey, thanks for pointing that out I wouldn't have gotten anywhere otherwise.

Ok so I have modified my design, am I going to have the same issues with the sign bit and overflow??? Can you envisage any problems with this. Obviously it is going to be an 8 bit adder not the three bits i'm showing at the moment.

This is always going to perform a twos complement isn't it, I need it to only perform the two's complement on a selection bases. If i'm using signed words constantly the highest I can go is -128 to 127 without the sign I can add up to 255 with my 8 bits. Just need some pointers to help me do this as I don't know where to begin.

If i put an AND gate on the penultimate overflow to the xor gate and use that as my overflow selection mechanism. Then i should be able to happily add two full 8 bits together without there being a sign bit???
That seems to be right.

But if I do a subtraction on two unsigned words and that subtraction is a negative and doesn't overflow the first 7 bits than somehow I'd want to detect that and set the sign bit and possibly a "sign register" to indicate the two unsigned words have a negative subtraction value and so have been converted to a signed result.

Remember that a full adder is combinational logic and you can always revert to a truth table to build and correct your logic, just build a truth table and a few karnaugh maps and the correct logic will reveal its self.

If you are going to perform subtraction (or addition of negative numbers), you always need the sign bit, which means that you will be using "signed integers".  This will always limit your range, because you have one less bit to use.  If you want to allow for a full 8-bit ALU, you need to then use 9 bits (you need one for the sign).

I still do not understand what your problem is and why the concern about the overflow and the sign bit.  The risk of overflow will *always* be there.  This is true for any number of bits (if you add the maximum number of bits, the result will never fit).  When the Carry-Out bit of the last Full Adder is different than its Carry-In bit, an overflow occurs, it indicates an error condition.  This is encoded in any programming language that I know (including Assembly Language, where you always check the Overflow flag after operations, unless you can be sure that the values are small enough to fit).

To detect overflow (and thus, add an "Overflow Flag" to your circuit), you can just add an XOR gate at the end of the circuit whose inputs will be the Carry-In and Carry-Out of bits of the MSB Full adder.

Here's more information on this, including mathematical explanations:
http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Comb/overflow.html

Is one of your requirements to overcome overflows and try to assess the answer from the register?

     -dZ.

I forgot to say something.  The reason that Overflow is detected and flagged, but not overcome, is because the Overflow condition means that the result cannot be represented in the available register, and thus, cannot be used by the machine.

For example, if you build an 8-bit computer and the addition of two 8-bit values results in an overflow, even if you were able to extract what the correct value is, what are you going to do with it? It doesn't fit in any of your registers; it cannot be stored in 8-bit memory, and cannot be transfered via 8-bit busses.  Thus, it is an invalid value for your machine.

This means, as you said before, that an 8-bit machine that operates on signed values, can only use values from -127 to +127 (because it needs the eighth bit for the sign), and if values are of the same sign, it may overflow.  So the effective range of the operands of addition is smaller than that.

If you want your machine to operate on 8-bit values (excluding sign), then you need to use 9-bit registers and Adders.  The result, still, cannot be equal to or larger than the sum of two values of the maximum magnitud, of the same sign.

    -dZ.

Detecting the overflow wasn't a requirement. My lecturer said you may want to use different mnemonics in your language for adding signed or unsigned numbers. So my language would have::

add               a,b
addsigned    a,-b
sub               a,b
subsigned    -a,-b
etc.

Now if I add two unsigned numbers and they're too large then I get overflow error, that's fine.
Adding two signed numbers works fine if it overflows then i get an error, fine.
Subtracting two signed numbers could be greater than 128 and an overflow occurs, that's fine.

So the logic circuit allows you to choose to add/subtract signed or unsigned numbers which I have done and from going through it it seems to work (I need to test it a bit more as I think the overflow has issues).

My only issue now is subtracting of two unsigned positive numbers. ie:

sub   2,8   (00000010 - 00001000)

Should produce -6, well that's what i want it to do. So i need to know if this happens and as long as the number isn't greater than -128 to detect it and set the sign bit to 1 and a register to indicate the result is a signed number.

However

sub  8,2  (00001000 - 00000010)

Should simply be 6 which it is.

To subtract, all you need to do is take the Two's Compliment of the second operand, and add.  This will work whether it is positive or negative.

sub   2, 8
    00000010 =>    00000010  =  2
  - 00001000 =>  +11111000  = -8
                          ---------------
                           11111010  = -6  Carry = 0, Overflow = 0

sub 8, 2
    00001000 =>    00001000  =  8
   -00000010 =>  +11111110  = -2
                         ----------------
                        1 00000110  =  6  Carry = 1, Overflow = 0

In the second case, there is a Carry-Out value on the MSB, but since it is the same as the Carry-In of the MSB adder, then it does not signify an overflow, so it can be safely discarded.

Signed and unsigned arithmetic should not require different circuitry; the bits are moved exactly the same for both.  The only difference is their contextual meaning: an unsigned number uses the MSB as part of the value, while a signed number uses it as the sign bit.  Any operation should not care about this at all.  The only time you care about this is when you are taking input or providing output.

     -dZ.