SYEN 3330 Digital Systems Chapter 5 Part 2 SYEN 3330 Digital Systems Jung H. Kim Chapter 5-2 1 Complements Subtraction of numbers requires a different algorithm than addition. Adding a complement of a number is equivalent to subtraction. We will discuss two complements: Diminished Radix Complement Radix Complement Subtraction will be accomplished by adding a complement. SYEN 3330 Digital Systems Chapter 5-2

Page 2 Diminished Radix Complement Given a number N in Base r having n digits, the (r-1)'s complement (called the Diminished Radix Complement) is defined as: (rn - 1) - N Example: For r = 10, N = 123410, n = 4 (4 digits),we have: (rn - 1) = 10,000 -1 = 999910 The 9's complement of 123410 is then: 999910 - 123410 = 876510 SYEN 3330 Digital Systems Chapter 5-2 Page 3 Binary 1's Complement For r = 2, N = 011100112, n = 8 (8 digits), we have: (rn - 1) = 256 -1 = 25510 or 111111112 The 1's complement of 011100112 is then:

111111112 - 011100112 ---------------100011002 NOTE: Since the 2n-1 factor consists of all 1's and since 1 - 0= 1 and 1 - 1 = 0, forming the one's complement consists of complementing each individual bit. SYEN 3330 Digital Systems Chapter 5-2 Page 4 Radix Complement Given a number N in Base r having n digits, the r's complement (called the Radix Complement) is defined as: for N 0 and rn - N 0 for N = 0 Note that the Radix Complement is obtained by adding 1 to the Diminished Radix Complement. Example:

For r = 10, N = 123410, n = 4 (4 digits), we have: rn = 10,00010 The 10's complement of 123410 is then 10,00010 - 123410 = 876610 or 8765 + 1 (9's complement plus 1) SYEN 3330 Digital Systems Chapter 5-2 Page 5 Binary 2's Complement For r = 2, N = 011100112, n = 8 (8 digits), we have: (rn ) = 25610 or 1000000002 The 2's complement of 011100112 is then: 1000000002 - 011100112 ---------------100011012 Note that this is the 1's complement plus 1. SYEN 3330 Digital Systems Chapter 5-2 Page

6 Binary 2's Complement Examples 100000000 - 11011100 ----------------00100100 100000000 - 00000000 ----------------00000000 100000000 11111111 ----------------00000001 (The 2's complement of 0 is zero!) (could this be -1)? (could this be +1?) SYEN 3330 Digital Systems Chapter 5-2 Page 7

Efficient 2s Complement Given: an n-bit binary number: an-1an-2 ai+110...00 Where for some digit position i, ai is 1 and all digits to the right are 0, form the twos complement value this way: and Leave ai equal to 1 (unchanged), Leave rightmost digits 0 (unchanged), and ` complement all other digits to the left of ai. (0 replaces 1, 1 replaces 0) SYEN 3330 Digital Systems Chapter 5-2 Page 8 Two's Complement Example 01101011100011100000

First 1 from right --- -Complement leftmost digits ------------------ 10010100011100100000 ------ Leave these This becomes 0110100111100 1001011000100 This becomes 1000000000000 1000000000000 SYEN 3330 Digital Systems Chapter 5-2 Page 9 Subtraction with Radix Complements Subtract two n-digit, unsigned numbers M N,

in base r as follows: 1. Add the minuend M to the r's complement of the subtrahend N to perform: n n M + (r - N) = M N + r 2. If M N, the sum will produce an end carry, rn which is discarded; what is left is the result, M N. 3. If M < N, the sum does not produce an end carry and is equal to rn - ( N - M ), which is the r's complement of ( N M ). To obtain the answer in a familiar form, take the r's complement of the sum and place a negative sign in front. SYEN 3330 Digital Systems Chapter 5-2 Page 10 Example: Find 543 10 - 123

10 1). Form 10's complement of 123: 1000 - 123 ----------877 2). Add the two: 543 (+) 877 ------------1420 3). Since M > N, we discard the carry. Ans: 420 SYEN 3330 Digital Systems Chapter 5-2 Page 11

Example: Find 123 10 - 543 10 1). Form 10's complement of 543: 2). Add the two: 3). Since M < N, form complement Answer is ( )420. SYEN 3330 Digital Systems 1000 543 ----------457 123 (+) 457 ------------580 (no carry) 1000

( ) 580 ----------420 Chapter 5-2 Page 12 Binary Example Compute: 1010100 - 1000011 1). Form 2's complement of 1000011: 2). Add the two: 3). Since M N, discard the carry. SYEN 3330 Digital Systems 1000011 0111101 1010100 0111101 (+) ------------1 0010001 (a carry ) Ans. = 0010001

Chapter 5-2 Page 13 Another Binary Example Compute: 1000011 - 1010100 1). Form 2's complement of 1010100: 2). Add the two: 1010100 0101100 1000011 0101100 (+) ------------1101111 (no carry) 3). Since M < N, complement the result. Ans. = ( ) 0010001 SYEN 3330 Digital Systems Chapter 5-2

Page 14 Subtract: Add 1s Complement We can use addition of the 1's complement to subtract two numbers with a minor modification. Since (r-1)'s complement is one less than the r's complement, the result produces a sum which is one less than the correct sum when an end carry occurs. We can simply add in the end carry when it occurs to correct the answer. If the end carry does not occur, the result is negative and we can use the 1's complement to represent the negative result. SYEN 3330 Digital Systems Chapter 5-2 Page 15 1s Complement Subtraction Use 1's complement to compute 1010100 - 1000011 1). Form 1's complement of 1000011:

2). Add the two: 3). Add carry, end around 1000011 0111100 1010100 0111100 (+) ------------10010000 (a carry) (+) 0000001 ------------0010001 Ans. = 0010001 SYEN 3330 Digital Systems Chapter 5-2 Page 16 1s Complement Subtraction Use 1's complement for computing 1000011 - 1010100

1). Form 1's complement of 1010100: 1010100 0101011 2). Add the two: 1000011 0101011 (+) ------------1101110 (no carry) 3). Form 1's complement: 0010001 4). The answer has a negative sign. Ans. = ( ) 0010001 SYEN 3330 Digital Systems Chapter 5-2 Page 17 Signed Integers Positive numbers and zero can be represented by unsigned ndigit, radix r numbers. We need a representation for negative numbers.

To represent a sign (+ or -) we need exactly one more bit of 1 information (1 binary digit gives 2 = 2 elements which is exactly what is needed). Since most computers use binary numbers, by convention, (and for convenience), the most significant bit is interpreted as a sign bit as shown below: san-2 a2a1a0 Where: and SYEN 3330 Digital Systems s = 0 for Positive numbers s = 1 for Negative numbers ai are 0 or 1 Chapter 5-2 Page 18 Interpreting the Other Digits Given n binary digits, the digit with weight 2(n-1) is the sign and the digits with weights 2(n-2) down to 2(0) can be used to represent 2(n1) distinct elements. There are several ways to interpret the other digits. Here are three popular choices:

1. Signed-Magnitude -- here the n-1 digits are interpreted as a positive magnitude. 2. Signed-Complement -- here the digits are interpreted as the rest of the complement of the number. There are two possibilities here: 2a. Signed One's Complement -(use the 1's Complement to compute) 2b. Signed Two's Complement -(use the 2's Complement to compute) SYEN 3330 Digital Systems Chapter 5-2 Page 19 Example: Given r=2, n=3 We have the following interpretations for signed integer representation: Number Sign-Mag. 1's Comp. 2's Comp. +3 011 011 011 +2 010 010 010

+1 001 001 001 +0 000 000 000 -0 100 111 ---1 101 110 111 -2 110 101 110 -3 111 100 101 -4 ----100

SYEN 3330 Digital Systems Chapter 5-2 Page 20 Addition with Signed Numbers Caution: If you use all rn possible combinations of n radix r digits, some operations on elements of the set will produce elements which will not be represented in the set. Example: Add unsigned, 3-bit integers 1012 to 1002 to get 10012 (5 + 4 = 9). This result cannot be represented in the set of 3-bit unsigned integers. An overflow is said to have occurred. SYEN 3330 Digital Systems Chapter 5-2 Page 21 Signed-Magnitude Arithmetic

Addition: If signs are the same: 1. Add the magnitudes. 2. Check for overflow (a carry into the sign bit). 3. The sign of the result is the same. If the signs differ: 1. Subtract the magnitude of the smaller from the magnitude of the larger. 2. Use the sign of the larger magnitude for the sign of the result. 3. Overflow will never occur. Subtraction: Complement the sign bit of the number you are subtracting and follow the rules for addition. SYEN 3330 Digital Systems Chapter 5-2 Page 22 Sign-Magnitude Examples Same signs 000 + 001 = 001 (signs are the same) 010 + 010 = x00 (Overflow into sign bit) 101 + 101 = 110 (signs are the same)

110 + 110 = x00 (Overflow into sign bit) Different signs 001 + 110 = 101 (010 001, take sign) 111 + 010 = 101 (011 001, take sign) 101 + 010 = 001 (010 001, take + sign) 100 + 000 = ?00 (is it + or - zero?) SYEN 3330 Digital Systems Chapter 5-2 Page 23 Signed-Complement Arithmetic Addition: 1. Add the numbers including the sign bits, discarding a carry out of the sign bits (2's Complement), or using an end-around carry (1's Complement). 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. SYEN 3330 Digital Systems Chapter 5-2 Page 24 Binary Adder/Subtractor Subtraction can be accomplished by addition of the Two's Complement. Thus we:: 1. Complement each bit (One's Comp.) 2. Add one to the result. The following circuit computes A - B: It computes A - B when the Carry-In is "1" by forming the One's Complement of B using EXOR gates and adding one A(3)

B(3) C(4) x Co y FA S S(3) SYEN 3330 Digital Systems Ci C(3) A(1) B(1) A(2) B(2)

x Co y FA S S(2) Ci C(2) x Co y FA Ci C(1)

S S(1) Chapter 5-2 A(0) B(0) x Co y FA S S(0) Page 25 Ci C(0)