Transcript Automatic Dot Detection of Optical Braille Images

CS151
Introduction to Digital Design
Chapter 4: Arithmetic Functions and HDLs
4-4 : Binary Adder-Subtractor
Created by: Ms.Amany AlSaleh
1
4-4 : Binary Adder-Subtractor
 Subtraction can be done by addition of the 2's Complement.
1. Complement each bit (1's Complement.)
2. Add 1 to the result.
 The circuit shown computes A + B and A – B:
• For S = 1:
• Subtract  Bi  1 = Bi’ and C0 = 1
• the 2’s complement of B is formed
complement and adding the 1 applied to C0.
by
using
XORs
to
form
the
1’s
• For S = 0:
• add, Bi  0 = Bi and C0 = 0
• B is passed through unchanged.
Created by: Ms.Amany AlSaleh
2
Binary Adder-Subtractor (Cont.)

Using the 2’s complement we have eliminated the
subtraction operation and need:
•
Complementer
•
Adder

To perform subtraction:
•

To perform addition:
•

Complement N
Do not complement N
Perform both operations
complementer and adder.
by
Created by: Ms.Amany AlSaleh
using
a
selective
3
Signed Integers
 Positive numbers and zero can be represented by unsigned n-digit,
radix r numbers. We need a representation for negative numbers.
 To represent a sign (+ or –) we need exactly one more bit of
information (1 binary digit gives 21 = 2 elements which is exactly what
is needed).
 Since computers use binary numbers, by convention,
significant bit is interpreted as a sign bit:
the most
s an–2  a2a1a0
where:
s = 0 for Positive numbers
s = 1 for Negative numbers
“Signed Magnitude System”
Created by: Ms.Amany AlSaleh
4
Signed Integers
 Inside a computer both signed and unsigned numbers consist of string
of bits. The user determines whether this represents a singed or
unsigned number.
 Singed number: MSB  sign and the rest represents the number
 Unsigned: all bits represent the number
 E.g.:
 01001:
• Unsigned binary: 9
• Signed binary: +9
 11001:
• Unsigned binary: 25
• Signed binary: -9
Created by: Ms.Amany AlSaleh
5
Signed Integer Representations
Signed-Magnitude:
• MSB  sign
• the n – 1 digits are interpreted as a positive magnitude.
Signed-Complement:
• Here the digits are interpreted as the rest of the complement of the number.
There are two possibilities here:
• Signed 1's Complement: Uses 1's Complement Arithmetic
• Signed 2's Complement: Uses 2's Complement Arithmetic
All previous formats consist of a string of 0’s and 1’s! User determines
interpretation.
E.g.: Represent (+9) and (-9) in the two systems mentioned above.
Assume 8 bits are needed to represent each number.
• +9  0000 1001 in both systems
• -9  1000 1001 signed magnitude representation
• -9  1111 0111 signed 2\s complement representation
Created by: Ms.Amany AlSaleh
6
Signed Binary Representation Example2
 n= 4  we can represent 16 binary
numbers:
• Sign magnitude: 7 +ve, 7 –ve and
2 signed 0’s.
• signed 2’s complement: 7 +ve, 8
-ve and 1 zero.
 Note that positive numbers have the
same
representation
in
both
systems and have 0 in the msb.
 The signed 2’s complement has one
representation for 0 which is always
positive.
 The signed magnitude system has a
positive 0 and a negative 0.
The signed complement is normally used in computer arithmetic.
Created by: Ms.Amany AlSaleh
7
Signed Integer Representation Example
 r =2, n=3  8 different binary numbers.
Number
+3
+2
+1
+0
–0
–1
–2
–3
–4
Sign -Mag.
011
010
001
000
100
101
110
111
—
1's Comp.
011
010
001
000
111
110
101
100
—
Created by: Ms.Amany AlSaleh
2's Comp.
011
010
001
000
—
111
110
101
100
8
Signed-Magnitude Arithmetic

For an n-bit number, the single sign bit in the msb and the
n-1 magnitude are processed separately.
•
Magnitude bits are processed as unsigned numbers.
s an–2  a2a1a0
S=0  + (an–2  a2a1a0)
S=1 
- (an–2  a2a1a0)

If the signs are the same, add the two magnitudes and give the result
the sign of M.

If the signs are different, subtract the magnitude of N from the
magnitude of M:

The absence or presence of an end borrow determines the sign of
the result and whether or not a 2’s complement correction is needed.
Created by: Ms.Amany AlSaleh
9
Signed-Magnitude Arithmetic Example

Add:
0 0011001
+ 1 0100101
This causes 0100101 to be subtracted from 0011001:
1
0011001
- 0100101
1110100
End
Borrow
2’s comp
-0001100
1 0001100
The end borrow shows that M<N so the result should be –ve.
Created by: Ms.Amany AlSaleh
10
Signed 2’s Complement Arithmetic
 Addition:
1. Add the numbers including the sign bits, discarding a carry out of the sign
bits.
2. If the sign bits were the same for both numbers and the sign of the result is
different, an overflow has occurred.
3. The sign of the result is computed in step 1.
 Subtraction:
Form the complement of the number you are subtracting and follow the rules
for addition.
What does 11111001 represent in signed 2’s complement?
The left most bit is 1  the number is neagtvie.
Take the 2’s complement: 0000 0111  binary equivalent of 7  the original
number is -7.
Created by: Ms.Amany AlSaleh
11
Signed 2’s Complement Examples
 Example 1:
1
Discarded
1101
+ 0011
0000
 Example 2:
1
1101
-0011
2’s comp
Discarded
1101
+ 1101
1010
Created by: Ms.Amany AlSaleh
12
Signed 2’s Complement Examples (Cont.)
 Examples: Signed Binary Addition Using 2’s Complement
+6
00000110
-6
11111010
+13
+ 00001101
+13
+ 00001101
+19
00010011
+13
00000111
+6
00000110
-6
11111010
-13
+ 11110011
-13
+ 11110011
-7
11111001
-19
11101101
Created by: Ms.Amany AlSaleh
13
Signed 2’s Complement Examples (Cont.)
 Examples: Signed Binary Subtraction Using 2’s Complement
-6
-(-13)
11111010
11111010
- 11110011
+ 00001101
+7
00000111
+6
00000110
00000110
-(-13)
- 11110011
+ 00001101
11111001
00010011
+19
Created by: Ms.Amany AlSaleh
14
Overflow Detection
 Overflow occurs if n + 1 bits are required to contain the result from an n-bit
addition or subtraction
 Overflow can occur for:
• Addition of two operands with the same sign
• Subtraction of operands with different signs
 Detection can be performed by examining the result signs which should match the
signs of the top operand
 Examples: Assuming two signed numbers are stored in 2 8-bit registers  range of binary
numbers each register can accommodate is -128 to +127.
010000000
+70
+80
-----+150
01000110
01010000
------------10010110
Sum 150 exceeds capacity
-70
-80
-----150
1 01100000
10111010
10110000
-------------01101010
Sum -150 exceeds capacity
Created by: Ms.Amany AlSaleh
15
Overflow Detection Logic

Overflow can be signaled by detecting the inequality of the
carry into the sign bit position and the carry out of the sign
bit position.
Created by: Ms.Amany AlSaleh
16