Mathematics

The mathematics are as simple as addition of 10-based digits

• Add two binary number of the same bit and the carry (from the last bit)
• If sum exeeds 1, sum turns 0, add 1 to the next carry

Overflow

Overflow occurs when the result of addition exceeds the maximum length of binary digits ($2^N$), resulting the result to be the modulo of $2^N$ (decreases $2^N$)

Digital Adder

• Half Adder - adds two bits
• Full Adder - adds three bits
• Adder - Adds two numbers

Half Adder

If the carry is 0, then

a	b	Sum	Carry
0	0	0	0
1	0	1	0
0	1	1	0
1	1	0	1

• $Sum=a\text{ XOR }b$
• $Carry=a\text{ AND }b$

**Diagram**

Full Adder

Why a half adder is called HALF? There're two of them in a FULL Adder.

Take the carry into consideration

a	b	c (last carry)	Sum	Carry
0	0	0	0	0
0	0	1	1	0
1	0	0	1	0
1	0	1	0	1
0	1	0	1	0
0	1	1	0	1
1	1	0	0	1
1	1	1	1	1

• There're two ways to get $Sum=1$
  1. $HalfAdd(a,b{)}_{sum}=0$ And $c=1$
  2. $HalfAdd(a,b{)}_{sum}=1$ And $c=0$
  • Otherwise Sum = 0
  • $$Sum=HalfAdd(HalfAdd(a,b{)}_{sum},c{)}_{sum}$$
• There're two ways to get $Carry=1$
  1. $HalfAdd(a,b{)}_{sum}=1$ And $c=1$
  2. $HalfAdd(a,b{)}_{carry}=1$
     • ($c$ doesn't matter because $HalfAdd(a,b{)}_{sum}\equiv 0$, so $c$ only affect $Sum$)
  • $$Carry=HalfAdd(HalfAdd(a,b{)}_{sum},c){)}_{carry}\vee HalfAdd(a,b{)}_{carry}$$

**Diagram**

Multi-bit Adder

• The first c is always 0
• The last carry is thrown (ignore the overflow)

For N-bit adder

• 1 Half adder
• N-1 Full adder