CH1 Number Systems and Conversion

Presentation on theme: "CH1 Number Systems and Conversion"— Presentation transcript:

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

2 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 台灣大學 吳安宇 教授

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

4 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 台灣大學 吳安宇 教授

5 Number System and Conversion
Decimal (Base 10) Number (separated by decimal point): ( ) = 9* * * * *10-2 Binary (Base 2) Number (separated by binary point): ( ) = 1*23 + 0*22 + 1*21 + 1*20 + 1* *2-2 = /2 +1/4 = (11.75)10 台灣大學 吳安宇 教授

6 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 台灣大學 吳安宇 教授

7 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*R 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* = ( )10 EX：R=16, Digits = { 0,1,2,...,A,B,C,D,E,F } (A2F)16 = 10* *161 + F* = (2607)10 台灣大學 吳安宇 教授

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

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

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

11 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 台灣大學 吳安宇 教授

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

13 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 = ( ……)2 台灣大學 吳安宇 教授

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

15 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 台灣大學 吳安宇 教授

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

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

18 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 台灣大學 吳安宇 教授

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

20 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 台灣大學 吳安宇 教授

21 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) 台灣大學 吳安宇 教授

22 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) 台灣大學 吳安宇 教授

23 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 台灣大學 吳安宇 教授

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

25 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 – ( ) = ( )2 台灣大學 吳安宇 教授

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

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

28 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 台灣大學 吳安宇 教授

29 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 台灣大學 吳安宇 教授

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

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

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

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

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

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

36 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. 台灣大學 吳安宇 教授

37 Addition of 1’s Complement Numbers
Addition of positive & negative numbers (a) (correct) (b) (end-around carry) (correct, no overflow) 台灣大學 吳安宇 教授

38 Addition of 1’s Complement Numbers
Adding two negative numbers (a) (end-around carry) (-7) (correct, no overflow) (b) (end-around carry) (wrong, overflow!!) 台灣大學 吳安宇 教授

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

40 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 台灣大學 吳安宇 教授

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

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

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

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