Transcript Document

EE207: Digital Systems I,
Semester I 2003/2004
CHAPTER 3-v:
Combinational Logic Design
(Section 3.9-3.11)
Overview

Binary Subtraction
2’’s complement
 Extension to r’s complement



Subtraction with complements
Binary Adders/Subtractors
Signed numbers
 Signed Addition/Subtraction
 Overflow problem


Binary Multipliers
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
2
Binary Subtraction


Unsigned numbers: minus sign is not explicitly
represented.
Given 2 binary numbers M and N, find M-N:


Case I: M ≥ N, thus, MSB of Borrow is 0
B000110
M 1 1110
30
N -1 0 0 1 1
-19
Result is Correct
Dif 0 1 0 1 1
11
Case II: N > M, thus MSB of Borrow is 1
B11 1000
M 1001 1
19
N -1 1 1 1 0
-30
Result requires correction!
Dif 1 0 1 0 1
21
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
3
Binary Subtraction (cont.)




In general, if N > M, Dif = M-N+2 ,
where n = # bits.
In Case II of the previous example,
5
Dif= 19-30+2 = 21.
To correct the magnitude of Dif, which
n
n
should be N-M, calculate 2 -(M-N+2 ).
This is known as the 2’’s complement of
Dif.
7-Jul-15
n
Chapter 3-v: Combinational Logic Design (3.9-3.11)
4
General Procedure

To subtract two n-bit numbers, M-N, in
base 2:
Find M-N.
 If MSB of Borrow is 0, then M ≥ N. Result
is positive and correct.
 If MSB of Borrow is 1, then N > M. Result
is negative and its magnitude must be
n
corrected by subtracting it from 2 (find
its 2’s complement).

7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
5
Another Subtraction Example

Given M = 01100100 and N = 10010110, find M-N.
B 10011 1100
M
01100100
N
-1 0 0 1 0 1 1 0
Dif 1 1 0 0 1 1 1 0
n
100000000
Dif - 1 1 0 0 1 1 1 0
0001 1 0010
2
7-Jul-15
100
-50
206
256
-206
50
Chapter 3-v: Combinational Logic Design (3.9-3.11)
6
Block Diagram for Subtractor
M0M1M2M3
B
N0N1N2N3
4-bit Subtractor
Enabled when B=1;
otherwise, just pass the
result from the subtractor
Selective
2’s Complementer
Not the best way to implement a subtractor circuit!
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
7
Block Diagram for
Binary Adder-Subtractor
N0N1N2N3
M0M1M2M3
 
 
Binary Adder
 


B
4-bit Subtractor
Selective
2’s Complementer
Sub/Add
Quadruple 2-to-1 MUX
Result
7-Jul-15
Sub/Add=1  Result=|M-N|
Sub/Add=0  Result=M+N
Chapter 3-v: Combinational Logic Design (3.9-3.11)
8
Complements

There are 2 types of complements for
each base-r system:
Radix (r’s) complement, ex. 2’s complement
and 10’s complement.
 Diminished radix (r-1’s) complement, ex. 1’s
complement and 9’s complement.


We examine only 2’s and 1’s
complements for base 2. Same concepts
hole for other bases (ex. decimal).
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
9
2’s Complement

For a positive n digit number N2 in binary, the
2's complement, 2C(N2), is given by:


{0
2n-N2 ,
,
if n > 0
if n = 0
Example: N2 =1010


2C(N2) =
2C(N2) = 24-N2 = 100002 – 10102 = 01102
Example: N2 =11111

7-Jul-15
2C(N2) = 25-N2 = 1000002 – 111112 = 00001 2
Chapter 3-v: Combinational Logic Design (3.9-3.11)
10
2’s Complement (cont.)
Here’s an easier way to compute the 2’s
complement:

1.
2.

Leave all least significant 0’s and first 1 unchanged.
Replace 0 with 1 and 1 with 0 in all remaining higher
significant bits.
Examples:
complement unchanged
N = 1010
01 10
2’s complement

7-Jul-15
complement unchanged
N = 01011000
10101000
2’s complement
Chapter 3-v: Combinational Logic Design (3.9-3.11)
11
1’s Complement

For a positive n digit number N2 in binary, the
1's complement, 1C(N2), is given by:




1C(N2) = (2n-1) - N2
Example: N2 =011
3

1C(N2) = (2 -1)-N2 = 1112 – 0112 = 1002

1C(N2) = (24-1) - N2 = 11112 – 10102 = 0101 2
Example: N2 =1010
Observation: 1’s complement can be derived
by just complementing all the bits in the
number.
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
12
Observation

Compare 1’s complement with 2’s
complement:



2n-N = [(2n-1) - N] + 1
Thus, the 2’s complement can be obtained by
deriving the 1’s complement and adding 1 to it.
Example:
N = 1001
4
 2C(N) = 2 – N = 10000 – 1001 = 0111
4
 1C(N) = 2 – 1 - N = 1111 – 1001 = 0110
 2C(N) = 1C(N) + 1 = 0110 + 0001 = 0111

7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
13
Subtraction with Complements


To perform M-N = M+(-N), we may use a
complement form to represent the
negative number -N, and perform a
“plain old addition”.
Need to be able to “convert” the result.
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
14
Subtraction with 2’s complement

1.
2.
3.
If we use 2's complements to represent
negative numbers:
n
n
Form RI = M + 2C(N2) = M + (2 -N) = M – N + 2 .
If there is a nonzero carry out of the addition,
M ≥ N, so discard that carry and the remaining
digits are the result R = M-N.
Otherwise, M < N, so take the 2’s complement
n
n
n
of RI (=2 - RI = 2 - (M – N + 2 ) = N – M), and
attach a minus sign in front, i.e., the result R is
-2C([RI]2) = -(N-M).
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
15
Example


A = 1010100 (8410), B = 1000011 (6710)
Find R = A-B:
2C(B) = 0111101 (6110)
 A+B = 1010100+0111101 = 10010001
 Discard carry, R = 0010001 (1710) ✔


Find R = B-A:
2C(A) = 0101100 (4410)
 B+A = 1000011+0101100 = 1101111
 R = -2C(B+A) = -0010001 (-17) ✔

7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
16
Subtraction with 1’s complement

1.
2.
3.
If we use 1's complements to represent negative
numbers:
Form
n
n
RI = M + 1C(N2) = M + (2 -1-N) = M – N + 2 -1.
If there is a nonzero carry out of the addition,
M ≥ N, so discard that carry and add 1 to the
remaining digits. The result R = M-N.
Otherwise,
M < N,nso take the 1’s ncomplement of
n
RI (=2 - 1 - RI = 2 - 1 - (M – N + 2 -1) = N – M ),
and attach a minus sign in front, i.e.,
the result R is -1C([RI]2) = -(N-M).
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
17
Example


A = 1010100 (8410), B = 1000011 (6710)
Find R = A-B:




1C(B) = 0111100 (6010)
A+B = 1010100+0111100 = 10010000
Discard carry and add 1,
R = 0010000 + 1 = 0010001 (1710) ✔
Find R = B-A:



7-Jul-15
1C(A) = 0101011
B+A = 1000011+0101011 = 1101110
R = -1C(B+A) = -0010001 (-17) ✔
Chapter 3-v: Combinational Logic Design (3.9-3.11)
18
Binary Adder/Subtractors


If we perform subtraction using complements,
we eliminate the subtraction operation, and
thus, can use an adder with appropriate
complementer for subtraction.
Actually, we can use an adder for both
addition and subtraction:



Complement subtrahend for subtraction
Do not complement subtrahend for addition
Thus, to form an adder-subtractor circuit, we
only need a selective complementer and an
adder.
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
19
Binary Adder/Subtractors (cont.)


The subtraction A-B can be performed by
taking the 2's complement of B and adding to
A.
The 2's complement of B can be obtained by
complementing B and adding one to the result.
A-B = A + 2C(B)
= A + 1C(B) + 1
= A + B’ + 1
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
20
4-bit Binary Adder/Subtractor
–XOR
7-Jul-15
gates act as programmable inverters
Chapter 3-v: Combinational Logic Design (3.9-3.11)
21
4-bit Binary Adder/Subtractor (cont.)


When S=0, the circuit performs A + B.
The carry in is 0, and the XOR gates
simply pass B untouched.
When S=1, the carry into the least
significant bit (LSB) is 1, and B is
complemented (1’s complement) prior to
the addition; hence, the circuit adds to
A the 1’s complement of B plus 1 (from
the carry into the LSB).
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
22
4-bit Binary Adder/Subtractor (cont.)
S=0
B3
B2
B1
B0
0
S=0 selects addition
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
23
4-bit Binary Adder/Subtractor (cont.)
S=1
B3’
B2’
B1’
B0’
1
S=1 selects subtraction
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
24
4-bit Binary Adder/Subtractor (cont.)
When C4 = 0 and S=1 it means that A < B and we must correct
the result R3…R0 (see slide 15).
Thus, we must compute 2’s complement of R3…R0:
Use a specialized 2’s complement circuit or
Use the 4-bit Adder/Subtractor again, with A3…A0=0000,
B3…B0=R3…R0, and S=1.
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
25
Signed Binary Numbers

Signed-magnitude system: Singed
numbers are represented using the MSB
of the binary number to indicate the
number’s sign:
If MSB is 0  number is positive
 If MSB is 1  number is negative


Do not confuse with unsigned numbers!
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
26
Signed Binary Numbers (cont.)

For example:

-1010 is
-10102 in unsigned (- sign is implicit)
 110102 in singed (- sing is indicated in MSB=1)


Another example:

10112 is
1110 in unsigned
 -310 in signed

7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
27
Signed Binary Numbers (cont.)


To implement signed-magnitude addition
and subtraction we need to separate the
sing bit from the magnitude bits, and
treat the magnitude bits as an unsigned
number (do correction whenever
necessary).
To avoid correction, use the singedcomplement system.
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
28
Signed-Complement System


The magnitude of the negative number is
represented in a complement form (2’s or
1’s complement).
Ex.: Use 8-bits to represent -910 and 910

-910 is:




10010012 in singed-magnitude
111101102 in singed-1’s complement
111101112 in singed-2’s complement
910 is 000010012 in any of the above systems
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
29
Signed-Magnitude
Addition-Subtraction

To perform addition or subtraction of two
numbers M and N in signed-magnitude, follow
ordinary arithmetic rules:



Same signs: Add and keep same sign.
Different signs: Subtract N from M; if end Borrow is 1,
correct result by taking its 2’s complement. Sign is
negative.
Example: M:00011001, N:10100101
N is negative, so find |M-N|=0011001-0100101
=1110100, with end borrow 1. This implies that M-N is a
negative number, so to correct find its 2’s complement
0001100. Result is 10001100.
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
30
Signed-Complement Addition


“Addition of two signed numbers, with negative ones
represented in signed-2’s complement, is obtained by
adding the two numbers (including the sing bits).
Carry out is discarded”.
Examples: (Assume 5-bit representations)
01010 (+10)
+00101 (+5)
01111 (+15)
7-Jul-15
01010 (+10)
+11011 (-5)
00101 (+5)
10110 (-10)
+00101 (+5)
11011 (-5)
10110 (-10)
+11011 (-5)
10001 (-15)
Chapter 3-v: Combinational Logic Design (3.9-3.11)
31
Signed-Complement Addition
(cont.)


Do not get confused reading negative numbers
in signed-2’s complement! Remember, if MSB
is 1 the number is negative and you need to
find the 2’s complement of the magnitude.
Example: What’s the decimal equivalent of 10010012?
 Negative number, since MSB=1
 Magnitude = 001001
2’s complement of magnitude = 110111

7-Jul-15
The number is -5510
Chapter 3-v: Combinational Logic Design (3.9-3.11)
32
Signed-Complement Subtraction


“Subtraction of two signed numbers, with negative
ones represented in signed-2’s complement, is
obtained by taking the 2’s complement of the
subtrahend (including sing bit) and add it to the
minuend. Discard carry out”.
Examples: (Assume 5-bit representations)
01010 (+10)
-00101 -(+5)
01010 (+10)
-11011 -(-5)
10110 (-10)
-00101 -(+5)
10110 (-10)
-11011 -(-5)
01010 (+10)
+11011 +(-5)
00101 (+5)
01010 (+10)
+00101 +(+5)
01111 (+15)
10110 (-10)
+11011 +(-5)
10001 (-15)
10110 (-10)
+00101 +(+5)
11011 (-5)
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
33
The Overflow problem



If the sum of two n-bit numbers results
in an n+1 number, then an overflow
conditions is said to occur.
Detection of overflow can be
implemented using either hardware or
software.
Detection depends on number system
used: signed or unsigned.
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
34
The Overflow problem in
Unsigned System

Addition:


Subtraction:


When Carry out is 1.
Can never occur. Magnitude of the result is
always equal or smaller than the larger of
the two numbers.
 Not REALLY a problem!
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
35
The Overflow problem in
Signed-2’s Complement


Remember that the MSB is the sign.
But, the sign is also added! Thus, a carry
out equal to 1 does not necessarily
indicate overflow.
Overflow can occur ONLY when both
numbers have the same sign. This
condition can be detected when the
carry out (Cn) is different than the
carry at the previous position (Cn-1).
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
36
The Overflow problem in
Signed-2’s Complement (cont.)

Example 1: Let M=6510 and N=6510 in an 8-bit signed2’s complement system.



M = N = 010000012
M+N = 10000010 with Cn=0. This is clearly wrong! Bring Cn as
the MSB to get 0100000102 (13010) which is correct, but
requires 9-bits  overflow occurs.
Example 2: Let M=-6510 and N=-6510 in an 8-bit
signed-2’s complement system.


7-Jul-15
M = N = 101111112
M+N = 01111110 with Cn=1. This is wrong again! Bring Cn as the
MSB to get 1011111102 (-13010) which is correct, but also
requires 9-bits  overflow occurs.
Chapter 3-v: Combinational Logic Design (3.9-3.11)
37
Overflow Detection in
Signed-2’s Complement

Overflow conditions is detected by comparing
the carry values into and out of the sign bit
(Cn and Cn-1).
n-bit Adder/Subtractor with Overflow Detection Logic
V
C
Cn
Cn+1
n-bit Adder/Subtractor
• C =1 indicates overflow condition when adding/subtr. unsigned numbers.
• V=1 indicates overflow condition when adding/subtr. signed-2’s
complement numbers
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
38
Binary Multiplier

Binary multiplication resembles decimal
multiplication:

n-bit multiplicand is multiplied by each bit
of the m-bit multiplier, starting from LSB,
to form n partial products.
Each successive set of partial products is
shifted 1 bit to the left.
 Derive result by addition the m rows of
partial products.

7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
39
Binary Multiplier (cont.)

Example:


Multiplier A=A1A0 and multiplicand B=B1B0
Find C = AxB:
B1
x A1
B0
A0
-----------------
+ A1B1
A0B1 A0B0
A1B0
-------------------------------
C3
7-Jul-15
C2
C2
C0
Chapter 3-v: Combinational Logic Design (3.9-3.11)
40
Binary Multiplier Circuit
2-bit by 2-bit multiplier
Half Adders are Sufficient
since there is no Carry-in
in addition to the two inputs
to sum
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
41
Binary Multiplier Circuit
4-bit by 3-bit multiplier
4 bit by 3 bit yields a
7 bit result
7-Jul-15
Chapter 3-v: Combinational Logic Design (3.9-3.11)
42