Transcript ee1210 - Daniels

Adding Binary Numbers
• Binary addition is similar to
decimal addition
• 0+0 = 0
• 0+1 = 1
• 1+0 = 1
• 1+1 = 10
0010
+1100
=1110
1
• If we have a result greater
than 1, we must carry a ‘1’
to the next digit
• Produce carry (to left) ->
Carry-out
• Get a carry (from right) -->
Carry-In
Seattle Pacific University
0010
+1010
=1100
Carry-Out of bit 1,
carry-In to bit 2
1 1 1
Carries
0110
+ 1110
=10100
EE 1210 - Logic System Design
Numbers-1
Half Adder
A half adder adds two bits, A and B
and produces a Sum and CarryOut
X
0
0
1
1
X
Y
+
Sum
Y Sum CarryOut
0
0
0
1
1
0
0
1
0
1
0
1
CarryOut
Sum = XY  XY
= X Y
X
Sum
Y
CarryOut
CarryOut = XY
Problem: We often need to add two bits and a CarryIn...
Seattle Pacific University
EE 1210 - Logic System Design
Numbers-2
Full Adder
CarryIn
A
+
B
A
0
0
0
0
1
1
1
1
A full adder adds two
bits, A and B, and a
CarryIn and produces
a Sum and CarryOut
Sum
CarryOut
Cin
Cout
Cin 0
AB
Cin
Sum
Cin 0
AB
1
1
00
0
0
00
0
1
01
0
1
01
1
0
B
A
11
1
1
10
0
1
Cout = AB BCin ACin
Seattle Pacific University
B
0
0
1
1
0
0
1
1
Cin
0
1
0
1
0
1
0
1
Cout
0
0
0
1
0
1
1
1
B
A
11
0
1
10
1
0
Sum = A B  Cin
EE 1210 - Logic System Design
Numbers-3
Sum
0
1
1
0
1
0
0
1
4-bit Ripple Carry Adder
CarryIn=0
A0
B0
CIn
+
C
Sum0
Out
A1
B1
CIn
+
C
Sum1
+
A3A2A1A0
B3B2B1B0
S3S2S1S0
Note bit numbering: 3,2,1,0
Out
A2
B2
CIn
+
C
Sum2
Connect Cin’s to Cout’s
Set global Cin to 0
Global Cout is an output
Out
A3
B3
CIn
+
C
Sum3
Out
CarryOut
Seattle Pacific University
EE 1210 - Logic System Design
Numbers-4
Ripple Carry Timing
0 CarryIn=0 Inputs stable at 0ns
A0 0
CIn
B0 0
+
C
8
Sum0
Out
10
A1 0
CIn
B1 0
+
C
18
Sum1
A
Cin
5
B
Cin
5
A
B
5
Full Adder
Circuit
Cout
5
Out
A
20
A2 0
+
C
B2 0
Out
CIn
B3 0
+
C
Sum
Sum3 stable at 38ns
Assume 5ns delay for
AND/ORs and 8ns for XORs
38
Sum3
Out
40
8
Cin
30
0
A3
B
28
Sum2
CIn
CarryOut
Seattle Pacific University
Cout stable at 40ns
EE 1210 - Logic System Design
Numbers-5
Number Systems- Negative Numbers
• What about negative numbers?
• We need to represent numbers less than zero as
well as zero or higher
• In n bits, we get 2n combinations
• Make half positive, half negative...
First method: use an extra bit for the sign
0 101
1 101
+5
-5
3 remaining bits for magnitude
Sign bit: 0-->positive, 1-->negative
Seattle Pacific University
EE 1210 - Logic System Design
Numbers-6
Sign and Magnitude Representation
Seven Negative
Numbers and
“Negative” Zero
-7
-6
1111
+1
0000
0001
1110
-5
1101
-4
1100
-3
1011
-2
0010
+2
Inner numbers: 0011 +3
Binary
representation 0100 +4
1010
0101
1001
-1
Note: Example is shown
for 4-bit numbers
+0
Seven Positive Numbers
and “Positive” Zero
+5
0110
1000
-0
0111
+6
+7
• High order bit is sign: 0 = positive (or zero), 1 = negative
• Three low order bits represent the magnitude: 0 (000) through 7 (111)
• Number range for n bits = +/- 2n-1 -1
• Two different representations for 0!
• Two discontinuities
Seattle Pacific University
EE 1210 - Logic System Design
Numbers-7
Two’s Complement Representation
Re-order Negative
Numbers to
Eliminate
Discontinuities
-1
-2
1111
+1
0000
0001
1110
-3
1101
-4
1100
-5
1011
-6
0010
0101
1001
Eight Positive Numbers
+5
0110
1000
0111
-8
• Only one discontinuity now
• Only one zero
• One extra negative number
Seattle Pacific University
+2
Inner numbers: 0011 +3
Binary
representation 0100 +4
1010
-7
Note: Example is shown
for 4-bit numbers
+0
+6
+7
Note: Negative numbers
still have 1 for MSB
EE 1210 - Logic System Design
Numbers-8
2’s Complement Negation Method #1
To calculate the negative of a 2’s complement number:
1. Complement the entire number
2. Add one
Examples:
n = 0110= 6
complement
1001
add 1
-n =1010 = -6
Seattle Pacific University
WARNING: This is for calculating
the negative of a number. There is
no such thing as “taking the 2’s
complement of a number”.
n = 01000100 = 68
complement
n = 10010000= -112
complement
10111011
add 1
01101111
add 1
-n =10111100 = -68
-n =01110000 = 112
EE 1210 - Logic System Design
Numbers-9
2’s Complement Negation Method #2
To calculate the negative of a 2’s complement number:
1. Starting at LSB, search to the left for the first one
2. Copy (unchanged) the first one and everything to its right
3. Complement the remaining bits
Examples:
n = 0110= 6
complement
copy
n = 01000100 = 68
complement
copy
-n = 10111 100 = -68
-n = 1010 = -6
n = 10010000= -112
complement
copy
-n = 01110000 = 112
Seattle Pacific University
EE 1210 - Logic System Design
Numbers-10
Adding Two’s Complement Numbers
Just add the complete
numbers together.
4
0100
-4
1100
+3
0011
+ (-3)
1101
7
0111
-7
1 1001
Sign taken care of
automatically.
4
0100
-4
1100
-3
1101
+3
0011
1
1 0001
-1
1111
Discard carry-out (for now)
A carryout from MSB does not necessarily mean overflow!
Seattle Pacific University
EE 1210 - Logic System Design
Numbers-11
Overflow
Overflow:
- Add two positive numbers to get a negative number
- Add two negative numbers to get a positive number
Not a discontinuity No Overflow
-1
-2
1111
+0
0001
1110
-3
+1
0000
1101
0010
5 + 3 = -8
+2
-4
1100
0011
+3 -7 - 2 = +7
-5
1011
0100
+4
-6
1010
0101
1001
A carryout from the
MSB could mean
crossing at either of
these places – One is
OK, one is Overflow
Seattle Pacific University
-7
0110
1000
-8
0111
+7
+6
+5
Overflow occurs when
crossing bottom
discontinuity
Overflow cannot occur when
adding a positive and negative
number together
EE 1210 - Logic System Design
Numbers-12
Detecting Overflow
Overflow occurs when:
We add two positive numbers and obtain a negative
We add two negative numbers and obtain a positive
Looking at the sign bit (MSB):
+
+
+
Cout
0
0
+0
0
Cin
0
No overflow
+
+
-
Cout
0
0
+0
1
Cin
1
Overflow
+
Cout
1
1
+1
0
Overflow
Overflow when carryin to sign
bit does not equal carryout
Seattle Pacific University
Cin
0
-
Cout
1
1
+1
1
Cin
1
No Overflow
+
-
Cout
0
1
+0
1
Cin
0
No Overflow
Cin
Cout
EE 1210 - Logic System Design
Cout
1
1
+ +0
+
0
Cin
1
No Overflow
Overflow
Numbers-13
Two’s Complement Summary
• Two’s complement representations must specify
the number of bits
• -3 is 1101 in 4-bit, 11111101 in 8-bit, 111111111101 in
12-bit
• When adding two’s complement numbers, discard
the carryout from MSB
• This is NOT overflow  it is OK
• To represent positive numbers in 2’s complement,
just copy them
• +2 in 4-bit two’s complement  0010
• To represent negative number in 2’s complement,
write out their negative and negate it
• -3 is -(+3)  - (0011) = 1101
Seattle Pacific University
EE 1210 - Logic System Design
Numbers-14
4-bit Ripple Carry Adder/Subtractor
Subtract
CarryIn
Subtraction: Adding the negative
of the subtracted number
A0
B0
In 2’s complement:
Negative obtained by:
Complementing and adding 1
+
C
Sum0
Out
A1
B1
CIn
+
C
To subtract A3A2A1A0 - B3B2B1B0:
1. Complement B3B2B1B0 by
complementing each one
individually (for subtract only)
CIn
Sum1
Out
A2
B2
CIn
+
C
Sum2
Out
2. Add one to total by setting
global Cin to 1 (for subtract only)
A3
B3
CIn
+
C
Sum3
Out
CarryOut
Seattle Pacific University
EE 1210 - Logic System Design
Numbers-15