Calculating the sign of a carry-save number

Question

Does anyone know how to calculate the sign of a number in carry-save format, i.e. with a virtual sum and virtual carry, without adding them together? A verilog example would be ideal. Thanks!

Answer 1

Unsigned version: Compare two numbers (my warmup):

Of course you have to go through some of the numbers, but just by starting from the most significant bit (I assume we talk about unsigned numbers). The algorithm is sort of a carry-save algorithm but backwards:

An example:

0001111010101 = the number to compare with
0000211002000 = the carry save number

start from top

0 = 0
0 = 0
0 = 0
1 > 0   - ops! keep the compare-number
0 = 2 - phew! (02 = 10)
1 = 1 
1 = 1 
0 = 0 
0 = 0
1 < 2 :: aha! Carry save number wins!

When we talk about signed numbers, you want to make sure that the most significant bit is set (and do not care about any other result), or rather eliminate the possibility that lower carry-sign bits influence on the result.

When you add two numbers the only possibility for them to change a bit higher than they are is that one of them is that they have more than one bit set at an individual bit. Hence, as soon as you find an occurenct where both of the bits are zero, you can be sure that you will have a positive (not overthrowing number).

An algorithm for the sign would be answering the question "can the sum of the lower bits change in carry and sign numbers change the bit i'm looking at right now?"

This would happen when there are two bits set in one position, it and the algorithm could terminate when both the carry and the sign-bit are 0:

       Sign bit
       v
Carry: 100010010000
Sign : 011101110000

would be treated: The sign bit is set. 6 bits below have a positive XOR. The fifth bits (from left) are both set. The sign will change. (can it change once again if the least significant bits are different? yes, as long as the XOR chain gives 1).

       Sign bit
       v
Carry: 000001111111
Sign : 011101111111

Here the sign bit are not set. The three following bits gives XOR=1, continue. The eight bit from left are both zero. The sign bit cannot be changed.

A very sketchy logic-gate implementation would therefore be:

THESIGN = false

loop through the numbers SIGNBIT, CARRYBIT from highest (sign) bits downwards:
    when  XOR(SIGNBIT, CARRYBIT) = 1, continue
    when  AND(SIGNBIT, CARRYBIT) = 1, flip THESIGN bit, continue
    when NAND(SIGNBIT, CARRYBIT) = 1, stop the evaluation, return THESIGN.