Two's Complement Overflow in a Saturating Accumulator
A 12-bit signed accumulator sums 8-bit signed samples. The designer claims that because each sample fits in 8 bits and the accumulator is 12 bits wide, overflow is impossible for any run of fewer than 16 samples. A test run sums the following signed samples in order: +120, +120, +120, +120, +127, -128, -1, +100. The accumulator wraps (no saturation) and the hardware sets an overflow flag on each two's-complement overflow event. A second engineer argues the flag should have fired only on the final addition, since the individual sums stay modest.
1. Determine the running accumulator value after each addition and identify exactly which additions set the overflow flag. State the rule you applied.
Read the worked answer
Rule: for signed addition, overflow occurs when both operands share a sign and the result's sign differs (equivalently, carry into the sign bit differs from carry out).
Running 12-bit signed values (range -2048..+2047):
- 0 + 120 = 120 (no overflow)
- 120 + 120 = 240 (no)
- 240 + 120 = 360 (no)
- 360 + 120 = 480 (no)
- 480 + 127 = 607 (no)
- 607 + (-128) = 479 (no)
- 479 + (-1) = 478 (no)
- 478 + 100 = 578 (no)
No overflow ever fires. The 12-bit accumulator has ample headroom: the worst-case magnitude of eight 8-bit samples is 8128 = 1024, well inside 2047. So the second engineer's intuition about where a flag would fire is moot here - the flag never fires, and the first engineer's 'fewer than 16 samples' bound is actually conservative but directionally correct (16128 = 2048, which just exceeds the positive range, so 16 is the first count where overflow becomes possible at all).
2. The designer now wants to widen the sample stream to 16-bit signed samples but keep the 12-bit accumulator. Give the minimum number of samples after which overflow is guaranteed possible, and explain why the 'each sample fits' argument breaks down.
Read the worked answer
With 16-bit samples the per-sample magnitude can reach 32768, which already exceeds the 12-bit accumulator range (-2048..+2047). So a single sample can overflow: adding +32767 to a zero accumulator wraps.
The 'each sample fits' argument only bounds a single operand, not the partial sum. Signed overflow is a property of the result relative to the destination width, not of the inputs. Minimum samples for guaranteed possible overflow = 1. More generally, with n-bit samples and an m-bit accumulator, overflow becomes possible as soon as 2^(n-1) > 2^(m-1) - 1, i.e. n >= m. Here n=16 > m=12, so overflow is possible immediately.
3. Recommend a fix that preserves the 12-bit datapath but prevents silent wrap, and state the tradeoff versus simply widening the accumulator.
Read the worked answer
Options:
- Saturating add: clamp to +2047/-2048 on overflow and raise a sticky saturation flag. Keeps 12-bit datapath, costs a comparator plus mux, and the flag tells software the result is clipped.
- Guard/sticky bits: keep 1-2 extra high bits internally and only round/truncate at output; cheap but still needs a final clamp.
- Widen accumulator to 16+ bits: eliminates overflow for this sample width, costs area and changes downstream interfaces.
Recommendation: saturating add with a sticky flag, because the 12-bit datapath and interfaces stay unchanged while the system gets an explicit, testable error signal instead of silent wrap. Tradeoff: saturation introduces nonlinearity (clipping) that must be documented, whereas widening is linear but invasive. The wrap behavior must never be left silent, since a wrapped value is indistinguishable from a legitimate small sum.