CH1 Number Systems and Conversion Lecturer：吳安宇 教授 Date：2010/09/16

Outline Digital Systems and Switching Circuits Number Systems and Conversion Binary Arithmetic Representation of Negative Numbers Addition of 2’s Complement Numbers Addition of 1’s Complement Numbers Binary Codes 台灣大學 吳安宇 教授

Purpose Switching Circuits Input …… Output Design a switching network (Logic Function) ：Binary number Input Output Switching Circuits …… X1 X2 Xm Z1 Z2 Zm 台灣大學 吳安宇 教授

Outline Digital Systems and Switching Circuits Number Systems and Conversion Binary Arithmetic Representation of Negative Numbers Addition of 2’s Complement Numbers Addition of 1’s Complement Numbers Binary Codes 台灣大學 吳安宇 教授

Number System and Conversion Decimal (Base 10) Number (separated by decimal point): 953.7810 (210.-1-2) = 9*102 + 5*101 + 3*100 + 7*10-1 +8*10-2 Binary (Base 2) Number (separated by binary point): 1011.112 (3210.-1-2) = 1*23 + 0*22 + 1*21 + 1*20 + 1*2-1 + 1*2-2 = 8 + 0 +2 +1+1/2 +1/4 = (11.75)10 台灣大學 吳安宇 教授

Generalized Representation of an Positive integer N with Base (Radix) R： Name Decimal Binary Octal Hexadecimal Radix 10 2 8 16 Digits 0,1,2,3,4 ,5,6,7,8,9 0,1 0,1,2,3, 4,5,6,7 0,1,2,3,4,5, 6,7,8,9,A,B, C,D,E,F First seventeen positive integers 1 3 4 5 6 7 9 11 12 13 14 15 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 17 20 A B C D E F 台灣大學 吳安宇 教授

Generalized Representation of an Positive integer N with Base (Radix) R： N = (a4 a3 a2 a1 a0 . a-1 a-2 a-3)R = a4*R4 + a3*R3 + a2*R2 + a1*R1 + a0*R0 + a-1*R-1 + a-2*R-2 + a-3*R-3 EX：R=8 , Digits = { 0,1,2,3,4,5,6,7 } (147.3)8 = 1*82 + 4*81 + 7*80 + 3*8-1 = (103.375)10 EX：R=16, Digits = { 0,1,2,...,A,B,C,D,E,F } (A2F)16 = 10*162 + 2*161 + F*160 = (2607)10 台灣大學 吳安宇 教授

Integer Conversion Using “Division Method” (1/2) 台灣大學 吳安宇 教授

Integer Conversion Using “Division Method” (2/2) EX：Convert (53)10 to Binary no. (53)10 = (110101)2 MSB MSB 台灣大學 吳安宇 教授

Conversion of A Decimal Fraction Using “Successive Multiplication” (1/3) Fi：Fraction Number 台灣大學 吳安宇 教授

Conversion of A Decimal Fraction Using “Successive Multiplication” (2/3) EX：Convert (0.625)10 to Binary number MSB MSB (0.625)10 = (0.101)2 台灣大學 吳安宇 教授

Conversion of A Decimal Fraction Using “Successive Multiplication” (3/3) EX：Convert (0.7)10 to Binary number (0.7)10 = 0.1 0110 0110 0110 …… (Base2) No exact conversion !!! Repeated Process 0.8, 1.6, 1.2, 0.4, …. 台灣大學 吳安宇 教授

Conversion (1/2) EX：Convert (231.3)4 to Base 7 number (231.3)4 = 2*42 + 3*41 + 1*40 + 3*4-1 = (45.75)10 Integer Fraction (45.75)10 = (63.51 51 51 ……)2 台灣大學 吳安宇 教授

Conversion (2/2) Conversion from Binary (Base 2) to Octal (Base 8) to Hexadecimal (Base 16) (11010111110.0111 )2 = (3276.34)8 (11010111110.0011)2 = (6BE.3)16 00 3 2 7 6 3 4(補0) Binary point ( R=2 ) Hexadecimal point decimal point (R=10) 6 B E 3 台灣大學 吳安宇 教授

Outline Digital Systems and Switching Circuits Number Systems and Conversion Binary Arithmetic Representation of Negative Numbers Addition of 2’s Complement Numbers Addition of 1’s Complement Numbers Binary Codes 台灣大學 吳安宇 教授

Binary Arithmetic -- Addition 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 (sum 0 & carry 1) EX： (Carry) 1111 台灣大學 吳安宇 教授

Binary Arithmetic -- Subtraction 0 – 0 = 0 1 – 0 = 1 1 – 1 = 0 0 – 1 = 1 (with borrow 1 from next column) EX： (Borrow) 1111 台灣大學 吳安宇 教授

Binary Arithmetic -- Multiplcation Multiplication 0 * 0 = 0 0 * 1 = 0 1 * 0 = 0 1 * 1 = 1 EX： (13)10 (11)10 copy of multiplicand if “1” multiplicand multiplier 台灣大學 吳安宇 教授

Binary Arithmetic -- Division 台灣大學 吳安宇 教授

Outline Digital Systems and Switching Circuits Number Systems and Conversion Binary Arithmetic Representation of Negative Numbers Addition of 2’s Complement Numbers Addition of 1’s Complement Numbers Binary Codes 台灣大學 吳安宇 教授

Signed Number Representation Magnitude signed bit bit bit bit bit bit bit bit bit A computer “word”, wordlength n = 8 bits (other popular n = 16 bits, 32 bits) 台灣大學 吳安宇 教授

Singed Magnitude Numbers N = (an-1 an-2 ……a1 a0)r N = ( s, an-2 ……a1 a0)2sm EX： N = -(13)10 = -(0,1101)2 = (1,1101)2sm Signed magnitude s = 0 if N 0 s = 1 if N 0 (2sm = Binary Singed Magnitude) 台灣大學 吳安宇 教授

Radix Complement Definition: The “radix complement [N]” of a number (N)r is defined as: N* (notation in textbook) = [N]r = rn – (N)r where n is the number of digits (wordlength) in (N)r The largest positive number (positive full scale) = rn-1 – 1 The most negative number (negative full scale) = - rn-1 台灣大學 吳安宇 教授

2’s Complement N* = [N]2 = 2n – (N)2 + [N]2 = - (N)2 EX：2’s complement of (N)2 = (01100101)2 [N]2 = [01100101]2 = 28 – (01100101)2 = (100000000)2 – (01100101)2 = (10011011)2 EX：show that (N)2 + [N]2 = 0 01100101 10011011 00000000 (carry) + 1 [N]2 = - (N)2 台灣大學 吳安宇 教授

2’s Complement EX：check (N)2 = [ [N]2 ]2 (by yourself) EX：2’s complement of (N)2 = (10110)2 for n=8 [N]2 = 28 – (10110)2 = (100000000)2 – (00010110)2 = (11101010)2 台灣大學 吳安宇 教授

2’s Complement Convert (N)2 to [N]2： First nonzero digit Method 1 N = 0 1 1 0 0 1 0 1 [N]2 = 1 0 0 1 1 0 1 1 N = 1 1 0 1 0 1 0 0 [N]2 = 0 0 1 0 1 1 0 0 First nonzero digit First nonzero digit 台灣大學 吳安宇 教授

2’s Complement Convert (N)2 to [N]2： Flip then Add 1 Method 2 N = 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 complement the bits 1 add 1 1 0 0 1 1 0 1 1 Flip then Add 1 台灣大學 吳安宇 教授

Two’s Complement System One’s Complement System Signed Decimal Sign Magnitude Binary Two’s Complement System One’s Complement System +15 +14 +13 +12 +11 +10 +9 +8 +7 +6 +5 +4 +3 +2 +1 0,1111 0,1110 0,1101 0,1100 0,1011 0,1010 0,1001 0,1000 0,0111 0,0110 0,0101 0,0100 0,0011 0,0010 0,0001 0,0000 (1,0000) (1,1111) for n = 5 台灣大學 吳安宇 教授

Two’s Complement System One’s Complement System Signed Decimal Sign Magnitude Binary Two’s Complement System One’s Complement System -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 1,0001 1,0010 1,0011 1,0100 1,0101 1,0110 1,0111 1,1000 1,1001 1,1010 1,1011 1,1100 1,1101 1,1110 1,1111 -------- 1,0000 for n = 5 台灣大學 吳安宇 教授

2’s Complement EX：2’s complement of –(13)10 for n = 8 (13)10 = (1011)2 = (00001101)2 -(00001101)2 = [00001101]2 = (11110011)2 EX：(n=8) Determine the decimal no. of N=(1,111,1010)2 1111010 (?) (-6) 0000110 (6) 台灣大學 吳安宇 教授

Radix Complement Arithmetic EX：compute (9)10 + (5)10 for 5-bit 2’s complement 0 1 0 0 1 (+9) + 0 0 1 0 1 (+5) 0 1 1 1 0 (+14) EX：compute (12)10 + (7)10 0 1 1 0 0 (+12) + 0 0 1 1 1 (+7) 1 0 0 1 1 (-13) EX：compute (12)10 – (5)10 = (12) + (-5) 0 1 1 0 0 (+12) + 1 1 0 1 1 (2’s complement of (5)2) 1 0 0 1 1 1 (+7) Add two positive no. and obtain a negative no. (overflow occurs!) discard the carry 台灣大學 吳安宇 教授

Radix Complement Arithmetic EX：(-9) – (5) = (-9) + (-5) 9 = 0 1 0 0 1  -9 = 1 0 1 1 1 5 = 0 0 1 0 1  -5 = 1 1 0 1 1 1 0 1 1 1  (-9) + 1 1 0 1 1  (-5) 1 1 0 0 1 0  (-14) discard (why?) EX：(-12) – (5) = (-12) + (-5) 1 0 1 0 0  (-12) + 1 1 0 1 1  (-5) 1 0 1 1 1 1  (+15) (overflow occurs) 台灣大學 吳安宇 教授

1’s & 2’s Complement 2’s complement is the main stream Check SIGN for the overflow! (+) + (+)  (-) (-) + (-)  (+) overflow!! 台灣大學 吳安宇 教授

Overflow Condition - ˇ ˇ：overflow x ：no overflow A B A+B A-B + x - +ˇ + ˇ ˇ：overflow x ：no overflow 台灣大學 吳安宇 教授

Diminished Radix Complement 1’s complement EX： 1 0 1 1 0 1 0 0 (N)2 0 1 0 0 1 0 1 1 1’s complement of (N)2 台灣大學 吳安宇 教授

Addition of 1’s Complement Numbers “End-around carry” : Instead of discarding the last carry (as in 2’s complement), it is added to the n-bit sum in the position furthest to the right. 台灣大學 吳安宇 教授

Addition of 1’s Complement Numbers Addition of positive & negative numbers (a) +5 0101 -6 1001 -1 1110 (correct) (b) -5 1010 +6 0110 +1 1 0000 1 (end-around carry) 0001 (correct, no overflow) 台灣大學 吳安宇 教授

Addition of 1’s Complement Numbers Adding two negative numbers (a) -3 1100 -4 1011 -7 1 0111 1 (end-around carry) 1000 (-7) (correct, no overflow) (b) -5 1010 -6 1001 -11 1 0011 1 (end-around carry) 0100 (wrong, overflow!!) 台灣大學 吳安宇 教授

Addition of 1’s Complement Numbers EX：Addition for a word-length of 8 (a) (-11) + (-20) in 1’s complement +11 = 00001011  (-11) = 11110100 +20 = 00010100  (-20) = 11101011 (1)11011111 1 (+31) 00011111 11100000 (-31) (b) (-8) + (+19) in 2’s complement 11111000 (-8) 00010011 (+19) (1)00001011 (+11) discard the last carry 台灣大學 吳安宇 教授

Outline Digital Systems and Switching Circuits Number Systems and Conversion Binary Arithmetic Representation of Negative Numbers Addition of 2’s Complement Numbers Addition of 1’s Complement Numbers Binary Codes 台灣大學 吳安宇 教授

Binary Codes BCD (Binary Coded Decimal) codes EX： 1 9 8 9 0001 1001 1000 1001 0： 0000 1： 0001 2： 0010 3： 0011 4： 0100 5： 0101 6： 0110 7： 0111 8： 1000 9： 1001 台灣大學 吳安宇 教授

Binary Codes ASCII codes keyboard  computer Character Binary Code Hexadecimal Code D i g t a l 1000100 1101001 1100111 1110100 1100001 1101100 44 69 67 74 61 6C Encode the word Digital in ASCII code, representing each character by two hexadecimal digits 台灣大學 吳安宇 教授

ASCII Code (Table 1-3 on p.22) 台灣大學 吳安宇 教授

Binary Codes for Decimal Digits 台灣大學 吳安宇 教授