Binary Adders
Asst. Prof. Mohanad Alayedi
Department of Software Engineering
Haliç University
mohanadysalayedi@halic.edu.tr
CEN203, Fall 2024
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 1
Overview
➢ Addition and subtraction of binary data is fundamental
• Need to determine hardware implementation
➢ Represent inputs and outputs
• Inputs: single bit values, carry in
• Outputs: Sum, Carry
➢ Hardware features
• Create a single-bit adder and chain together
➢ Same hardware can be used for addition and
➢ subtraction with minor changes
➢ Dealing with overflow
• What happens if numbers are too big?
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 2
Half Adder
➢ A0 , B0 -> single bit inputs
➢ S0 -> single bit sum
➢ C1 -> carry out
Dec Binary
1 1
+1 +1
2 10
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 3
Multiple-bit Addition
➢ Consider single-bit adder for each bit position.
A3 A2 A1 A0 B3 B2 B1 B0
A 0 1 0 1 B 0 1 1 1
1 1 1 Ci+1 Ci
A 0 1 0 1 Ai
B 0 1 1 1 +Bi
1 1 0 0 Si
Each bit position creates a sum and carry
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 4
Full Adder
➢ Full adder includes carry in Ci
➢ Notice interesting pattern in Karnaugh map.
Ci Ai Bi Si Ci+1 AiBi
Ci 00 01 11 10
0 0 0 0 0
0 0 1 1 0 0 1 1
0 1 0 1 0
0 1 1 0 1 1 1 1
1 0 0 1 0
1 0 1 0 1 Si
1 1 0 0 1
1 1 1 1 1
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 5
Full Adder
➢ Full adder includes carry in Ci
➢ Alternative to XOR implementation
Ci Ai Bi Si Ci+1 Si = Ci'·Ai'·Bi + Ci'·Ai·Bi'
0 0 0 0 0
+ Ci ·Ai'·Bi'+ Ci ·Ai·Bi
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 6
Full Adder
➢ Reduce and/or representations into XORs
Si = Ci'· Ai'· Bi
+ Ci'· Ai · Bi'
+ Ci · Ai'· Bi'
+ Ci · Ai · Bi
Si = Ci'· (Ai'· Bi + Ai · Bi')
+ Ci · (Ai'· Bi'+ Ai · Bi)
Si = Ci'· (Ai Bi) + Ci · (Ai Bi)'
Si = Ci (Ai Bi)
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 7
Full Adder
➢ Now consider implementation of carry out
➢ Two outputs per full adder bit (Ci+1, Si)
Ci Ai Bi Si Ci+1 AiBi
0 0 0 0 0 Ci 00 01 11 10
0 0 1 1 0 0 1
0 1 0 1 0
0 1 1 0 1 1 1 1 1
1 0 0 1 0
1 0 1 0 1 Ci+1
1 1 0 0 1
1 1 1 1 1
Note: 3 inputs
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 8
Full Adder
➢ Now consider implementation of carry out
➢ Minimize circuit for carry out - Ci+1
Ci Ai Bi Si Ci+1 Ci 00 01 11 10
0 0 0 0 0 0 1
0 0 1 1 0
0 1 0 1 0 1 1 1 1
0 1 1 0 1
1 0 0 1 0 Ci+1
1 0 1 0 1
1 1 0 0 1 Ci+1 = Ai·Bi + Ci·Bi + Ci·Ai
1 1 1 1 1
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 9
Full Adder
Ci+1 = Ai·Bi + Ci Ai'·Bi + Ci·Ai·Bi'
Ci+1 = Ai·Bi + Ci·(Ai'·Bi + Ai·Bi')
Ci+1 = Ai·Bi + Ci·(Ai Bi)
Recall:
Si = Ci (Ai Bi)
Ci+1 = Ai·Bi + Ci·(Ai Bi)
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 10
Full Adder
➢ Full adder made of several half adders
Si = Ci (Ai Bi)
Ci+1 = Ai·Bi + Ci·(Ai Bi)
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 11
Full Adder
➢ Hardware repetition simplifies hardware design
A full adder can be made from two
half adders (plus an OR gate).
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 12
Full Adder
➢ Putting it all together
➢ Single-bit full adder
➢ Common piece of computer hardware
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 13
4-Bit Adder
➢ Chain single-bit adders together
➢ What does this do to delay?
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 14
Negative Numbers – 2’s Complement.
➢ Subtracting a number is the same as:
1. Perform 2’s complement
2. Perform addition
➢ If we can augment adder with 2’s complement hardware?
110 = 0116 = 00000001
-110 = FF16 = 11111111
12810 = 8016 = 10000000
-12810 = 8016 = 10000000
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 15
4-bit Subtractor: E = 1
Add A to B’ (one’s complement) plus 1 That is, add A to two’s complement of
BD=A-B
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 16
Adder- Subtractor Circuit
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 17
Overflow in two’s complement addition
➢ Definition: When two values of the same signs are added:
➢ Result won’t fit in the number of bits provided
➢ Result has the opposite sign.
Assumes an N-bit adder, with bit N-1 the MSB
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 18
Addition cases and overflow
00 01 11 10 00 11
0010 0011 1110 1101 0010 1110
0011 0110 1101 1010 1100 0100
0101 1001 1011 0111 1110 0010
2 3 -2 -3 2 -2
3 6 -3 -6 -4 4
5 -7 -5 7 -2 2
OFL OFL
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 19
Summary
➢ Addition and subtraction are fundamental to computer systems
➢ Key – create a single bit adder/subtractor
➢ Chain the single-bit hardware together to create bigger designs
➢ The approach is call ripple-carry addition
➢ Can be slow for large designs
➢ Overflow is an important issue for computers
➢ Processors often have hardware to detect overflow
➢ Next time: encoders/decoder.
CEN203, Fall 2024 2024, Dr. Mohanad Alayedi (Haliç University) 20
