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?
Electronic – Overflow detection in a CSA (Carry-save Adder)
digital-logicintegrated-circuitmathverilog
Related Solutions
The standard adder / subtract circuit is given by the figure below.For an explanation of how it works please see my previous answer here : Subtraction using adder circuit
Now notice that if you were to change the input that is tied to '0' to Cin, then the circuit would now perform the operation: A + ~B + (Cin ^ SUB), meaning that:
1) it would be a normal Adder/Subtract circuit when Cin is 0.
2) if Cin = 1 and Sub = 1 it would evaluate to:
A + ~B + (1 ^ 1) = A + ~B = A + ~B + 1 - 1 = A + (~B + 1) - 1 = A - B - 1 ,
This means that the normal Add/Sub circuit can achieve the operation you require, all you need to do is change the input tied to '0' your Cin.
You could also design the desired circuit by using the usual method of writing all your possible inputs into a truth table, then deriving the Boolean equations for them, then simplifying them to get your final circuit equation.
When can an overflow happen?
- Adding a positive and a negative number yields a number in between them (lower border inclusive), thus no overflow is possible.
- Adding two positive numbers will always result in a positive number.
- Adding two negative numbers will always result in a negative number.
-> An overflow is only possible when both summands share the same sign.
Can an overflow wrap around more than once?
In a n-bit 2's complement number,
- the maximum number is \$2^{n-1}-1\$. Adding two of them yields: $$2\cdot(2^{n-1}-1)=2^n-2=-2$$
- the minimum number is \$-2^{n-1}\$. Again adding two of them: $$2\cdot(-2^{n-1})=-2^n=0$$
-> In case of an overflow the result will be always negative for positive summands and positive for negative summands.
Conclusion
An overflow has happened if, and only if, both summands have the same sign and the result has the other sign.
Related Topic
- Electrical – Two’s complement overflow at a 4-bit adder circuit
- Electrical – Problem in overflow detection in signed 2’s complement 3-bit numbers
- Electrical – Quick question about signed full adders (carry and overflow)
- Electrical – sublw carry bit: Microchip PIC16C instruction set “two’s complement method”
- Electronic – When adding binary numbers, how do you just ignore the overflow
- Electrical – Signed Overflow Detection
- Electronic – 2’s complement subtraction with overflow
Best Answer
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).
And another with all the same most significant bits that doesn't overflow: