Digital Design Number Systems Credits Slides adapted from J F Wakerly Digital Design 4 e Prentice Hall 2006 C H Roth Fundamentals of Logic Design 5 e Thomson 2004 1 Positional Number Systems A number is represented by a string of digits where each digit position has an associated weight and it has the following form dp 1dp 2 d1d0 d 1d 2 d n The value of the number is given by p 1 D d i r i i n 2 Binary Numbers The general form of a binary number of p n binary digits bits is bp 1bp 2 b1b0 b 1b 2 b n and its value is p 1 B bi 2 i i n 3 Octal and Hexadecimal Numbers The octal number system uses radix 8 while the hexadecimal number system uses radix 16 The octal and hex number systems are useful for representing multibit numbers 4 Conversion from Binary to Decimal p 1 Method summation B bi 2i i n Example 101110110012 1 210 0 29 1 28 1 27 1 26 0 25 1 24 1 23 0 22 0 21 1 20 149710 5 Conversion from Decimal to Binary Method successive divisions Example 6 EXAMPLE convert 5310 to binary 7 EXAMPLE convert 625ten to binary 8 EXAMPLE convert 0 710 to binary 9 EXAMPLE convert 231 34 to base 7 10 Addition of Binary Numbers EXAMPLE Add 1310 and 1110 in binary 11 Subtraction of Binary Numbers EXAMPLES 12 Representation of Negative Numbers Signed Magnitude Representation 10ten 10ten 001010two 101010two The number zero has two representations 0 and 0 An n bit signed magnitude number lies within the range 2n 1 1 through 2n 1 1 To add signed magnitude numbers we must examine the signs of the addends to determine what to do Radix Complement Representation Diminished Radix Complement Representation 13 Representing Numbers Key observation Numbers are just strings of symbols The meaning value we assign to each string instance pattern is up to us If the string is n symbols digits long and each symbol can take up to different r instances radix then we can form rn different patterns Common sense characteristics of a system number Assign a different value to each different pattern Split the patterns equally between positive numbers and negative numbers The mechanic of doing arithmetic operations should be as simple as possible 14 Complement Number Systems While the signed magnitude system negate a number by changing its sign a complement number system negates a number by taking its complement Radix complement Representation The complement of an n digit number D is obtained by subtracting it from rn rn D rn 1 D 1 Diminished Radix complement Representation In a diminished radix complement system the complement of an n digit number D is obtained by subtracting it from rn 1 15 Complement Number Systems 16 Complement Number Systems 17 Complement Number Systems Once we know how to compute the diminished radix complement of a number computing the radix complement is very simple radix complement diminished radix complement 1 9 0 1 8 2 7 3 6 5 4 18 C2 Number System For binary numbers the radix complement is called two s complement C2 The MSB of a number in this system serves as the sign bit Negative numbers have MSB equal to 1 Positive numbers have MSB equal to 0 The range of representable numbers is 2n 1 through 2n 1 1 Zero has only one representation 19 Two s Complement Number System 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 0 1 1 0000 1111 0001 2 2 0010 1110 3 3 1101 0011 4 0100 4 1100 5 0101 1011 5 1010 6 1001 7 1000 8 0111 7 0110 6 20 C1 Number System For binary numbers the diminished radix complement is called one s complement C1 The MSB of a number in this system serves as the sign bit Negative numbers have MSB equal to 1 Positive numbers have MSB equal to 0 The range of representable numbers is 2n 1 1 through 2n 1 1 Zero has two representations positive zero 00 00 and negative zero 11 11 21 Summary of Signed Number Systems 22 C1 Number System In the C1 number system to negate an n bit number all we have do is to flip invert all the bits 23 C2 Number System In the C2 number system to negate an n bit number requires two steps invert all bits of the number i e take the C1 of the number and then add 1 24 Playing with the C2 notation The sum of a number and its inverted representation must be 111 111two which in C2 represent 1 X X 1 X 1 X X X 1 0 25 C2 EXAMPLES 26 C2 sign extension As far as m n it is possible to convert n bit numbers into mbit numbers but some care is needed copy This the most significant bit the sign bit into the other bits 0010 0000 0010 1010 1111 1010 procedure is referred as sign extension 27 C2 Addition and Subtraction 1 Addition of 2 positive numbers sum 2 n 1 2 Addition of 2 positive numbers sum 2n 1 28 C2 Addition and Subtraction 3 Addition of positive and negative numbers negative number has greater magnitude 4 Addition of positive and negative numbers positive number has greater magnitude 29 C2 Addition and Subtraction 5 Addition of two negative numbers sum 2n 1 6 Addition of two negative numbers sum 2n 1 30 Detecting overflow Overflow occurs when the value affects the sign bit adding two positives yields a negative adding two negatives gives a positive subtract a negative from a positive and get a negative subtract a positive from a negative and get a positive No overflow when adding a positive and a negative number No overflow when subtracting two numbers of same sign Consider the operations A B and A B cannot occur Can overflow occur if B is 0 can occur Can overflow occur if A is 0 n 1 for A B if B 2 31 Binary Codes for Decimal Numbers 32 Gray Code 33 Character Codes 34 N cubes and Hamming distance 35 Traversing a 3 cube in Gray code order 36