2
\$\begingroup\$

How do you detect overflow when you have a CSA?

I have 3 16-bit two's complement inputs and a 16-bit output and I'm wondering how do I detect overflow?

\$\endgroup\$
  • \$\begingroup\$ What's a CSA??? \$\endgroup\$ – Leon Heller Aug 2 '13 at 16:59
  • \$\begingroup\$ Carry-save Adder \$\endgroup\$ – Veridian Aug 2 '13 at 16:59
  • \$\begingroup\$ Why do you need to use a carry-save adder in a context where overflow would matter? If your goal is to determine overflow when summing together three values, compute the sum of everything below the sign bit along with the number of carries out (zero, one, or two). Then add together the sign bits and those carries to compute the number of carries out of the final result (again zero, one, or two). If the number of carries in the two calculations don't match, there was an overflow. This approach is extensible to larger numbers of inputs as well. \$\endgroup\$ – supercat Aug 13 '13 at 20:49
2
\$\begingroup\$

In a carry-save adder there are three inputs and two outputs. Many different output-pairs represent the same number. Carry-save adders have no carry-propagation overhead, so they are good for adding together many operands at low latency, but the cost for that speed is that you don't really know anything about the result (even whether it is positive or negative) until you add the final two outputs together using a "normal" adder (e.g. ripple-carry, carry-select, carry-skip, or carry-lookahead.)

I know of no way to determine overflow just by looking at most significant bits (like you can in an adder that carries.) For example, here's an example that overflows in 3-bit 2's complement (3+3-2 = 4).

  0 1 1     (3)
  0 1 1     (3)
  1 1 0     (-2)
  -----
  1 1 0     (-2)
0 1 1       (6)

And another with all the same most significant bits that doesn't overflow:

  0 1 1     (3)
  0 1 1     (3)
  1 0 1     (-3)
  -----
  1 0 1     (-3)
0 1 1 0     (6)
\$\endgroup\$
  • \$\begingroup\$ @starbox: Huh? Since the largest possible value representable in 3-bit 2's complement is +3, and since 3+3-2 is more than that, 3+3-2 will overflow in 3-bit 2's complement. \$\endgroup\$ – davidcary Aug 4 '13 at 7:29
1
\$\begingroup\$

I had to dig back into my 68HC11 manual to figure out where I was going wrong in my answer. So! The answer is to look at the sign bits of both the inputs and the results.

  • If you add two positive numbers and the result is negative, you've had an overflow.
  • If you add two negative numbers and the result is positive, you've had an overflow
  • The addition of a negative and a positive number can't overflow
\$\endgroup\$
  • \$\begingroup\$ Yes, i could make the adder output wider, but how would i go about performing this operation anyway? \$\endgroup\$ – Veridian Aug 2 '13 at 17:30
  • \$\begingroup\$ I expanded my answer to try to better answer your question and comment \$\endgroup\$ – Brooks Aug 2 '13 at 17:41
  • \$\begingroup\$ I believe your answer is only true for unsigned operands. I'm performing operations with two's complement operands (signed) \$\endgroup\$ – Veridian Aug 2 '13 at 18:04
  • \$\begingroup\$ This is correct for most adders but not RCA. \$\endgroup\$ – travisbartley Aug 6 '13 at 1:38
0
\$\begingroup\$

You can detect overflow after the CSA using the two most significant carry-bits, denote \$C_o\$ (the bit that is discarded), and \$C\$, and the most significant sign-bit, \$S\$. The addition will overflow if \$C_o = S = 0\$ and \$C=1\$, i.e., all positive numbers in, but the sum can not be represented in the corrsponding two's complement represenation (although you way actually end up with a positive number at the end caused by double overflows) or \$C_0 = S = 1\$ and \$S=0\$, i.e., all negative inputs but too high magnitude (but it may still result in a negative number because of double overflows).

The overflow in the final addition (carry-save to non-redundant form) is detected as usual (comparing the two final carry bits, if they are different there is an overflow, as we will see, checking signs is not feasible).

Example 1:

  011
  011
 +011
-----
 011  carry
  011 sum

Overflow as \$C_o = 0, S = 0, C = 1\$

  110
 +011
 ----
  001

Here, another overflow happens at the end (although this is not detected since from a two's complement perspective \$-2 + 3\$ does not overflow) so a positive number is obtained despite the overflow.

Example 2:

  010
  010
 +110
-----
 010  carry
  110 sum

No overflow as \$C_o = 0, S = 1, C = 1\$

  100
 +110
 ----
  010

Correct answer! However, it appears as an overflow has happened looking at the two's complement addition. This can be solved by replacing the sign-bits as \$S' = C_o\$ and \$C'= C \oplus S \oplus C_o\$ (this will also make the carry-save represenation shiftable) leading to

  000
 +010
 ----
  010

and no overflow detected (which is correct).

Example 3:

  011
  011
 +111
-----
 011  carry
  111 sum

No overflow as \$C_o = 0, S = 1, C = 1\$

  110
 +111
 ----
  101

No overflow detected here neither, although there is one. Replace the sign-bits as discussed above:

  010
 +011
 ----
  101

Now, since the incoming carry to the final stage (1) is different from the outgoing (0) there is an overflow detected, which is of course correct since \$3+3-1\$ is out of the \$[-4,3]\$ range possible

All this is suggested and discussed in "Carry-save architectures for high-speed digital signal processing" by Tobias Noll.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.