Online arithmetic with radix 2 addition

Question

I am having trouble working with OLA(online arithmetic addition) radix 2 SD(signed digit) addition MSDF(most significant digit first).

If I have an 8 bits range unsigned number and a redundant and symmetric set of \$\left\{ {-1, 0, +1}\right\}\$ with the following table:

+1 ---> 01
 0 ---> 00
 0 ---> 11
-1 ---> 10

If I want to make \$a-b=c\$, I do not understand how the operation of \$a-b\$ is performed in binary.

If we have \$25-10=15\$,

$$25_{10}=0001 1001_2$$ $$10_{10}=0000 1010_2$$

If we map each two consecutive digits to the those in the table, how do I perform the computation so that I could implement it in hardware?

Answer 1

In carry-save/borrow save arithmetics, each binary position is represented as two bits. Numbers can have several possible representations.

+25 = P=11001 / N=00000
-10 = P=00000 / N=01010

The result is simply : +25-10 : P= 11001 / N=01010

P=1, N=1 combinations can be simplified to P=0, N=0.

So : +25-10 : P= 10001 / N=00010

You can convert to a traditional two's complement representation by doing the actual subtraction : 10001 - 00010 = 1111 = 15

For a simple substraction, it does not make any sense. The whole purpose of this mess is that you can do iterative additions or subtraction and you only have to perform one level of binary operations on each step ( a few XORs or muxes per bit), without propagating the carry.

For example, divisions (particularly SRT divisions) can be done with many successive additions or subtractions. Using carry-save/borrow-save representations allows to reduce the cycle time, or to calculate more bits per cycle and, as there is no carry propagation, it does not depends on the operand size (for example the same cycle frequency is adapted for both single and double precision floating point).

Edit

Look for "borrow-save adder" for actual implementations . For example : http://users-tima.imag.fr/cis/guyot/Cours/Oparithm/english/Additi.htm

Edit

FA blocks are "full adders"

Take 3 inputs, A,B and C, each weighting 0 or 1. The result is between 00 and 11. A full adder is :

Carry = (A and B) or (B and C) or (A and C)
Sum = A xor B xor C

The bubbles around the adders are obviously inverters, 'NOT' gates

The 'Online' version on the right diagram processes bits serially instead of in parallel. I have the impression that the least significant bit should be provided first. Squares are memory/flipflops, the propagation time is therefore 3 clocks.

The adder

This diagram describes an adder taking two BS vectors (X+/X-) and (Y+/Y-) and generating one BS result (Z+/Z-). It can also be used to calculate the sum of two differences.

The problem I see is that you need the absolute value to calculate the 'sum of absolute differences'. I don't know how to convert to the absolute without doing a (carry propagating) comparison.

Answer 2

For your example, first convert 10 to -10 by flipping bits/adding 1:

Then perform the addition of [25 + (-10)] using 8-bit two's complement.