Ones' complement addition

Eric Smith wrote:
> Phil Hays wrote about a one's complement adder, which uses
> end-around carry:
>> It looks to me like there is a chance of a pulse running around the carry
>> loop for a multiple times, perhaps even forever.
> 
> There is no way that can happen if the inputs are stable.  For an n-bit
> one's complement adder, there can't be a carry propogation wider than n
> bits.
> 
> In other words, in a 16-bit adder, a carry propogation might start in
> position 5, but even if it wraps it cannot cause carry propogation
> past position 4.
> 
> You can prove this by exhaustion for a short word width, and then by
> induction for longer word widths.
> 

Eric,

I was wondering if you can provide a reference to a good book or article 
that deals with the proof you are mentioning here?

Regards,
Koen

Eric Smith wrote:

> A one's complement adder does not have a "carry-in" input,

Please excuse my poor choice of words. Replaced "carry-in" with
"carry-wrapped around input to LSB", which is the same as the "carry-out"
or the "carry-wrapped around output from the MSB" after the propagation
delay from the MSB's output to the input of the LSB. So let me try again:

An example. Note that the two inputs can be anything that are inverses of
each other. The first two cases are stable.

  0111
 +1000
    +0 Carry wrapped around input to LSB
======
  1111 carry wrapped around output from MSB = 0

Note that the carry bits are 0000

or:

  0111
 +1000
    +1 Carry wrapped around input to LSB
======
  0000 carry wrapped around output from MSB = 1

Note that the carry bits are 1111

The key point here is that there are two correct answers in ones
complement to the problem:

7 - 7 = ?

And these answers are positive zero and negative zero.

With me so far?

To describe an unstable case, I'm going to show only the carry bits. The
inputs are the same as above. I'm assuming ripple carry, and that one time
step is required for propagation of carry for one bit position.

Time
0     Carry  0011
1     Carry  0110
2     Carry  1100
3     Carry  1001
4     Carry  0011
5     Carry  0110
6     Carry  1100
7     Carry  1001
8     Carry  0011
...

The sum would also not be stable.

There are multiple ways to avoid the unstable cases. A few that come to
mind with little effort:

1) Force the previous carry wrap around input into the LSB until the carry
wrap around output from the MSB is stable. This has the side effect of
making the result (positive or negative zero) depend on the previous
computation. (I think that the CDC6600 used this method)

2) If the carry look ahead shows all propagate bits are '1', then generate
a carry wrap around input into the LSB = '1' regardless of the carry wrap
around output from the MSB or any generate bits. This has the side effect
of producing only positive zeros for any add unless both operands were
negative zeros.

3) Force a carry wrap around input of '0' until the carry wrap around
output is stable. This has the side effect of never producing a positive
zero output for any add unless both operands were positive zeros. (Hand
computed examples often use this method)

4) Force a carry wrap around input of '1' until the carry wrap around
output is stable. This has the side effect of producing only positive
zeros any add unless both operands were negative zeros.

Any method that must decide between two correct answers may take forever
to come to one of the two answers.


-- 
Phil Hays (Xilinx, but posting for myself)

Phil Hays wrote:
> Please excuse my poor choice of words. Replaced "carry-in" with
> "carry-wrapped around input to LSB", which is the same as the "carry-out"
> or the "carry-wrapped around output from the MSB" after the propagation
> delay from the MSB's output to the input of the LSB. So let me try again:

My apologies for misunderstanding your point.

> There are multiple ways to avoid the unstable cases. A few that come to
> mind with little effort:

After further consideration, I believe you are correct that the cases
where the result is numerically zero can be unstable, unless a method
to precondition at least one stage of the carry chain is used (as done
in your suggestions).

> 1) Force the previous carry wrap around input into the LSB until the carry
> wrap around output from the MSB is stable. This has the side effect of
> making the result (positive or negative zero) depend on the previous
> computation. (I think that the CDC6600 used this method)

When I find a bit of spare time, I'll look into what method was used
by the PDP-1.  As a guess, I suspect the design probably is such that
the initial state of the carry signals is zero, in which case the
result is stable even for operands that add to zero.

Eric

Phil Hays wrote:

> 
> There are multiple ways to avoid the unstable cases. A few that come to
> mind with little effort:
> 
> 1) Force the previous carry wrap around input into the LSB until the carry
> wrap around output from the MSB is stable. This has the side effect of
> making the result (positive or negative zero) depend on the previous
> computation. (I think that the CDC6600 used this method)
> 
> 2) If the carry look ahead shows all propagate bits are '1', then generate
> a carry wrap around input into the LSB = '1' regardless of the carry wrap
> around output from the MSB or any generate bits. This has the side effect
> of producing only positive zeros for any add unless both operands were
> negative zeros.
> 
> 3) Force a carry wrap around input of '0' until the carry wrap around
> output is stable. This has the side effect of never producing a positive
> zero output for any add unless both operands were positive zeros. (Hand
> computed examples often use this method)
> 
> 4) Force a carry wrap around input of '1' until the carry wrap around
> output is stable. This has the side effect of producing only positive
> zeros any add unless both operands were negative zeros.
> 
> Any method that must decide between two correct answers may take forever
> to come to one of the two answers.
> 
> 

This post started with the question how ones' complement is best done on 
FPGAs (Xilinx)

 From the discussion we learned that interconnecting the carry-out and 
carry-in is a bad idea, as this can become unstable when A and ~A are 
added. (Thanks for clarifying this!)

With your suggestions in mind I've tried to come up with a couple of 
alternatives to build a 16 bit ones' complement adder, requiring a 
single clock cycle adding the operands A and B :

1. Make a chain of two 16 bit two's complement adders both calculating 
A+B. Use the carry-out of one of the adders as carry-in for the other 
adder. This is like building a 32bit adder calculating A&B + B&A.
The 16 most significant bits are used as the result.

2. Use a single 16 bit two's complement adder with end-around carry. If 
we put a flip flop triggered on the falling edge in the carry loopback 
path we can avoid the instability problems.
On the rising edge this flip flop should be set to zero, on the falling 
edge it clocks in the carry-out.

3. Instantiate two adders. One calculates A+B+0 and the other A+B+1.
Then add a 2:1 multiplexer and use the carry-out of A+B+0 to select the 
right sum. If the carry-out is zero, multiplex A+B+0 onto the output, 
otherwise multiplex the result of A+B+1 to the output

I guess 1 & 2 will reach similar speeds, but 2 uses less hardware.
Option 3 seems interesting as it could be faster then the other 
alternatives.

I would be happy to hear your ideas about this!


Koen.