Building an adder with overflow detection

22 July 2020

It’s been a while since I worked through the first part of The Elements of Computing Systems and, in preparation for the Computer Architecture course at Bradfield CS I was watching this UC Berkely lecture that touches on Two’s Complement addition. The point came up that you can detect an overflow or underflow by comparing the carry-in and carry-out values for the most significant bit. That seemed like it would be easy to implement in an 8-bit adder built from an array of 1-bit adders. So I decided to diagram an 8-bit adder with overlfow/underflow detection. In the spirit of strengthening some neural pathways I refused to look at my notes from my previous reading of ECS.

Half Adder

First, how to add two bits. This was pretty simple. First wrote out a truth table for the Out and Out(carry) bits:

The truth table patterns for the Out and Out(carry) bits look an awful lot like XOR and AND gates, respectively. So for a half adder that takes two inputs and provides an output with carry:

INPUT
    In(1)
    In(2)

OUTPUT 
    Out        = In(1) XOR In(2)
    Out(carry) = In(1) AND In(2)

This works for adding a single bit, but once we get to bit 2 we’ll need to use the previous carry bit as input.

Full Adder

As before, I mapped out the end state:

I noticed a pattern early on. I could generalize the rule for Out and Out(carry) based on the number on input bits equal to 1:

The Out Bit

I started with the Out bit. The generalization above made me think that there may not be any distinction between any of the input bits. I would need to perform some operations that would allow for variance in the order of the bits so that {0 0 1}, {0 1 0}, and {1 0 0} would evaluate to the same value. Given that AND gates prefer all 1s and OR gates prefer 1s in general, I had a haunch that XOR might help out with the order issue:

# Zero 1s ===========
{0 0 0}
0 XOR 0 = 0
          0 XOR 0 = 0

# One 1 =============
{0 0 1}
0 XOR 0 = 0
          0 XOR 1 = 1
{0 1 0}
0 XOR 1 = 1
          1 XOR 0 = 1
{1 0 0}
1 XOR 0 = 1
          1 XOR 0 = 1

# Two 1s ============
{0 1 1}
0 XOR 1 = 1
          1 XOR 1 = 0
{1 0 1}
1 XOR 0 = 1
          1 XOR 1 = 0
{1 1 0}
1 XOR 1 = 0
          0 XOR 0 = 0

# Three 1s ==========
{1 1 1}
1 XOR 1 = 0
          0 XOR 1 = 1

That did it! So far for a full adder:

INPUT 
    In(1)
    In(2)
    In(carry)

INTERMEDIATES
    Inter(a) = In(1) XOR In(2)

OUTPUT
    Out        = Inter(a) XOR In(carry)
    Out(carry) = ?

The Out(carry) bit

Now for the Out(carry) bit. This one took me for a ride. The fact that the presence of two or three 1s should evalute at 1 made me try a combination of ANDs and ORs to no avail.

I noticed that the Out(carry) column could be organized by switching the fourth row {0 1 1} for the fifth {1 0 0}:

This didn’t bring out any patterns.

I tried to approach it as two problems like decimal addition. You don’t add three numbers at once. Instead you add two numbers and then consider the sum and the third number. I added columns for

• Inter(a) defined as In(1) XOR In(2) above, and
• Out defined as Inter(a) XOR In(carry) above:

Rows 3-6 where either In(1) or In(2) is 1 looked interesting. I could see a pattern for those inputs:

If either In(1) or In(2) are 1, Inter(a) AND In(carry) produces the correct Out(carry) value…

The only other scenarios that need to produce Out(carry) = 1 are the final two rows. For those rows and only those rows In(1) AND In(2) is true.

Let’s define two more intermediates:

• Inter(b) = Inter(a) AND In(carry) (as seen on the previous table), and
• Inter(c) = In(1) AND In(2)

Now, all we have to do is transform Inter(b) OR Inter(c) to arrive at Out(carry)!

So the full adder is as follows:

INPUT 
    In(1)
    In(2)
    In(carry)

INTERMEDIATES
    Inter(a) = In(1) XOR In(2)
    Inter(b) = Inter(a) AND In(carry)
    Inter(c) = In(1) AND In(2)

OUTPUT
    Out        = Inter(a) XOR In(carry)
    Out(carry) = Inter(b) OR Inter(c)

8 Bits and Overflow detection

Two hours later…the whole point of this was to add over/underflow detection to a multi-bit adder according to the rule you can detect an overflow or underflow by comparing the carry-in and carry-out values for the most significant bit. The most significant bit will be the final adder and we can snatch it’s carry input and carry output. To detect if those values are the same, we can XOR then NOT them. Having defined a full adder, this was pretty simple:

define fullAdder(a, b, carryIn) : {out, carryOut}

INPUT
    In(1)   In(9)
    In(2)   In(10)
    In(3)   In(11)
    In(4)   In(12)
    In(5)   In(13)
    In(6)   In(14)
    In(7)   In(15)
    In(8)   In(16)

INTERMEDIATES
    Inter(outOne),   Inter(carryOne)   = fullAdder(In(1), In(9),  null)
    Inter(outTwo),   Inter(carryTwo)   = fullAdder(In(2), In(10), Inter(carryOne))
    Inter(outThree), Inter(carryThree) = fullAdder(In(3), In(11), Inter(carryTwo))
    Inter(outFour),  Inter(carryFour)  = fullAdder(In(4), In(12), Inter(carryThree))
    Inter(outFive),  Inter(carryFive)  = fullAdder(In(5), In(13), Inter(carryFour))
    Inter(outSix),   Inter(carrySix)   = fullAdder(In(6), In(14), Inter(carryFive))
    Inter(outSeven), Inter(carrySeven) = fullAdder(In(7), In(15), Inter(carrySix))
    Inter(outEight), Inter(carryEight) = fullAdder(In(8), In(16), Inter(carrySeven))
    
OUTPUT
    Out(1) = Inter(outOne)
    Out(2) = Inter(outTwo)
    Out(3) = Inter(outThree)
    Out(4) = Inter(outFour)
    Out(5) = Inter(outFive)
    Out(6) = Inter(outSix)
    Out(7) = Inter(outSeven)
    Out(8) = Inter(outEight)
    Out(overflowDetection) = NOT(Inter(carrySeven) XOR Inter(carryEight))
    Out(overflowFlag) = Inter(carrySeven)

This adder will take two 8-bit numbers as input and will output an 8-bit number, as well as an over/underflow detection bit and a flag to indicate if (0) an underflow was detected or (1) an overflow was detected.

Written by Dan Drust on 22 July 2020

Continue Reading: Where is Eloquent’s static creat…

Browse more posts