How can I find the full adder I/O in the entire design?

[altameemi]

Hi

I designed an ALU that can executes input instructions and produces results with associated status flags. I'm just confused how the overflow sign can be generated, which is the XOR of carry out  of bit-14 and carry out of bit-15 (in case of 16-bit CPU). To be more precise, How can I find the carry out of the 14th full adder? I catch it, as illustrated in the snip verilog below, but I think it is not practical  method and it is consuming as well.

input [15:0] X;

input [15:0] Y;

reg [15:0] result;

reg [14:0] sub_results;

.

.

always ...

{carry_out_15,result} = X+Y;    //here I get the 15th (last) carry out

{carry_out_14,sub_result} = X[14:0]+Y[14:0]; // here is the 14th carry out

Thanks in Advanced

Ammar

[eteam00]

In signed integer arithmetic, the MSB ( bit [N-1] ) is the sign bit.

If you sign extend the integer to [N+1] bits, bit [N] will equal bit [N-1] which equals the sign bit.

If you perform an add or subtract operation with two signed N-bit operands, with an N-bit result you cannot tell if the operation resulted in an overflow or not.

If you sign-extend the signed N-bit operands to N+1 bits, and then perform the add or subtract, result bit[N] and result bit[N-1] should both be the sign bit of the result (they should both be the same).  The N+1 bit result will signal an overflow if result bit [N] differs from result bit [N-1].  In a non-overflow result, bit [N-1] and bit [N] should be equal copies of the sign of the result.

Sign-extending the operands and result is the cleanest (and probably least expensive and most easily understood) solution for overflow.

Another approach -- the bit-hacker approach -- would be as follows (assuming signed 16-bit operands and result):

CRY[14] = A[15] XOR B[15] XOR SUB_B XOR RESULT[15];

OVF = CRY[14] ? ( ~A[15] AND ~(B[15] XOR SUB_B) ) : A[15] AND (B[15] XOR SUB_B);

As you posted, overflow is the logical XOR of carry out from bit[15] and carry in to bit[15].  In the above example, the carry out from bit[15]  -- IF there is NO carry in from bit[14] -- is:  

A[15] AND (B[15] XOR SUB_B)

If there IS a carry in from bit[14], carry out from bit[15] is:

A[15] OR (B[15] XOR SUB_B)

The carry in to bit[15] is the XOR of what result[15] would be without carry in from bit[14] -- XORed with the actual result bit[15].  Here is result[15] without carry in from bit[14]:

A[15] XOR B[15] XOR SUB_B

Therefore, this would be carry IN to bit[15] (i.e. CRY[14] ):

A[15] XOR B[15] XOR SUB_B XOR RESULT[15]

Using the calculated carry IN to bit[15] as a selector, overflow would be:

CRY[14] ? ( ~A[15] AND ~(B[15] XOR SUB_B) ) // if carry in and no carry out
          : A[15] AND (B[15] XOR SUB_B);    // if carry out and no carry in

- Bob Elkind

[ywu · Accepted solution]

For the 16-bit result case, since we are using Verilog, how about

assign overflow = ((a[15] == 1'b0) & b[15] == 1'b0) & (result[15] == 1'b1)) | ((a[15] == 1'b1) & b[15] == 1'b1) & (result[15] == 1'b0));

This way it is self-explanatory what the overflow conditionit is and just let the synthesis tool to figure out the actual equation.

[altameemi]

Thanks Jim, I was running around. You reminded me with Overflow rule, which is if the both operands are in different sign, the overflow never occurred, while if the operands have the same sign, the result have to be in the same sign of operands. But what about case of ADD with Carry and Subtract with Borrow? where three and four operands enter respectivelly.

Regards

Ammar

[eteam00]

You reminded me with Overflow rule, which is if the both operands are in different sign, the overflow never occurred, while if the operands have the same sign, the result have to be in the same sign of operands.

For ADD, yes.  For SUB, no.

But what about case of ADD with Carry and Subtract with Borrow?

where three and four operands enter respectively.

Hmmm... you skipped my post.  Good to know the time I spent answering you was appreciated!

Jim tried to simplify his answer for you, but apparently either Jim's answer or your original question was over-simplified.

Read my first post/answer, and see if it makes sense to you.

- Bob Elkind

[altameemi]

Dear Bob

I 'm really appreciating sharing your experince with me as well as your time, so accept my excuse please. With respect to your first solution is completely understood. But for the second part, I'm just confused how you calculate CRY 14 from the bits 15 of entered operands. I also didn't understand what SUB_B is.

---

For ADD, yes.  For SUB, no.

---

we can opposit the rule in case of SUB to be: If the both operands have the same sign, the Overflow never occurred. If the the operands sign are different, we can get OV from this:

assign OV = ((x[15] && ~y[15]) && ~result[15]) | ((~x[15] && y[15]) && result[15]));

But we will have an exception in case one opernad equal 0x8000, which is have the same 2nd complement.

Best Regards

Ammar

[eteam00]

how you calculate CRY 14 from the bits 15 of entered operands

If the XOR of (operands) A[15] and B[15] is different than result[15], then there was a carry in to bit[15] from bit[14].

didn't understand what SUB_B is

I presumed that your ALU needs to detect underflow/overflow for SUBTRACT as well as ADD.  SUB_B is shorthand for distinguishing "A_+_B" function from "A_-_B" function.

But we will have an exception in case one opernad equal 0x8000, which is have the same 2nd complement.

I assume you meant to say "2s complement" rather than "2nd complement".

This is your ALU design, you get to set the rules for operand range and result range to suit your design.  Or perhaps you design your ALU to suit the operand/result requirements.  I described a design approach which would handle overflows and underflows and multiple (more than 2) operands quite nicely.  Did this make sense to you?

- Bob Elkind