Right shifting a carry save number

Question

Carry save arithmetic uses twice the number of bits, one word to hold the "virtual sum", one to hold the "virtual carry" to avoid propagating the carry which is the limiting factor in hardware speed.

I have a system that requires dividing these numbers by powers of two, but simply right shifting both numbers does not work in all cases eg. two 16 bit carry save numbers, which you add to produce 4000, C001 is the Virtual Sum, 7FFF is the virtual carry.

C001 + 7FFF = 4000  (discard overflow bits)
but after right shift
6000 + 3FFF = 9FFF   (when it should be 2000)

In short: How do you divide a carry save number by a power of two? (While keeping it a carry save number)

Answer 1

First, right shift by 1 effectively does deleting by 2 with forgetting a remainder. But the remainder could be needed for having the exact result. For instance, change your initial example with adding C000 to 8000, or C002 to 7FFE. Both give the same sum but, sum of shifted values is A000 instead of your 9FFF, and this is definitely more correct. So, you can do such shifting only if sum of LSBs could be lost. In your case with 2 summands and 1 bit shift, this means no more than 1 summand could have 1 in its LSB.

Second, consider this is fixed and you've got A000. A simple ideal math says (a+b)/2 == a/2 + b/2. For your case, the carry bit you initially ignored weighed 0x10000, but after shifting by 1, it weighs 0x8000. That is exactly how A000 differs from your expected 2000. So, if you are sure in other aspects of your method, finish it with logical AND with ~0x8000 == 0x7FFF.

Answer 2

There is a technique to correct the representation such that it is shiftable. This originates from a paper "Carry-save architectures for high-speed digital signal processing" by Tobias Noll. You can compute new sign-bits of the carry and sum vectors as

c' = c_out

s' = s xor c xor c_out

where s and c are the original sign-bits and c_out is the discarded carry-bit from the carry-save addition.